私は人工知能から引用します: A Modern Approach :
深さ優先探索の特性は、グラフ探索とツリー探索のどちらを使用するかによって大きく異なります。繰り返される状態と冗長なパスを回避するグラフ検索バージョンは、最終的にすべてのノードを展開するため、有限状態空間で完全です。一方、ツリー検索バージョンは完全ではありません[...]。深さ優先ツリー検索は、ルートから現在のノードへのパス上の状態に対して新しい状態をチェックするように、追加のメモリ コストなしで変更できます。これにより、有限状態空間での無限ループは回避されますが、冗長パスの増殖は回避されません。
ツリーが特定のグラフであるため、グラフ検索が完了し、ツリー検索が完了しない方法がわかりません。
その上、「無限ループ」と「冗長パス」の違いがはっきりとわかりません...
誰かが私にこれを説明してもらえますか?
ps。本をお持ちの方は86ページ（第3版）です。
深さ優先のツリー検索は、無限ループに陥る可能性があるため、「完全」ではありません。グラフ検索は、すでに検索したノードを追跡するため、次の無限ループを回避できます。
「冗長パス」とは、同じ開始ノードから同じ終了ノードにつながる異なるパスです。グラフ検索は、これらの冗長なパスをすべて探索しますが、以前に訪れたノードに到達すると、それ以上先には進みませんが、バックアップして、まだ試していないパスを探します。
これは、ノードからノード自体に戻るパスである「無限ループ」とは異なります。
あなたのコメントに応えて、投稿したばかりの引用を見てください。
Depth-first tree search can be modified at no extra memory cost so that it checks new states against those on the path from the root to the current node.
したがって、深さ優先ツリー検索はルートから現在のノードまでのパスを追跡しますが、無限ループを回避するために、新しいノードにアクセスするたびにそのパスを線形検索する必要があります。そのチェックを行わない深さ優先ツリー検索の実装を作成した場合、無限ループに陥る可能性があります。
そうです、「冗長なパスの増殖」について本が述べたことは、完全性とは関係ありません。グラフ検索とツリー検索の違いを指摘しているだけです。ツリー検索は現在のパスを追跡するだけなので、同じ検索で同じパスを複数回実行できます (前述のチェックを行ったとしても)。
ルート ノードに 2 つのブランチがあるとします。これらの分岐のそれぞれは、そこから続く長いパスを持つ同じ単一のノードにつながります。ツリー検索は、それにつながる 2 つの分岐のそれぞれについて 1回、その長いパスを 2 回たどります。それが著者の指摘です。