局遊戲尋路 - 找到多個最優路徑

我有一個很簡單的任務爲尋路棋盤遊戲上的8×8網格播放，每個正方形要麼是可通過與否。我正在尋找的是一個算法，它會給我從最佳的n個路徑從一些平方A到B（假設有）。局遊戲尋路 - 找到多個最優路徑

我一直在看A *，但據我所看到的，是把它擴大到找到多個路徑沒有明確的辦法。

那麼，什麼是關鍵的是它給人的路徑實際上是最短的N條路徑，它不會錯過任何。效率也非常重要。任何人都可以提出一個合適的算法，或者指向正確的方向嗎？

來源

2011-06-05 Stereotomy

鑑於板廣度優先窮舉搜索的小尺寸是你應該考慮的東西。 8 x 8表示只有64個方格，x8移動（如果不允許對角線，則爲4個），總搜索量非常小。

來源

2011-06-05 03:41:56

對角線是不允許的，所以每平方只有4個棋步。尋路將會重複很多次，所以儘可能地提高效率非常重要 – Stereotomy 2011-06-05 04:35:48

Dijkstra的是像這些大多數情況下，一個好的算法，但由於您使用的是8x8的網格，我將承擔所有的每個單元之間的距離都等於和靜態。在這種情況下，BFS（廣度優先搜索）應該很適合你。

來源

2011-06-05 03:45:01 mmmeff

退房k-shortest paths，一個開源實現，也包括一些參考。

來源

2011-06-05 03:46:40 Nemo

Dijkstra的工作很好找到單一的最短路徑。要找到第二，第三，第n條最短路徑，您需要使用Dijksta算法的擴展。一旦找到N1，N2，N3 ... Nx的最短路徑，請克隆該路徑上的所有中間節點以創建節點N2'至Nx-1'。克隆最短路徑上的所有進入邊，除了（N1，N2'）和刪除邊（Nx-1，Nx）。將所有邊緣放到克隆路徑上的節點上，該路徑現在代表從前一次迭代獲得最短路徑上節點的第二快速方式。

來源

2011-06-05 03:52:31 btreat

對不起，我不太習慣於處理圖形。你能否通過「克隆所有進入的邊緣」來準確解釋你的意思？所以，舉個例子，假設你正在查看Ni，它有邊Ni + 1，Ni-1和兩個不在路徑上的節點A和B. Ni的相應邊是什麼？我也不確定什麼「將所有邊緣放到克隆路徑上的節點上」的意思。 – Stereotomy 2011-06-05 04:49:32

當然。假設Dijkstra算法的第一次迭代發現了最短路徑N1，N2，N3 ... Nx，其中N1是起始節點，Nx是精整節點。首先克隆節點N2以創建N2'。您還可以克隆N2的任何進入邊，以便對於原始圖中的每個邊（？，N2），現在在修改後的圖中有一個邊（？，N2'）。一個例外是你不克隆邊緣（N1，N2）來創建（N1，N2'）。繼續下一個評論... – btreat 2011-06-05 14:12:54

現在你放鬆所有的邊緣進入N2'。在Dijkstra算法的情況下，放鬆邊緣意味着如果到尾部的距離加上邊緣的成本小於到頭部的現有距離，則更新到頭部的距離（最短已知路徑）。此時，從N1到N2'的最短路徑表示從N1到N2的第二短路徑。現在，爲其他中間節點N3 ... Nx-1重複該過程以創建節點N3'... Nx-1'。在每一步中，克隆除原始最短路徑（例如create（N2'，N3'）而不是（N2，N3'）之外的所有進入邊） – btreat 2011-06-05 14:22:03

局遊戲尋路 - 找到多個最優路徑

回答

相關問題