depth-first-search - 「バックトラッキング」と「ブランチ アンド バウンド」の違い

Question

バックトラッキングでは、bfs と dfs の両方を使用します。分岐限定でも、最小コスト検索に加えて bfs と dfs の両方を使用します。

では、いつバックトラッキングを使用し、いつブランチ アンド バウンドを使用するのですか?

分岐限定を使用すると、時間の複雑さが軽減されますか?

分枝限定法における最小コスト探索とは?

Answer 1

バックトラッキング

1. 問題に対して利用可能なすべての解決策を見つけるために使用されます。
2. DFS (Depth First Search) 方式で状態空間ツリーをトラバースします。
3. 間違った選択をしたことに気づき、後退することで最後の選択を取り消します。
4. 解が見つかるまで状態空間ツリーを検索します。
5. これには実行可能関数が含まれます。

分岐限定

1. これは、最適化問題を解くために使用されます。
2. DFS または BFSのいずれかの方法でツリーをトラバースできます。
3. 事前解が導くより良い最適解が既にあることに気づき、その事前解を放棄します。
4. 状態空間ツリーを完全に検索して、最適解を取得します。
5. これには境界関数が含まれます。