通過使用DFS，BFS，A *

解決迷宮我想知道當我們對DFS，BFS和A *搜索算法使用開放式迷宮或閉合式迷宮時結果的變化嗎？在擴展節點數量，成本等方面增加的產出是否有很大差異？通過使用DFS，BFS，A *

2010-07-23 Shilpa

這與python有什麼關係？ – 2010-07-23 06:05:30

一個幼稚的DFS可以在某些開放的迷宮中進入無限循環，而在封閉的迷宮中它總是會結束。我不認爲BFS或A *可以陷入這個陷阱。（通過「天真的DFS」我的意思是不會將節點標記爲「已訪問」，因爲它穿越它們。）編輯：Daniel的評論迫使我重新考慮這個答案，而不是在我去之前的那一天睡覺。我會承認A *將節點標記爲其基本功能的一部分。不過，我仍然認爲BFS甚至可以解決打開迷宮而無需標記節點。它不會有效，但如果有解決方案的迷宮，BFS會找到它。根據定義，它將在進入下一個深度之前嘗試所有可能的路徑。因此，如果長度爲10的解決方案存在，BFS將在嘗試任何深度爲11的解決方案之前找到該解決方案。

來源

2010-07-23 04:59:13

BFS和A *還必須將節點標記爲已訪問才能正常工作。 – 2010-07-23 06:04:54

是的。不同的策略以完全不同的順序遍歷迷宮有很大的區別

來源

2010-07-23 04:59:34

我認爲這個問題是開放式迷宮vs封閉式迷宮，而不是A *與DFS/BFS相比。 – 2010-07-23 16:46:28

與樸素dfs和bfs相比，A *可以非常有效。但是，您需要找到一個很好的功能來評估從當前位置到目標的成本。

來源

2010-07-23 14:41:00 Rambo

我認爲問題是開放式迷宮vs封閉式迷宮，而不是A *與DFS/BFS相比。 – 2010-07-23 16:45:23

通過使用DFS，BFS，A *

回答

相關問題