バックトラッキングでは、BFS と DFS の両方を使用します。分岐限定法でも、最小コスト検索に加えて、BFS と DFS の両方を使用します。
では、バックトラッキングはいつ使うのでしょうか？分岐限定法はいつ使うのでしょうか？
分岐限定法を使用すると時間の計算量は減りますか?
分枝限定法における最小コスト探索とは何ですか?
ベストアンサー1
バックトラッキング
- 問題に対して利用可能なすべての解決策を見つけるために使用されます。
- 状態空間ツリーを走査し、ドフス(深さ優先探索)方式。
- 誤った選択を行ったことに気づき、バックアップして最後の選択を元に戻します。
- 解決策が見つかるまで状態空間ツリーを検索します。
- それは実現可能性関数。
分岐限定法
- 最適化問題を解決するために使用されます。
- どのような方法でも木を横断できる。DFS または BFS。
- 事前ソリューションによって導かれるより優れた最適ソリューションがすでに存在することを認識し、その事前ソリューションを放棄します。
- 状態空間ツリーを完全に検索して最適なソリューションを取得します。
- それは境界関数。