ツリー検索の使用

Question

本の第3章で説明されているように、ツリー検索とグラフの検索（情報のない検索）についていくつか質問があります。 http://aima.cs.berkeley.edu/

私が見るように、2つの唯一の違いは、グラフ検索がループを処理することです（それらを回避します）。

最初の質問：グラフ検索とツリー検索の両方が、手元の問題の動的なツリーを構築しますか？

2番目の質問：フロンティアキューのみをソートする戦略として、DFS、BFS、UCSを使用して、ルーマニアの問題（AradからBucharestへの到達）のマップを解決するためにグラフ検索が使用されたと仮定します。ここで、ルーマニアのマップのグラフをツリーに変更し、ツリー検索を使用する標準的な方法はありますか？

3番目の質問：グラフとツリーの検索を選択するのに役立つ基準は何ですか？

よろしくお願いします

Answer 1

BFSとDFSの両方がグラフを取得し、それのサブグラフを誘導します。このサブグラフには、開始ノードからすべてのノードが到達可能で、ツリーです。

おそらくグラフをツリーに変換してからツリー検索を使用することもできますが、グラフをツリーに変換する最も簡単な方法は、実際には何らかの検索であり、検索を使用することは冗長です。グラフを変換し、最初の検索を使用できた場合に、ツリーで別の検索を行います。

グラフでグラフ検索を使用し、ツリーでツリー検索を使用します。特に、これは、ツリーサーチを使用すると、周期的なグラフが無限のループに巻き込まれる可能性があるためです。

（指示されたグラフを話している場合、おそらく非環状グラフを検索する特別な種類のツリー検索があります。

Answer 2

処理する質問に応じて、どの検索方法（ツリー検索またはグラフ検索）を使用します。通常、質問が解決方法に影響すると考える見解があります。 2つの検索方法は、異なる構造、ツリー検索ハンドルを備えたツリー検索ハンドル、グラフのグラフ検索ハンドルの処理とは異なります。私たちが知っているように、木は特別な種類のグラフであり、サイクルはありません。そのため、質問をツリーとしてモデル化できる場合は、ツリー検索を簡単に使用できます。たとえば、8つのパズルでは、エッジにない数字には4つの決定があります。ケースを考えてみましょう。 、新しい状態が以前と同じであることを避けるために、新しい場所で3つの決定のみを準備します。この制限は、問題を解決するのに役立ちます。次に、8つのパズル解決プロセスが状態転送ツリーを構築できます。