DFSとバックトラッキングの違いは何ですか

Question

DFSとバックトラッキングアルゴリズムの違いについて混乱しています。 私の意見では、バックトラックは特別なバージョンのDFSです。

Answer 1

バックトラッキングアルゴリズムは、深さ優先順に、ダウンルートから、再帰的に探索木を横断します。各ノードcにおいて、アルゴリズムは、cが有効な解決策に完了できるかどうかをチェックする。 できない場合は、cをルートとするサブツリー全体をスキップして（刈り込み）します。そうでない場合、アルゴリズムはc自体が有効な解決策であるかどうかをチェックし、そうであればそれをユーザに報告する。 cのすべての部分木を再帰的に列挙する。 2つのテストと各ノードの子は、ユーザ指定のプロシージャによって定義されます。 （グラフの場合にルートとして、いくつかの任意のノードを選択する）ルートに

深さ優先探索（DFS）開始とをバックトラックする前までの各分岐に沿ってできるだけ探ります。