4

グラフ/ツリーでの検索についていくつか質問があります。

空のチェス盤があり、ポーンを点 A から点 B に動かしたいとします。

A. 深さ優先検索または幅優先検索を使用する場合、開いたリストと閉じたリストを使用する必要がありますか? これは、チェックするすべての要素を含むリストと、すでにチェックされている他のすべての要素を含むリストですか? それらのリストがなくてもそれを行うことさえ可能ですか? A* はどうですか?

B. リストを使用する場合、解を見つけた後、A から B への状態のシーケンスをどのように取得できますか? オープンリストとクローズリストにアイテムがある場合、 (x, y) 状態だけでなく、 (x, y, parent_of_this_node) で形成された「拡張状態」があると思いますか?

C. 状態 A には 4 つの移動 (右、左、上、下) があります。先手左としたら、次の状態で元の状態に戻せばいいのでしょうか？これは、つまり、「正しい」動きをしますか？そうでない場合は、検索ツリーを毎回横断して、どの州に行ったことがあるかを確認する必要がありますか?

D. ツリーの状態が行き止まりになっていることを知っているので、それを無視する必要がありますか? これを行うには、訪問した州のリストを常に保持する必要があると思いますよね?

E. 検索ツリーとグラフに違いはありますか? それらは同じものを見る別の方法ですか？

4

3 に答える 3

3

A. 深さ優先検索または幅優先検索を使用する場合、開いたリストと閉じたリストを使用する必要がありますか?

DFS では、少なくとも現在のパスを保存する必要があります。そうしないと、後戻りできません。訪問した (閉じた) すべてのノードのリストを維持することを決定した場合、サイクル (同じノードを複数回展開する) を検出して回避することができます。反対に、DFS のスペース効率はもうありません。クローズド リストを使用しない DFS は、検索スペースの深さに比例するスペースのみを必要とします。

BFS では、公開リスト (フリンジと呼ばれることもあります) を維持する必要があります。そうしないと、アルゴリズムは機能しません。さらにクローズドリストを維持すると、（再び）サイクルを検出/回避できるようになります。BFS を使用すると、閉じたリストの追加スペースはそれほど悪くないかもしれません。とにかくフリンジを維持する必要があるからです。フリンジ サイズとクローズド リスト サイズの関係は検索空間の構造に強く依存するため、ここではこれを考慮する必要があります。たとえば、分岐係数が 2 の場合、両方のリストのサイズは同じであり、閉じたリストを使用することによる影響は、その利点に比べてそれほど悪くないように見えます。

A* はどうですか?

A* は、特別な (情報に基づいた) タイプの BFS と見なすことができるため、オープン リストが必要です。クローズド リストの省略は、BFS よりもデリケートです。また、クローズド リスト内のコストの更新を決定します。これらの決定に応じて、使用されるヒューリスティックの種類などに応じて、アルゴリズムが最適化および/または完全でなくなる可能性があります。ここでは詳しく説明しません。

B.

はい、閉じたリストはある種の逆ツリー (ルート ノードに向かうポインター) を形成する必要があるため、ソリューション パスを抽出できます。通常、これを行うにはクローズド リストが必要です。DFS の場合、現在のスタックはまさに​​ソリューション パスです (クローズド リストは必要ありません)。また、パスには関心がなく、解決策またはその存在のみに関心がある場合があることに注意してください。

C.

以前の回答を読んで、サイクルの検出について説明している部分を探してください。

D.

閉じたリストの循環を避けるには、既に閉じたリスト内にあるノードを展開しないでください。注: パス コストが関係するようになると (A* を思い出してください)、事態はさらに複雑になる可能性があります。

E. 検索ツリーとグラフに違いはありますか?

閉じたリストを維持してグラフ検索のようなサイクルを回避する検索と、1 つのツリー検索を使用しない検索を検討できます。

于 2010-01-21T18:26:20.597 に答える
2

A) オープン/クローズ リストを回避することは可能です。考えられるすべてのパスを試すことができますが、非常に長い時間がかかります。

B) ゴールに到達したら、parent_of_this_node 情報を使用して、ゴールから「後退」します。ゴールから始めて、その親を取得し、親の親を取得するなどして、開始点に到達します。

C）それは問題ではないと思います-あなたが説明したステップがより短いパスになる方法はありません（あなたのステップが負の重みを持っていない限り、その場合Dijkstra / A *を使用することはできません）。私の A* コードでは、このケースをチェックして無視しますが、コーディングが最も簡単な方法は何でも行います。

D) それは依存します - Dijkstra が同じノードを再び開くことは決してできないと思います (誰かが私を修正してくれますか?)。A* は間違いなくノードを再訪できます。同じノードへの短いパスが見つかった場合はそのパスを保持し、それ以外の場合は無視します。

E) よくわかりません。私自身、特にツリーに対して何かをしたことはありません。

ここに A* の優れた紹介があります: http://theory.stanford.edu/~amitp/GameProgramming/ では、オープン セットの実装方法、ヒューリスティックの選択方法などについて多くの詳細が説明されています。

于 2010-01-21T07:08:00.993 に答える
1

A. オープン リストとクローズ リストは一般的な実装の詳細であり、アルゴリズム自体の一部ではありません。たとえば、これらのいずれも使用せずに深さ優先のツリー検索を行うのが一般的です。標準的な方法は、ツリーの再帰的なトラバーサルです。

B. ノードが以前のノードを参照するようにするのが一般的であり、バックリンクをたどって計画を再構築できるようにします。または、これまでのソリューション全体を各候補に格納するだけですが、それを実際にノードと呼ぶと誤解を招く可能性があります。

C. 左に移動してから右に移動すると、同等の状態になると想定しています。この場合、元の状態を既に探索しており、クローズド リストに含まれているため、元の状態に戻す必要はありません。開いているリスト。どの状態がすでに完全に調査されているかを知るというまさにこの目的のために、クローズドリストを保持するため、毎回検索ツリーをトラバースしません。これは、O(1) 構造として実装されることが多いためです。同じ位置にいることは同じ状態にあることと同じであると常に想定できるわけではないことに注意してください。ほとんどのゲーム パス検索ではそうですが、一般的な検索ではそうではありません。

D. はい。訪れた州のリストは、クローズド リストと呼ばれるものです。また、開いているリストをチェックして、特定の状態を 2 回調べる予定がないことを確認する必要があります。通常、これらのものは線形構造に格納されるため、ツリー自体を検索する必要はありません。アルゴリズムは全体としてツリー (またはグラフ) を検索し、(状態空間を表すノードの) ツリーを生成しますが、アルゴリズム内のどの時点でもツリー構造を明示的に検索しません。

E. ツリーは、サイクル/ループを持たないタイプのグラフです。したがって、同じグラフ検索手順を使用して、いずれかを検索します。グラフを介して検索を表すツリー構造を生成するのが一般的です。これは、各ノードから検索で先行/生成されたノードへの後方リンクによって暗黙的に表されます。（ただし、各状態で計画全体を保持するルートをたどると、ツリーはなく、部分的なソリューションのリストだけになります。）

于 2010-01-21T11:36:15.383 に答える