問題タブ [depth-first-search]

私はしばらくの間、バイナリ ツリーを装ったこのグラフを動作させようと試みてきました。現在、ルート ノードと探しているノードの ID を渡す関数を使用しています。唯一の問題は、コーディング方法によっては、一方の側が 3 ノードを超えることができないことです。私は再帰を正しく行っていないと確信しています。私はこれに一晩中立ち往生しており、これを取得できません。他のグラフやツリーを調べてみましたが、役に立ちませんでした。実際の頂点やその他のグラフのようなプロパティは使用if (x <root.getID())していませんが、root.left をそのまま使用することはできません。

これは、いくつかのノードを長くすると、右側で機能しなくなる私の非機能検索アルゴリズムです。Visited は HashSet() クラスを使用しています。

すべてのツリーを印刷するための作業コードがありますが、上記のコードのキー比較のためにコードを変更することはできません。

助けてくれてありがとう。

編集：私がやっていることを拡張すると思います。新しいノードを配置する関数 makeRight または makeLeft が必要です。その後、既存のノードがその左または右の子を配置します。これがそれです。その検索には、プライベート dfs を呼び出すパブリック メソッドがあります。

lc と rc の if ステートメントの再帰関数をどのように並べるかによって、ツリーの別の側が基本ケースに再帰されます。これが、dfs メソッドが間違っていると思い込ませる理由です。要求されたノード クラスは次のとおりです。

}

ここまで書いてきました。

Russel-Norvig で説明されているアルゴリズムを使用しています。パス全体を作成する方法がわかりません。ここで何かが欠けています。私にとって、ラッセル・ノーヴィグはそれについて本当に不可解です。

こんにちは、迷路を生成するプログラムを作成しているので、後でパスをグラフィカル パーツに変換できます。私はそれのほとんどを機能させていますが、東と南のルートをたどることができれば、最後まで行くことができます. 幅を 64 に設定しても、迷路は 64*64 になりますが、これら 2 つのオプションを選択して、毎回最後まで到達することができます。なぜそれがそうしているのか、私には本当にわかりません。コードは以下のとおりです。かなり理解しやすいです。

ご覧のとおり、問題は迷路を生成するポイントにあると思いますが、現在のポイントが最後になるまでそのままにしておくと、すべての迷路がいっぱいになるわけではなく、通常は 1 つの直線的なパスになります。 . 助けてくれてありがとう。

更新: 迷路を生成する for ループを単純な while ループに変更したところ、はるかにうまく機能するようです。for ループが実行されたときは再帰的に実行されなかったようですが、while ループではまったく問題ありません。ただし、すべてのマスが埋まらないようになりました。

800 x 600 の画像があります。行列のように扱い、隣接する要素を取得したい

元。

(0,0) (1,0) (2,0) (3,0)

(0,1) (1,1) (2,1) (3,1)

(0,2) (1,2) (2,2) (3,2)

(0,3) (1,3) (2,3) (3,3)

解の例: (0,0) は (1,0) (0,1) (1,1) に隣接しています。

(1,1) は (0,0) (1,0) (2,0) (2,1) (2,2) (1,2) (0,2) (0,1) に隣接しています。

だから私はこれらのポイントのそれぞれを格納する構造体配列を書きました

私の最初のアイデアは、dfs を実装することでしたが、それは実際にはうまくいきませんでした。そのため、自分自身を正しい軌道に乗せるために外部の意見を得たいと考えました。ありがとう

Pythonで行うことにしたプロジェクトがあります。簡単に言うと、リストのリストがあります。それらのそれぞれにもリストがあり、要素が 1 つだけの場合もあれば、それ以上の場合もあります。次のようになります。

ポイントは、numpy 配列の値をこのルール (ルール テーブルの要素) の値と比較することです。一部の [x][y] ポイントを最初の要素 (たとえば、最初の要素の 1) と比較し、それが真の場合は、配列の値 [x-1][j] をリストの 2 番目と比較します。[x][y] ポイントの値を変更するには、最初の 5 つの比較が真でなければなりません。私はこのようにsthを書きました（メイン関数はSimulateLoopです。simulate2関数は2番目の関数の後に書かれたため、順序が入れ替わっています）：

データクラス:

NumPy 配列は World クラスのオブジェクトです。ルールは上記のリストであり、別のプログラム (GPL ライセンス) から取得した関数によって解析されます。

正直なところ、うまく機能しているように見えますが、そうではありません。私は他の可能性を試していましたが、運が悪かったのです。動作しています。インタプリタはエラーを返しませんが、何らかの形で配列の値が間違って変化しています。パーサーを取得したプログラム (GPL ライセンス) によって提供されたので、ルールは適切です。

多分それは役に立つでしょう - それはペリエのループ、修正されたラングトンのループ (人工生命) です。

どんな助けにも非常に感謝します！)

ユークリッド重みの隣接行列として表される無向グラフがあります。これを使用して、より大きな完全なグラフの最小スパニング ツリーを表します。

私が見つけたいのは、グラフ内の単一のノードであり、ルート ノードとして使用すると、可能な限り短いツリーの高さを作成します。私が思いついたのは、すべてのノードをルートとして使用して深さ優先のトラバーサルを実行し、見られる最短の高さを追跡することです。これを達成するためのより速い方法はありますか？

I have conflicting information about depth first traversal and could use some help in understanding how to build a program. Given a certain graph, I want to print a sequence of vertices. The user will input a particular node to start the traversal from. I am looking at different examples and I don't understand how the order of the depth-first traversal works. I have the following pseudocode to work with:

ということで、ボグルゲームのプログラムを書いています。ユーザーが使用する小さなボードを作成しますが、問題は、その単語がボード上にあるかどうかを再帰的に確認する方法がわからないことです。入力した単語が実際にボード上にあり、有効かどうかを確認できるようにしたい。つまり、単語の文字は互いに隣接している必要があります。ボーグルをプレイしたことのある人なら、私の言いたいことがわかるでしょう。私がやりたいのは、単語がボード上にあるかどうかを確認することだけです。

これは私がこれまでに持っているものです....

検索は、単語がボード上にあるかどうかを確認するための検索アルゴリズムでしたが、それが正しいかどうか、または機能するかどうかはわかりません。さらに、単語が有効であることを実際にユーザーに伝える方法がわかりません!

すべての助けをありがとう:)

だから私はあなたが以下に提案したものを使用しようとしましたが、int [5] [5] のことを本当に理解していません。これは私が試したものですが、範囲外のエラーが発生し続けています! ここにソースがあります...

プライベート int カウント = 0; (どこから [count] という単語を取得したか疑問に思っている場合に備えて、クラスの先頭で宣言されました

重み付けされていないグラフといくつかの質問/懸念事項の隣接リストを実装しようとしています。エッジを格納するためのリンク リストと、頂点を格納するための配列が必要であることに気付きました。現在、(基本)Node クラスと、特定の頂点へのエッジの追加を処理する Graph クラスがあります。ただし、これはエッジの連結リストを明示的に定義しません。DFS と BFS を実行したいのですが、どうすればよいでしょうか? これらのメソッドを組み込むために既に必要なコードを変更する必要がありますか、それとも今ですか。助けていただければ幸いです。

説明付きのコード例を探しています。ウィキペディアはこれについて抽象的すぎます。