DFS、BFS、および A* 検索アルゴリズムに開いた迷路または閉じた迷路を使用した場合の結果の変化を知りたいですか? 拡張ノード数の増加、コストなど、出力に大きな違いはありますか?
3165 次
3 に答える
2
単純な DFS は、特定の開いた迷路では無限ループに入る可能性がありますが、閉じた迷路では常に終了します。BFS や A* がその罠に陥るとは思えません。（「素朴なDFS」とは、ノードが通過するときにノードを「訪問済み」としてマークしないことを意味します。）編集：ダニエルのコメントにより、私が行く前の眠い瞬間ではなく、日中にこの答えを再考することを余儀なくされました。ベッド。A* は、その基本的な機能の一部としてアクセス済みとしてノードをマークすることを認めます。ただし、BFS は、ノードをマークしなくても、開かれた迷路でも解決できると思います。効率的ではありませんが、迷路に解決策があれば、BFS が見つけてくれます。定義上、次の深さに移動する前に、特定の深さですべての可能なパスを試行します。したがって、長さ 10 の解が存在する場合、BFS は深さ 11 の解を試す前にそれを見つけます。
于 2010-07-23T04:59:13.390 に答える
1
はい。さまざまな戦略がまったく異なる順序で迷路を通過するため、大きな違いがあります
于 2010-07-23T04:59:34.023 に答える
0
A* は、単純な dfs および bfs と比較して非常に効率的です。ただし、現在の位置からターゲットまでのコストを評価するための適切な関数を見つける必要があります。
于 2010-07-23T14:41:00.890 に答える