9

Prolog のデフォルトの深さ優先検索スキームよりも幅優先を使用する一般的な考え方は何ですか?

無限の枝を取りませんか？

Prolog で幅優先を使用する一般的な方法はありますか? 私はグーグルで検索してきましたが、初心者にとって有用な情報があまり見つかりませんでした.

4

3 に答える 3

7

「議事事検索」として知り合ったことがあります。（データ、関係、ルールなどの）ツリーをトラバースしている間、次に何をするかについての「議事日」（リスト）を維持します。ノードに入ると、その子をアジェンダに配置し、次に、ポップするアジェンダの最初の要素に進みます。このように、アジェンダの最後に新しいアイテムを配置すると、幅優先になります。それらを議題の前に置くと、深さ優先になります。

Prologで実装するのは簡単です。

編集：私はここで実装のヒントを与えることもできます。これは、アジェンダ検索アルゴリズムの非常に基本的な実装です。

agenda_search([N|T],Mode):-
    doWithNode(N),           % do whatever you do the searching for
    getNodeChildren(N,C),
    (Mode=bf ->              % bf or df (depth-first)
        append(T,C,A);
        append(C,T,A)),
    agenda_search(A,Mode).

これは、各ノードで実行するアクションを表す外部述語に依存しdoWithNodeます（たとえば、ノードデータを検索語と比較したり、ノードコンテンツをシリアル化したりします）。そしてgetNodeChildren、それは与えられたノードの子のリストをにバインドしますC（つまり、この述語は実際にツリー構造と子ノードを見つける方法を知っています）。もちろん、doWithNode述語はその仕事をするために追加のパラメーターを必要とするかもしれません、そしてそれはまたの引数リストに現れるでしょうagenda_search。

次のように呼び出すことができます。

agenda_search([RootNode], bf)   % for breadth-first search

と

agenda_search([RootNode], df)   % for depth-first search

また、このWebページで議事事検索の説明を少し見つけました。アジェンダ検索の良いところは、2つのバリアントdfとbfを簡単に切り替えて、結果を試すことができることです。アルゴリズムはメモリに関して非常に適切に動作します。アジェンダとして、まだ探索中のノードは、ツリー内のノードの（多かれ少なかれ）ごく一部のみを一度にキャプチャします（いわゆるフリンジ）。

于 2009-07-22T08:20:48.717 に答える
7

幅優先の利点は、すべての解が見つかることです。深さ優先では、無限分岐に行き詰まる可能性があります。

短所は、幅優先は大量のメモリを使用するため、通常は実行には使用されません。

使用したい場合は、ある種のキューで明示的に実装する必要があります。

編集：多くのメモリを使用せずに幅優先検索の利点を得たい場合は、反復深化を使用できます。これは、深さ制限のある深さ優先検索であり、連続して増加します。これにより、計算の重複が発生しますが、探索空間に分岐のない長い線形ストレッチがない場合、この重複は小さくなります。

于 2009-04-21T07:10:46.680 に答える
4

Agenda_search のコードは問題なく動作するはずです。効率のために、別のデータ構造の使用を検討することをお勧めします。実際、幅優先モードでは、ノード (T) のリスト全体が append(T,C,A) によってトラバースされます。たとえば、SICStus の library(queues) モジュールを使用できます。幅優先探索は次のようになります (述語 start/1、後続述語 s/2、およびゴール述語 goal/1 によってパラメータ化されます)。ループチェックも追加したことに注意してください。

bfs(Res) :- start(開始)、empty_queue(EQ)、
  queue_append(EQ,[e(Start,[])],Q1),
  bfs1(Q1、解像度)。

bfs1(Queue,Res) :- queue_cons(e(Next,Path),NQ,Queue),
   bfs2(次、パス、NQ、解像度)。

bfs2(H,Path,_NQ,Res) :- ゴール(H), reverse([H|Path],Res).
bfs2(H、パス、NQ、解像度) :-  
              findall(e(Succ,[H|パス]),
                      (s(H,成功),\+ メンバー(成功,パス)),All成功),
              queue_append(NQ,AllSuccs,NewQueue),
              bfs1(NewQueue,Res)。

(パス コンポーネントをより良いデータ構造 (AVL ツリーなど) で置換/補完することもできます。) 解決すべき問題の例は次のとおりです。

開始 (env(0,0))。
s(env(X,Y),env(X1,Y)) :- X1 は X+1 です。
s(env(X,Y),env(X,Y1)) :- Y1 は Y+1 です。
ゴール (env(3,3))。

キューをプライオリティ キューに置き換え、ヒューリスティック関数を使用して優先度を計算することもできます。次に、A* 検索 (深さ優先、幅優先、最適優先などをエミュレートできます) を取得します。Bratko の本 (Logic Programming for Artificial Intelligence) は、この資料を読むための良い情報源になるはずです。

于 2010-04-22T06:56:36.263 に答える