最短路徑 - 廣度優先搜索

我有一篇文章的任務，絕不是要求任何代碼幫助，只是幫助理解如何解決此問題。最短路徑 - 廣度優先搜索

我們在哪裏給了最小的工作材料，而教授只瀏覽了廣度優先搜索的內容。

我們需要通過迷宮找到我們的方式，迷宮被創造出來，並且你的人每次都會落在一個隨機空間中。

當鍵被按下時，當前位置被髮送到該功能，並且從那裏我們必須使用廣度優先搜索來找到最短路徑。

現在我從這個搜索算法理解如下：

樹或圖形必須在各級搜索
我們需要的路徑存儲在a queue（FIFO）
然後找到最終路徑中的最短路徑

我到底該如何處理這類問題？

我們知道開始和結束，再加上我們可以很容易地獲得當前塊的所有相鄰塊。

非常感謝。

來源

2015-10-19 Tiaan Swart

如果您不是在尋求代碼幫助，那麼您來到了錯誤的網站。 – dursk

嗨@dursk感謝您的貢獻，但我相信在這裏提出這個問題可以。 –

那麼，你應該至少移除python標誌。 – dursk

你似乎錯過了廣度優先搜索的一些細微差別。

樹或圖形必須水平

這是正確的搜索。雖然你不一定會追蹤一組不同的關卡，但你自然會在完成後繼續下一個關卡。

我們需要的路徑存儲在隊列（FIFO）

不是真的。通常存儲未來的節點以便在隊列中進行探索，而不是整個路徑。如果需要維護路徑是一個額外的問題。

然後找出所有路徑的最短路徑到端項

在具有均勻的邊權的曲線圖，這是不必要的。你找到的第一條路徑是最短的。（請注意均勻邊權的要求，這是對BFS真）

的BFS的目標節點的通用代碼是類似如下：

q := new Queue 
q.enqueue(start) 
goal_found := false 
while(q is not empty) 
    n := q.dequeue() 
    if n is goal then 
     goal_found := true 
     break 
    for each neighbour v of n 
     q.enqueue(v) 

if(goal_found) 
    //do something (success) 
else 
    //do something else (failure)

還有更多一點如果你想跟蹤你遍歷的路徑，加入到這個框架中，防止你的路徑翻倍（在一個無向圖中這對於確保終止非常重要），防止重複處理一般節點（如果有周期和你想要終止），跟蹤長度等。但這是它的基本框架。

來源

2015-10-19 05:58:40 moreON

這使得更多的意義謝謝！ –

最短路徑 - 廣度優先搜索

回答

相關問題