BFS算法 - 在約束步驟的網格上最短步行

問題如下：流浪者開始在網格座標（x，y）上並希望到達座標（0,0）。從每個網格點，流浪者可以向北8步或向南3步或向東5步或向西6步（8N/3S/5E/6W）。BFS算法 - 在約束步驟的網格上最短步行

如何使用廣度優先搜索找到從（X，Y）到（0,0）的最短路徑？

澄清：

無限網格
負座標被允許
隊列（鏈表或陣列）必須用於
本

來源

2010-11-21 Gorkamorka

對不起，但我沒有找到任何解釋你的問題... – 2010-11-21 12:33:41

任何障礙出現在網格？網格的尺寸是多少？ – bjskishore123 2010-11-21 12:34:26

你爲什麼不考慮（8N/3S/5E/6W）。我的意思是爲什麼只推一次北/南/東/西。這不會改變BFS的答案嗎？請解釋... – 2011-01-04 22:52:11

-2

我要繼續前進，回答自己以供將來參考的問題。

僞代碼：

while (true) { 
    if (destination reached) 
     break; 
    addToQueue(go north); 
    addToQueue(go south); 
    addToQueue(go east); 
    addToQueue(go west); 
    getNextFromQueue; 
}

還應當指出的是，執行時間爲這個應用程序的增長非常快，所以用小的座標值測試它。例如，座標（1,1）給出7個水平的寬度並且需要16384次迭代。

來源

2010-11-27 19:12:17 Gorkamorka

你確定這可以嗎？如果你總是按順序添加到隊列N，S，E，W，那麼你就會有偏見。每四步完成一次，最終向北移動5個單位，向西移動1個單位。如果你的出發點恰好在（0,0）的北部和西部，你將會離開它。 – miked 2011-01-04 23:03:39

的算法沒有障礙這個問題將是：

對於每個軸，朝它步驟，直到你對其他的軸位置爲0

僞代碼：

while (x!=0) { 
    if (x>0) x-=6; 
    else x+=5; 
} 
while (y!=0) { 
    if (y>0) y-=8; 
    else y+=3; 
}

不過，我不明白爲什麼你需要搜索的路線 - 這並不是說複雜。

來源

2010-11-21 12:37:42 thejh

是的，沒有隊列需要。愚蠢的家庭作業問題。 – miked 2011-01-04 23:00:42

由於「thejh」表示不需要搜索，但您的任務需要一個。

一種合理的方法是

分析。對於任意（x，y）起始位置是否全部爲？檢查允許的移動，你可以看到它們可以組合產生1步的水平移動和1步的垂直移動，所以答案是肯定的（爲你的介入提供了這個細節）。
找出「廣度優先搜索」是什麼。維基百科是你的朋友（儘管如果你有機會去大學圖書館，我確實推薦帕特里克·亨利·溫斯頓的舊版人工智能，它非常好，非常清晰的解釋）。嘗試一下更簡單的問題。
以幾乎相同的方式完成作業的問題。如果遇到任何技術上的C++問題，請到這裏詢問。

乾杯&心連心，

來源

2010-11-21 12:47:42

關注點2：這幾乎是我發佈的原因:)我一直在四處尋找BFS搜索的解釋和代碼示例，但是當我找不到任何可以掌握的東西時，我發佈了這個問題，因爲我明白了它提出的問題以及如何使用DFS（深度優先搜索）而不是BFS來實現和解決此問題。 – Gorkamorka 2010-11-21 13:03:47

這裏是我的答案（其實是建立關閉thejh的回答），其使用隊列：

//set x to start position 
//set y to start position 
do { 
    if (x<0) Queue.Push(8N); 
    if (x>0) Queue.Push(3S); 
    if (y<0) Queue.Push(5E); 
    if (y>0) Queue.Push(6W); 
    while (!Queue.Empty()) 
    { 
    Move(Queue.Pop()); 
    } 
} while (x && y);

這是令人費解的，但遵循的方向。

來源

2011-01-05 00:02:13 miked

BFS算法 - 在約束步驟的網格上最短步行

回答

相關問題