使用A *搜索算法

Question

我正在從事圖挖掘工作，並且對於我目前的研究，我正試圖資助圖中非相鄰節點之間的鄰近性。

但是，由於非相鄰節點無處不在，所以我想縮小與圖中任何節點相關的非相鄰節點的數量。假設a是圖中的一個節點，我想找到最相關的非相鄰節點。爲此，我決定使用搜索算法，以便找到來自節點a的n-hop節點。

我最初想使用BFS，然後我決定更精確的算法：A星，所以可確定起始節點，並且必須最小化g和h功能和上限爲成本函數被最小化，因爲我不想指定目標節點。

這可能嗎？因爲我的目標是找到目標節點，而不是指定它。

Answer 1

想想這樣。將所有目標節點附加一個頂點，增加您的圖形。你能做一個A *搜索嗎？如果是這樣，那麼A *搜索對你很有用。

關鍵的是要有一個成本函數，將有用的下界放在距離目標節點多遠的地方，以便您將當前最有前途的搜索優先級放在沒有前景的搜索上，並儘快切換它不像其他東西那樣工作得很好。