は状態空間ツリー

Question

内の重複状態を確認し、私は参考のためにこの質問を読んでされています：コメンターの Graph Search vs Tree Search

一つ、私が直面しています正確な状況でこのコメントをしました。

"検索ツリー内のすべてのノードが状態空間グラフに沿った単一のパスに対応しているため、単一の状態はツリー検索で複数回訪問することができます。木探索で最大1回訪問した。

私の検索アルゴリズムは、すでに検索ツリーにあるものと同一のノードを生成しています。この新しく生成された状態が既に存在していることを検出する最良の方法は何ですか、私は無限ループに入ることを避けることができますか？ 私は閉鎖リストを使用することができず、DFSのサイクル検出を行う必要があります。これを行う最善の方法は何ですか？これは私が練習のためにやっているAIコースの課題の質問からです。それは提出のためではありません。私は好奇心の外にエージェントを建てています。どんな助けがありがたいですか

Answer 1

私は完全性のために私自身の質問への回答を投稿したいと思います。私は各ノードの訪問ビットを設定して終了しました。私はルートから下のパスに触れました。訪問されたフラグが設定されているノードを訪れた場合、通常の方法でサイクルがあると結論づけます。

私は基本的に、これらの頂点の間にある「頂点」と「エッジ」と呼ばれるオブジェクトの束を持っていました。そして、もう一方の端でエッジをトラバースすると、頂点がありました。コードにサイクルがあることを知っている。他のリンクで述べたように、各ノードは基本的に異なる状態オブジェクトを持つ新しいオブジェクトですが、状態オブジェクトは基本的にエージェントが以前にあった場所を表しており、この重複ノードの生成を避けたいとします。