帶有統一成本搜索的圖示瀏覽

Question

我是這個網站的新手，所以希望你們不要介意幫忙。

無論如何，我被要求編寫代碼來查找特定圖形上的圖形巡視的最短成本，其詳細信息從文件讀入。該圖如下所示：

http://img339.imageshack.us/img339/8907/graphr.jpg

這是一個人工智能類，所以我希望用一個足夠體面的搜索方法（蠻力已被允許，但不爲滿分）。

我一直在閱讀，我認爲我在尋找的是具有不斷啓發式價值的A *搜索，我相信這是一個統一的成本搜索。我在包裝我的頭時遇到了麻煩，如何在Java中應用這個問題。

基本上，這是我有：

頂點類 -

ArrayList<Edge> adjacencies; 
String name; 
int costToThis; 

邊緣種類 -

final Vertex target; 
public final int weight; 

現在的那一刻，我努力工作，如何申請統一的成本概念到我期望的目標路徑。基本上我必須從一個特定的節點開始，訪問所有其他節點，並以最低的成本結束同一個節點。

據我所知，我可以使用PriorityQueue來存儲我所有的旅行路徑，但我無法圍繞如何將目標狀態顯示爲所有其他節點訪問的起始節點。

這裏是我到目前爲止，這是非常離譜：

public static void visitNode(Vertex vertex) { 
     ArrayList<Edge> firstEdges = vertex.getAdjacencies(); 
     for(Edge e : firstEdges) { 
     e.target.costToThis = e.weight + vertex.costToThis; 
     queue.add(e.target); 
     } 
     Vertex next = queue.remove(); 
     visitNode(next); 
    } 

最初這需要起始節點，然後遞歸訪問中時Queue的第一個節點（下一個最低成本路徑）。

我的問題基本上是，如果該路徑處於目標狀態，如何阻止我的程序跟隨隊列中指定的路徑？該隊列當前存儲頂點對象，但在我看來，這不會起作用，因爲我無法存儲是否在頂點對象內訪問過其他頂點。

非常感謝幫助！ Josh

編輯：我應該提到先前訪問的路徑可能會再次訪問。在我提供的情況下，這不是有益的，但可能會出現這樣一種情況：訪問以前訪問過的節點以訪問另一個節點會導致更短的路徑（我認爲）。因此，我不能只是做基於節點已經訪問過（這是我的第一個想法太）

Answer 1

兩點意見：

1）當你設置一個頂點的costToThis，重寫現有的值，並這會影響隊列中的所有路徑，因爲頂點由許多路徑共享。我不會將costToThis作爲Vertex的一部分存儲。相反，我會定義一個Path類，其中包含路徑的總成本加上構成它的節點列表。

2）我不確定我是否正確理解了目標狀態的問題。但是，我將部分路徑添加到隊列的方式如下所示：如果路徑的長度爲< N-1，則返回任何訪問的節點都是非法的。當長度= N-1時，唯一的選擇是返回到起始節點。您可以將visitedSet添加到您的Path類（作爲HashSet），以便您可以有效地檢查給定節點是否已訪問過。

我希望這可以幫助...