[search] グラフ検索とツリー検索



1 Answers

ツリーはグラフの特殊なケースであるため、一般的なグラフのためにどのような作業が行われていても、ツリーに対して機能します。 ツリーは、ノードの各ペアの間に正確に1つのパスがあるグラフです。 これは、以前の回答状態のようにサイクルを含まないことを意味しますが、サイクルのない有向グラフ(DAG、有向非循環グラフ)は必ずしもツリーではありません。

ただし、グラフにツリーやDAGなどのいくつかの制限があることがわかっている場合は、通常、無制限のグラフより効率的な検索アルゴリズムを見つけることができます。 例えば、A *やそれ以外の「ダイクストラのアルゴリズム」をツリー(DFSやBFSで見つけることができるパスは1つしかありません)に使うのはあまり意味がありません。 DAG(トポロジカルソートによって得られた順序で頂点を考慮することによって最適な経路を見つけることができる)上で実行される。

無向グラフの場合、無向グラフは有向グラフの特殊なケースです。つまり、「 uからvへのエッジ(リンク、遷移)がある場合は、 vからuへのエッジもあります。

更新 :あなたが気にしているのは、グラフ自体の構造ではなく、検索のトラバーサルパターンであれば、これは答えではないことに注意してください。 例えば、@ ziggystarの答えを見てください。

Question

人工知能におけるDFS、A *検索に関するグラフ検索ツリー検索の基本的な違いは何ですか?




GRAPH VS TREE

  • グラフにはサイクルがあります
  • 木にはサイクルがありません。例えば、あなたの頭の中のどんな木も想像してください。枝は根に直接接続していませんが、枝は他の枝への接続を持っています。

しかし、AIの場合Graph-search対Tree-search

グラフ検索は、アルゴリズムが新しいノードを探索し、「使用されたアルゴリズムにかかわらず」、それが現在のノードから到達可能な他のすべてのノードを探索するたびにマークする良好な特性を有する。

例えば、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でなければならず、すべての頂点が最初と最後のノードを除いて区別されることを意味するので、これはサイクルではありません。

A→B→A→B→Aサイクリング特性> = 3に違反しているためサイクルではありませんが、A→B→C→Aはサイクル> = 3の別個のノードチェックされ、最初と最後のノードは同じチェックです。

2つのBsが存在するので、A - > B - > C - > B - > Aというツリーのエッジも当然サイクルではないと考えてください。

最後に、同じノードを2回探索するのを防ぐために、ツリー探索アルゴリズムを実装することができます。 しかし、それは結果をもたらします。






Related