人工知能における DFS、A* 検索に関するグラフ検索バージョンとツリー検索バージョンの違いは何ですか?
質問する
74190 次
7 に答える
197
既存の回答から判断すると、この概念には多くの混乱があるようです。
問題は常にグラフです
ツリー検索とグラフ検索の違いは、問題のグラフがツリーであるか一般的なグラフであるかという事実に根差したものではありません。一般的なグラフを扱っていると常に想定されています。違いは、グラフの検索に使用されるトラバーサル パターンにあります。これは、グラフの形またはツリーの形にすることができます。
ツリー型の問題を扱っている場合は、両方のアルゴリズム バリアントで同等の結果が得られます。したがって、より単純なツリー検索バリアントを選択できます。
グラフ検索とツリー検索の違い
基本的なグラフ検索アルゴリズムは次のようになります。開始ノードstart、有向辺 as successors、およびgoalループ条件で使用される仕様で。openは、現在検討中のノードをメモリ内に保持します。オープン リストです。次の疑似コードは、すべての面で正しくないことに注意してください (2)。
ツリー検索
open <- []
next <- start
while next is not goal {
add all successors of next to open
next <- select one node from open
remove next from open
}
return next
の実装方法に応じてselect from open、深さ優先検索 (DFS) (最新の要素を選択)、幅優先検索 (BFS) (最も古い要素を選択)、均一コスト検索 (パス コストが最も低い要素を選択) など、さまざまな検索アルゴリズムのバリアントを取得します。 )、最小コストとヒューリスティック値を持つノードを選択することによる一般的な A スター検索など。
上記のアルゴリズムは、実際にはツリー検索と呼ばれます。開始状態をルートとする有向パスが複数ある場合は、基礎となる問題グラフの状態を複数回訪問します。状態が有向ループ上にある場合、その状態を何度でも訪れることができます。ただし、各訪問は、検索アルゴリズムによって生成されたツリー内の異なるノードに対応しています。後で説明するように、この明らかな非効率性が必要になる場合があります。
グラフ検索
見てきたように、ツリー探索は状態を複数回訪問できます。そのため、この状態の後に見つかった「サブツリー」を数回探索しますが、これにはコストがかかる可能性があります。グラフ検索は、閉じたリストで訪問したすべての状態を追跡することでこれを修正します。新しく見つかった後継者nextが既に知られている場合、それはオープンリストに挿入されません:
open <- []
closed <- []
next <- start
while next is not goal {
add next to closed
add all successors of next to open, which are not in closed
remove next from open
next <- select from open
}
return next
比較
グラフ検索は、訪問したすべての状態を追跡するため、より多くのメモリが必要であることに気付きました。これは、開いているリストを小さくすることで補うことができ、その結果、検索効率が向上します。
最適解
実装のいくつかの方法は、select最適なソリューションを返すことを保証できます。つまり、最短パスまたは最小コストのパス(エッジにコストが付加されたグラフの場合)。これは基本的に、ノードがコストの増加順に展開されるとき、またはコストがゼロ以外の正の定数であるときに常に当てはまります。この種の選択を実装する一般的なアルゴリズムは、均一コスト検索、またはステップ コストが同一の場合はBFSまたはIDDFSです。IDDFS は、BFS のアグレッシブなメモリ消費を回避し、ステップ サイズが一定の場合、通常、情報に基づかない検索 (ブルート フォース) に推奨されます。
あ*
また、(非常に人気のある) A*ツリー検索アルゴリズムは、許容ヒューリスティックと共に使用すると最適なソリューションを提供します。ただし、 A*グラフ検索アルゴリズムは、一貫性のある (または「単調な」) ヒューリスティック(許容性よりも強い条件) を使用した場合にのみ、この保証を行います。
(2) 疑似コードの欠陥
簡単にするために、提示されたコードは次のことを行いません。
- 失敗した検索を処理します。つまり、解決策が見つかった場合にのみ機能します
于 2013-03-07T20:50:11.227 に答える
8
ツリーはグラフの特殊なケースであるため、一般的なグラフで機能するものはすべてツリーでも機能します。ツリーは、ノードの各ペア間に正確に1つのパスがあるグラフです。これは、前の回答が述べているように、サイクルが含まれていないことを意味しますが、サイクルのない有向グラフ（DAG、有向非巡回グラフ）は必ずしもツリーではありません。
ただし、グラフにいくつかの制限があることがわかっている場合（たとえば、ツリーやDAGである場合）、通常、制限のないグラフよりも効率的な検索アルゴリズムを見つけることができます。たとえば、A *またはその非ヒューリスティックな対応物である「ダイクストラのアルゴリズム」をツリー（とにかく選択できるパスが1つしかない場合、DFSまたはBFSで見つけることができます）で使用することは、おそらくあまり意味がありません。 DAG上（トポロジカルソートによって取得された順序で頂点を検討することにより、最適なパスを見つけることができます）。
有向グラフと無向グラフの場合、無向グラフは有向グラフの特殊なケースです。つまり、「uからvへのエッジ（リンク、遷移）がある場合、vからuへのエッジもあります。
更新：気になるのがグラフ自体の構造ではなく検索のトラバーサルパターンである場合、これは答えではないことに注意してください。たとえば、@ziggystarの回答を参照してください。
于 2012-05-21T12:59:15.217 に答える
3
グラフとツリーの唯一の違いはサイクルです。グラフにはサイクルが含まれる場合がありますが、ツリーには含まれません。したがって、ツリーに検索アルゴリズムを実装する場合は、循環の存在を考慮する必要はありませんが、任意のグラフを操作する場合は循環を考慮する必要があります。サイクルを処理しないと、アルゴリズムは最終的に無限ループまたは無限再帰に陥る可能性があります。
考慮すべきもう 1 つのポイントは、扱っているグラフの方向特性です。ほとんどの場合、各エッジで親子関係を表すツリーを扱います。DAG (有向非巡回グラフ) も同様の特性を示します。しかし、双方向グラフは異なります。双方向グラフの各エッジは、2 つの近傍を表します。したがって、これら 2 種類のグラフでは、アルゴリズムのアプローチが少し異なるはずです。
于 2012-05-21T06:20:37.043 に答える
2
グラフとツリー
- グラフには周期がある
- 木にはサイクルがありません 「たとえば、頭の中の木を想像してください。枝は根に直接接続していませんが、枝は他の枝に上向きに接続しています」
ただし、AI グラフ検索とツリー検索の場合
グラフ検索には、アルゴリズムが新しいノードを探索し、「使用されているアルゴリズムに関係なく」訪問済みとしてマークするたびに、アルゴリズムは通常、現在のノードから到達可能な他のすべてのノードを探索するという優れたプロパティがあります。
たとえば、3 つの頂点 AB と C を持つ次のグラフを考えて、次のエッジを考えます。
AB、BC、CA、C から A のサイクルがあります。
また、A から開始して DFS を実行すると、A は新しい状態 B を生成し、B は新しい状態 C を生成しますが、C が調査されると、アルゴリズムは新しい状態 A を生成しようとしますが、A は既にアクセスされているため、無視されます。涼しい！
しかし、木はどうですか？よく木のアルゴリズムは、訪問したノードを訪問済みとしてマークしませんが、木にはサイクルがありません。どのように無限ループに入るのでしょうか?
3 つの頂点を持つこのツリーを考えて、次のエッジを考えます
A - B - C は A に根ざし、下向きです。そして、DFSアルゴリズムを使用しているとしましょう
A は新しい状態 B を生成し、B は 2 つの状態 A と C を生成します。ツリーには「探索された場合に訪問したノードをマークする」機能がないため、DFS アルゴリズムが A を再度探索し、新しい状態 B を生成する可能性があります。無限ループに陥っています。
しかし、何か気づいたことはありますか?私たちは無向辺に取り組んでいます。つまり、AB と BA の間に接続があります。もちろん、これは循環ではありません。なぜなら、循環は頂点が >= 3 でなければならず、最初と最後のノードを除いてすべての頂点が異なることを意味するからです。
ST A->B->A->B->A サイクル プロパティ >= 3 に違反しているため、サイクルではありません。ただし、実際には、A->B->C->A はサイクル >= 3 つの異なるノード チェック済み、最初と最後のノードは同じ Checked です。
再びツリー エッジ、A->B->C->B->A を考えてみましょう。もちろん、これはサイクルではありません。2 つの B があるためです。つまり、すべてのノードが異なるわけではありません。
最後に、ツリー検索アルゴリズムを実装して、同じノードを 2 回探索しないようにすることができます。しかし、それには結果があります。
于 2016-03-29T08:35:05.387 に答える
1
I will add to the @ziggystar's answer (other answers refer to the differences between trees and graphs as data structures, which is not what the question is about, the question refers to the tree VS graph algorithms for traversing your graph!).
This somewhat confusing terminology comes from Russell and Norvig's "Artificial Intelligence A Modern Approach":
Tree-Search algorithm - is any particular algorithm used for solving your search problem.
Graph-Search algorithm - is a Tree-Search algorithm augmented with a set of explored states.
Both of these algorithms are represented as a tree! The reason we call the Graph-Search algorithm a Graph-Search algorithm is because it can be represented (again - as a tree) directly on our search problem's graph.
Take a look at the map of Romania. This is our search problem's graph.
Now, we can apply many algorithms to find a path from Arad to Bucharest (Breadth-First Search, Depth-First Search, Greedy Search - anything our heart desires). All of these algorithms, however, can be divided into Tree-Search algorithms and Graph-Search algorithms.
The Tree-Search algorithm represents the solution to our Arad-to-Bucharest problem as a tree. Note the repeated "Arad" node.
The Graph-Search algorithm represents the solution to our Arad-to-Bucharest problem as a tree, too - except we remove the repeated "Arad" node from the tree. However, thanks to this removal of repeated states, we have a nicer way to represent it - directly on the graph of our search problem, on the map of Romania! Hence the "Graph" in the "Graph-Search algorithm".
Here is some pseudocode for you. Note that the only difference between the Tree-Search algorithm and Graph-Search algorithm is the addition of the set of explored states.
于 2021-12-11T18:38:40.570 に答える