使用A*搜索算法

Question

我在图挖掘领域工作，为了我目前的研究，我试图为图中不相邻的节点之间的邻近性提供资金。

但是，由于非相邻节点无处不在，所以我想缩小与图中任何节点相关的非相邻节点的数量。设a是图中的一个节点，我想找出它最相关的非相邻节点。为此，我决定使用搜索算法来查找，例如，从节点n-hop中查找a节点。

我最初想要使用BFS，然后我决定了一个更精确的算法：A星，这样我就可以确定开始节点，并将g和h函数最小化，并为代价函数最小化提供一个上限，因为我不想指定目标节点。

这是可能的吗？因为我的目标是找到目标节点，而不是指定它。

Answer 1

这样想吧。通过在图中多放置一个顶点，并附加到所有目标节点来增强图形。你能做个A*搜索吗？如果是这样的话，那么搜索对你是有用的。

关键是要有一个成本函数，它为您离目标节点有多远提供了一个有用的下限，这样您就可以将当前最有希望的搜索线优先于没有希望的搜索线，并在搜索不能正常工作时立即切换。