我們給出N×N雷區(二維數組),在另一個M×2陣列中給出地雷的座標。尋找從左上角到右下角的最短路徑的最佳算法是什麼?有障礙物的最短路徑
3
A
回答
2
這是一個shortest path problem,並且可以通過減少問題的graph解決:
G=(V,E)
V = { (x,y) | for all x,y such that (x,y) is not a mine }
E = { ((x1,y1),(x2,y2)) | (x1,y1) is adjacent to (x2,y2) }
現在,當你有圖表,你需要應用一些最短路徑算法。
- 最簡單的將是BFS(因爲你的圖是未加權的)。這個 實現起來相當簡單,並且如果存在 ,它總是找到最快的路徑。
- 更復雜一點的方法是bi-directional BFS。在這裏,你從開始節點(0,0)和結束節點(n,n)做一個BFS - 並在算法的兩個前端找到對方時結束。路徑是通過將第一個與第二個的相反連接而給出的。這種方法可能比常規BFS更快,但編程起來有點困難。
- 您可以使用知情算法,如A* search algrotihm,曼哈頓距離作爲啓發函數(假設您只能上/下/右/左,沒有對角線)。這可能會比兩種選擇都快,但編碼更難。
我就從BFS,如果你有它的經驗開始,後來轉移到更先進的algroithms。
在僞碼:
BFS(x_source,y_source, x_target,y_target):
queue = empty new queue
queue.add(Pair(x_source,y_source))
parent= new dictionary
parent.add(source, None)
while (queue.empty() == false):
curr = queue.dequeue()
currX = curr.first
currY = curr.second
if (currX == x_target && currY == y_target)
return getPath(dict, curr)
for each neighbor u of curr: //u is a pair of (x,y) coordinates of adjacent cell
if u is not a key in parent:
parent[u] = curr
queue.add(u)
上面BFS填充parent
字典,並且該路徑是由以下的getPath()函數,該函數基本上橫穿字典,直到找到「根」返回(其是原始的源節點)。
getPath(dict, target):
sol = [] //empty list
curr = target
while curr != None:
sol.addFirst(curr)
curr = dict.get(curr)
1
這個問題可以用Dijkstra算法來解決。 首先刪除所有到達節點的傳入路徑,然後以最短路徑前往右下角節點。
+0
Dijkstra的算法在這裏是一種矯枉過正的情況,因爲圖形沒有加權。 BFS實施起來比較困難,效率也比BFS低,這在這裏也是最優的。 – amit 2015-03-25 16:10:35
+0
是的,如果圖未加權。感謝您指出。 :) – 2015-03-25 16:26:07
相關問題
- 1. Java 2D陣列從A點到障礙物的最短路徑
- 2. 算法找到最短路徑,障礙物
- 3. 矩陣中的最短路徑與作弊路徑的障礙
- 4. 最低成本路徑障礙(R)(gdistance)
- 5. 人工智能搜索問題:飛機上有障礙物的兩點之間的最短路徑
- 6. 2D遊戲的障礙路徑檢測
- 7. 使帶障礙物和空間限制的總路徑成本最小化
- 8. GKObstacleGraph在障礙物引入時未找到路徑
- 9. DFS路徑查找與障礙
- 10. 查找具有障礙物的連續大地圖上的路徑
- 11. 在A *遍歷後移除產生最佳路徑的障礙
- 12. 最短路徑
- 13. 最短路徑
- 14. 網格障礙物變形
- 15. 計算從開始到結束的最短路徑,如果我們有能力克服MOST 1的障礙
- 16. 路徑尋找在一個簡單的網格,沒有障礙
- 17. 用障礙物計算網格中的路徑和我的分析
- 18. 圖最短路徑?
- 19. DAG最短路徑
- 20. 最短路徑C#
- 21. 半徑搜索中的地理障礙物
- 22. 有多少線路通過障礙
- 23. 地圖探索/路徑規劃多個機器人(無障礙物)
- 24. 所有使用graph_tool的最短路徑
- 25. 有向無環圖的最短路徑
- 26. 找到有向圖的最短路徑
- 27. 旅行的最短路徑
- 28. Prolog:Knight的最短路徑
- 29. Dijkstra的最短路徑,HackerRank
- 30. JavaScript中的最短路徑
歡迎來到本網站!有一件事要記住:你應該總是先告訴我們你的算法,並指出那些不工作的部分,以期在這裏獲得幫助。 – ZygD 2015-03-25 03:52:13
這是功課嗎?應該這樣寫/標籤。我會在這裏使用'A *'看看http://stackoverflow.com/q/23705233/2521214如果你想要最好的算法,那麼你應該根據哪些方面/條件(性能,空間/時間複雜度,行數, ...) – Spektre 2015-03-25 06:36:22
你是什麼意思「最佳算法」?最快,最少的代碼,最易維護,最容易理解的? – 2015-03-25 08:23:09