performance - バックトラッキングと分枝限定法を使用する利点

Question

DPは、TSPのような多くのNP完全問題に対してより良いパフォーマンスを提供することを理解しています。必要なスペースは大きいですが、複雑さを大幅に軽減します。

しかし、ブルートフォース検索と比較して、分枝限定法とバックトラックの効率を理解できませんでした。

最悪の場合、ブルートフォースがb＆bに等しいか、バックトラックに等しいか。

Answer 1

徹底的な検索では、すべてのNを計算します。ノード間の可能なルート。バックトラッキングを使用すると、ノードの半分を訪問するルートを計算し、これまでに見つかった最良のルートよりもすでに高価であることに気付き、その時点でその部分的なルートの調査を停止できます。そうすることで、その部分的なルートを完了することによって生成されるすべてのルートの計算をスキップし、すべてをチェックし続けていたであろう徹底的な検索にかかる時間を節約できます。