深度優先搜索找到最短路徑？

我知道這通常是用做廣度第一，但我們被要求既要做到這一點，我已經完成廣度優先....深度優先搜索找到最短路徑？

我覺得這是一個使用深度優先搜索的一個非常典型的例子，所以我希望能夠在這裏得到一些幫助......我試圖通過使用深度優先搜索來找到通過迷宮的最短路徑，但截至目前我無法圍繞着如何完成它。這是到目前爲止我的代碼：

void maze::findPathRecursive(graph &g, int position, int goal) { 
    if (position == goal) { 
     isPath = true; //returns true if there is a path to the goal 
     correctPath.push_back(position); // the path to the goal 
    } else { 
     g.mark(position); 
     g.visit(position); 

     //gets all the neighbors of the current position 
     vector<int> neighbors = getNeighbors(position, g); 

     while (!neighbors.empty()) { 
      int n = neighbors.back(); 
      neighbors.pop_back(); 

      if (!g.isVisited(n)) { 
       findPathRecursive(g, n, goal); 
      } 

      if (isPath) { 
       correctPath.push_back(position); 
       break; 
      } 
     } 
    } 
}

眼下，這是什麼做的是找到從那裏的目標和休息的第一路徑就可以了。我知道我需要擺脫休息時間，並試圖製作另一個矢量來存儲最短路徑，並比較它和之前最短的路徑之間的長度，但它不起作用，因爲我覺得我需要在某個點但無法弄清楚在這裏如何做到這一點。

任何幫助非常感謝！

g是一個包含迷宮的圖形。

來源

2014-03-28 seanscal

你能確認你的圖是否是非循環的嗎？ – nobillygreen

@nobillygreen現在它的工作方式是，即使它確實做了一個大圓圈，第一個節點將被標記爲已訪問並且將不能被再次訪問，所以在某種意義上，它是 – seanscal

DFS shortest path of a maze in C++檢查幫助這裏提供的，不知道爲什麼，這個問題越來越多的關注比我的其他回答一個

來源

2015-10-19 19:17:10 seanscal

一般而言，您不想使用DFS查找最短路徑（除非您的圖形是明確非循環的，也是無向的，在這種情況下，您的目標只有一條路徑開始）。可能的是，但它變得非常人造。在最簡單的層面上，DFS更擅長確定是否有路徑，然後確定最佳路徑。

我建議看看不同的廣度優先搜索（BFS）算法。如果你的迷宮在網格上，A *可能是你最好的選擇。

來源

2014-03-28 14:44:59 nobillygreen

這是爲了一個任務我們必須做到這一點，我首先理解寬度，但深度首先似乎讓我絆倒 – seanscal

我不知道我完全理解這個問題，但通常情況下，您不會使用廣度優先搜索（至少在最簡單的情況下）？在我看來，任何試圖找到最短路徑的DFS都必須變成某種BFS，因爲DFS可能會「錯過」快捷方式。

也許這https://cs.stackexchange.com/questions/4914/why-cant-dfs-be-used-to-find-shortest-paths-in-unweighted-graphs和這個http://en.wikipedia.org/wiki/Shortest_path_problem幫助。

來源

2014-03-28 14:47:31 godfatherofpolka

儘管使用DFS可以找到一條路徑（如果您運氣最短的話），但它並不能保證一般的最短路徑。 BFS是你最好的選擇。

然而有一種方法叫做Iterative Deepening。維基百科：

迭代深入深度優先搜索1（IDDFS）是其中深度限制搜索被重複運行狀態空間搜索策略，隨着每次迭代增加深度限制，直到它到達d ，深度最淺的目標狀態。 IDDFS相當於廣度優先搜索，但使用的內存少得多;在每次迭代中，按照與深度優先搜索相同的順序訪問搜索樹中的節點，但首次訪問節點的累積順序實際上是寬度優先的。

僞代碼，再次從維基百科：

> IDDFS(root, goal) { 
> depth = 0 
> for(i=1, i<10, i++) { 
>  DFS(limit=i) 
> } 
> }

首先實現DFS（應該是完全一樣BFS，但使用一個堆棧，而不是一個隊列），然後執行算法ID。希望這有助於。

來源

2014-03-31 05:23:44 pushkin

，而不是「unvisit」的節點，我想你需要與每個節點有多少邊緣存儲它去了那裏。如果通過較短的路徑再次到達那裏，則會更新該節點以及從該節點到目標的最佳路徑上的所有節點的邊數。

來源

2016-05-03 16:41:52 Bob

不知道你是如何找到這個問題來回答它，但檢查我給出的答案，指出一個單獨的問題的鏈接回答這個問題 – seanscal

深度優先搜索找到最短路徑？

回答

相關問題