0

ツリー構造で幅優先検索と A* を使用する方法は理解していますが、次のグラフが与えられた場合、どのように実装されますか? 言い換えれば、検索はどのようにグラフを横断するのでしょうか? S は開始状態です

グラフはこちら

4

5 に答える 5

3

ツリーで行うのとまったく同じです。円にならないように、どのノードにアクセスしたかを何らかの方法で追跡する必要があります。

于 2009-10-20T20:29:58.517 に答える
2

基本的に、既にアクセスしたノードを追跡する必要があることを除いて、ツリーを扱うのと同じ方法でグラフを扱います。それはBFSにとっては問題ありません。その上で、A* の場合、ノードを再訪したときに、そのノードへのより安価なルートを見つけた場合にどうするかを検討してください。

于 2009-10-20T20:31:06.767 に答える
0

グラフを描画する - 各ノードを再帰的に検索し、アクセスしたノードをダーティとしてマークします。グラフが汚れていない場合にのみ再帰します。

メモリが問題にならない場合は、グラフをコピーし、ノードをマークする代わりに、コピー グラフからノードを削除します。

于 2009-10-20T20:31:13.287 に答える
0

加重グラフです。最短経路を見つけたいですか、それとも単に横断したいですか? トラバースだけしたい場合は、次のとおりです。

1) キューには S しかありません
2) キューに C と A を追加していますが、S から直接 (1 つのエッジで) 到達できるのはそれらだけです。
3) D、G2 - C から
4) B、E - A から
5) G1 - D から (G2 は既にキューに入っています)
6) G2 からの発信エッジがない
7) キューにまだ入っていない B の隣接ノードがない

ノードがキューに追加される順序は次のとおりです: S、C、A、D、G2、B、E、G1

于 2009-10-20T20:32:57.480 に答える
0

これがどれほど役立つかわかりませんが、関数型言語 J でコーディングされた完全なソリューションを次に示します (jsoftware.com から無料で入手できます)。

まず、写真に表示されているグラフの表現から直接作業するのがおそらく最も簡単です。これを、ノード i とノード j の間のリンクの値を表す (i,j) の番号を持つ (# ノード) x (# ノード) テーブルとして表します。また、対角線に沿って、各ノード自体に関連付けられた番号を付けました。

だから、私はこれを次のように入力します - なじみのない表記法についてあまり心配しないでください。結果がどのように見えるかすぐにわかります:

     grph=: <;.1&>TAB,&.><;._2 ] 0 : 0
    A   B   C   D   E   G1  G2  S
A   2   1           8           2
B       1   1   1       4       2
C       3   1               5   
D               1       5   2   
E                   6   9   7   
G1                      0       
G2                          0   
S   2       3                   5
)

そのため、変数「grph」を 9x9 テーブルとして割り当てました。最初の行と最初の列はラベル「A」-「E」、「G1」、「G2」、および「S」です。タブを使用して項目を区切ったので、必要に応じてスプレッドシートにカット アンド ペーストできます。

ここで、テーブルのサイズを確認して表示します。

   $grph
9 9
   grph
+---+--+--+--+--+--+---+---+--+
|   | A| B| C| D| E| G1| G2| S|
+---+--+--+--+--+--+---+---+--+
| A | 2| 1|  |  | 8|   |   | 2|
+---+--+--+--+--+--+---+---+--+
| B |  | 1| 1| 1|  | 4 |   | 2|
+---+--+--+--+--+--+---+---+--+
| C |  | 3| 1|  |  |   | 5 |  |
+---+--+--+--+--+--+---+---+--+
| D |  |  |  | 1|  | 5 | 2 |  |
+---+--+--+--+--+--+---+---+--+
| E |  |  |  |  | 6| 9 | 7 |  |
+---+--+--+--+--+--+---+---+--+
| G1|  |  |  |  |  | 0 |   |  |
+---+--+--+--+--+--+---+---+--+
| G2|  |  |  |  |  |   | 0 |  |
+---+--+--+--+--+--+---+---+--+
| S | 2|  | 3|  |  |   |   | 5|
+---+--+--+--+--+--+---+---+--+

見た目はOKで、これをグラフの写真と比較して確認するのは簡単です。ここで、最初の行と列を削除して、(ボックス化されたリテラルとして) 数字のみが残るようにし、余分なタブ文字を削除します。

   grn=. TAB-.~&.>}.}."1 grph

この結果を変数「grn」に割り当てていることがわかります。

次に、空のセルを無限を表す "_" に置き換え、リテラルを数値表現に変換します (結果を同じ名前 "grn" に再割り当てします)。

   grn=. ".&>(0=#&>grn)}grn,:<'_'

最後に、最後の列と行を先頭に移動します。これは "S" の列であり、最初にあるはずだからです。また、結果を表示して、正しいように見えることを確認します。

   ]grn=. _1|."1]_1|.grn   NB. "S" goes first.
5 2 _ 3 _ _ _ _
2 2 1 _ _ 8 _ _
2 _ 1 1 1 _ 4 _
_ _ 3 1 _ _ _ 5
_ _ _ _ 1 _ 5 2
_ _ _ _ _ 6 9 7
_ _ _ _ _ _ 0 _
_ _ _ _ _ _ _ 0

これで、グラフを表す単純な 8x8 の数字の表ができたので、それを走査するのは簡単なことです。

これは、「traverseGraph」と呼ばれる単純な J 関数で、このテーブルを読み取り、それが表すグラフをトラバースして、2 つの結果を返します。訪問したノードのインデックス (0 ベースの原点) と、訪問した。

traverseGraph=: 3 : 0
   pts=. ,_-.~,ix{y [ nxt=. ix=. ,0
   while. 0~:#nxt=. ~.ix-.~;([:I._~:])&.><"1 nxt{y do.
        ix=. ix,nxt [ pts=. pts,_-.~,nxt{y
   end.
   ix;pts
)

3 つの変数を初期化することから始めます: インデックス "ix" のリスト (テーブルの 0 番目の行から開始したいのでゼロに)、ノードの次のグループを指す変数 "nxt" (最初は開始ノード)、およびポイント値のリスト「pts」(入力テーブルの 0 番目の行から始まり、内部的には「y」として知られ、すべての無限値が削除されます。)

「その間」に。ループ、テーブルから現在の行を引き出し、既にアクセスしたノード ("ix" 内) を削除した結果の "nxt" 値が 0 を超える限り続行します。ループ内では、次の一連のインデックスを "nxt" の最後に、ポイント値を "pts" に累積します。最後に、インデックスとポイント値を (2 要素の) 結果として返します。

次のように実行します。デフォルトで結果が表示されます。

   traverseGraph grn
+---------------+---------------------------------------------+
|0 1 3 2 5 7 4 6|5 2 3 2 2 1 8 3 1 5 2 1 1 1 4 6 9 7 0 1 5 2 0|
+---------------+---------------------------------------------+

したがって、最初のボックスには、「0」で始まり「6」で終わるインデックスが含まれています。2 番目のボックス化された項目は、累積した順序でのポイント値のベクトルです。私はあなたがこれらで何をしているのか分からないので、私はそれらを見せるだけです.

インデックスを使用して、次のようにノード名を表示できます。

   0 1 3 2 5 7 4 6{(<"0'SABCDE'),'G1';'G2'
+-+-+-+-+-+--+-+--+
|S|A|C|B|E|G2|D|G1|
+-+-+-+-+-+--+-+--+

これがどれほど役立つかはわかりませんが、問題に対する簡単な解決策の概要を示しています。

于 2009-10-30T21:17:14.573 に答える