問題タブ [depth-first-search]

深さ優先検索を実行して、ツリーを反復処理するこのコードがあります。すべての要素が 1 回だけ処理されます。とても良い。

BUT: グラフの現在の深さを追跡するにはどうすればよいですか? 深さのレベルを知る必要があります。たとえば、次のノードがあります。

A には子 B、J がいます。B には子 C があります。C には子 D があります。D には子 E、F、I があります。

A が深さレベル 1 の場合、B は 2、C は 3 です。

再帰を使用すると、現在の深度レベルを追跡するのが非常に簡単になりました。自分自身を呼び出す前に変数をインクリメントし、自分自身を呼び出した後にデクリメントします。

しかし、ここでは、この空想的な while ループを使用することはできません。再帰のようにボックス内のボックス内にボックスはありません。

プロパティ (またはインスタンス変数) を TreeNode オブジェクトに追加する必要はありません。これは、あらゆる種類のオブジェクト グラフに対して一般的な方法で再利用できるはずだからです。

これを行う方法を知っている人はいますか？訪問したノードを追跡するために別の配列を導入する必要がありますか?

英語を母国語としない人 (ロシア) として、ウィキペディアでこの記事を読みました: http://en.wikibooks.org/wiki/Artificial_Intelligence/Search/Heuristic_search/Depth-first_search

そして、私はハードコアな英語で書かれたこの疑似コードの例に従い、説明やコメントをほとんど付けないようにしています。

特に、私は彼らがこの文で何を言おうとしているのか理解できません:

u に隣接するすべてのノード v に対して

この文の私の問題は、「隣接」部分です。私の辞書によると、これは「隣人」のようなものを意味します。では、u のスーパーノードのサブノードを反復処理する必要がありますか? u はグラフのノードであることに注意してください。

それとも、u のすべてのサブノードを反復処理しなければならないと言いたいのでしょうか? これは大きな違いになるからです。

これらの英語の問題に加えて、彼らはdとpが何を意味するのかを言及するのを忘れていました。

記事内のリンクは、このあまり意味のない不可解なことを繰り返しているだけです。たぶん、誰かが実際にこれを、より多くのコメントと意味のある変数を使って、より人間が読める方法で書き直すことができたでしょうか? DFSに関連するライターの支配的な知性を誇示するためだけにあるのではない、本当に良い説明は見つかりませんでした.

したがって、誰かがその場でそれをより良い方法で書き直し、学習価値を高めて私の一日を救うことができれば、私の口ひげを救います. すべてを保存します。ありがとうございました。

ノードからその隣接ノードへの訪問をランダム化するのに問題があります。グラフ全体（このテストでは4x4のMxN配列）が訪問されることはめったにありません。ここで間違っていることがわかりません。

このコードは私に次のような出力を与えています：

次の移動の位置を検証していますが（ブール値southValid、eastValidなどを介して）

Java での DFS 迷路の生成では、DFS の再帰呼び出しが行われる順序をランダム化したい:

どうやってやるの？

迷路の生成には深さ優先探索を使用しています。

M*N 個の頂点の隣接行列は、DFS を使用してランダムな順序でトラバースされます。ランダムなルートを生成することにのみ関心があります。

頂点の数を減らしても問題なく動作しますが、それを使用すると StackOverflow Exception が発生します

質問: a) スタックを使用して、この再帰呼び出しを反復呼び出しに変更するにはどうすればよいですか?

b) メソッド呼び出しスタックにより多くのメモリを割り当てる方法はありますか?

後で迷路を生成するために、スタックを介してマトリックスを介したDFS反復検索を実装しています。最初の要素をポップせずに押して行き詰まっています。

完全なコード：

私は試してみました。検索して検索しましたが、私の問題を解決するアルゴリズムを実際に見つけることができませんでした。ツリー内のすべてのパス (単純なパスだけでなく) を列挙したいと思います (ただし、これは簡単な制約です)。

たとえば、ツリーの場合。

次のパスを生成できるようにしたい:

それだけだと思います。

次の解決策を試しました深さ優先検索を使用してすべての単純なパスを見つけることの複雑さ? . ただし、単純なパスしか検索されないため、4-2-5-2-1-3-6 などのパスは検索できませんでした。

あなたが私を導くことができる方法はありますか、おそらくアルゴリズムはありますか?

私はJavaで8ピースのパズルゲームをやっていて、ランダムな状態から始めて、解決策を見つけるためにDFSを実行する割り当てコマンドを実行しています。

私は Node クラスを持っています。各 Node オブジェクトは、int[][] を使用してどの状態であるか、およびその親ノードが何であるかを認識しています。また、移動できる方向 (左、右、上、下) も認識しています。

単一のノード (開始ノード) から始めて、プログラムは可能なすべての子ノードのノードを作成します。空白の正方形がどの方向に移動できるかを確認し、すでに別のノードに属している状態に戻らないことを確認します。上記の例では、開始ノードは次のように展開されます。

これを処理する方法は、最初のノードを探索し、そのすべての子をスタックにプッシュすることです。これは、目標状態に到達するかカットオフに到達するまで各ノードをループ拡張する再帰的な方法で発生します (私が提供する数)永遠にループしないようにしてください)

私のカットオフが高すぎない限り、コードは正常に機能します。

私は何を間違っていますか？

私が見つけることができるすべての継続チュートリアルは、固定長の継続に関するものです（つまり、データ構造には、トラバースされているため、既知の数のアイテムがあります

私は DepthFirstSearch Negamax(http://en.wikipedia.org/wiki/Negamax) を実装しています。コードが機能している間、継続を使用してコードを書き直したいと思います。

私が持っているコードは次のとおりです

ここで、 update は特定の動きでゲームの状態を更新し、 eval はゲームの状態を評価し、インクリメンタル評価のためにインクリメンター (現在は使用されていません) を返し、 isTerminal は位置が終了位置かどうかを評価します。

問題は、不明な数のアクション (残っているすべての list.map 反復) を継続にサインアップする必要があり、実際にこれを行う効率的な方法を思いつかないことです。

これは指数関数的なアルゴリズムなので、明らかにこれを可能な限り効率的に保つようにしています (ただし、これを理解しようとすると頭が痛くなるので、効率的なものよりも答えが必要です)。

ありがとう

ここでなぜUnmark vertex v必要なのですか？そして、なぜvが再び到達できなくなるような行を追加しても安全なのですか？それは再訪につながるのでしょうか？