4

path(A,B,Path)A から B へのボード上のすべての有効なパスを生成する Prolog 関数があります。

この関数の出力は次のようになります。

?- path(0,2,Path).
Path = [0, 1, 2] ;
Path = [0, 3, 2] ;
Path = [0, 1, 4, 2] ;
Path = [0, 3, 4, 2] ;
Path = [0, 1, 4, 5, 3, 2] ;

などなど

有効なパスを含むリストの無限のセットを生成します。これらのパスの最短を取得したいだけです（ただし、いくつもあります）。つまりshortest(A,B,Path)、ボード上の A から B への最短の有効なパスを生成する関数が必要です。

私が望む出力は次のとおりです。

?- shortest(0,2,Path).
Path = [0, 1, 2] ;
Path = [0, 3, 2] ;
false.

Prologの関数をいじって、setofすべてのパスをセットにバインドし、そのセットに長さの制限を課しましたが、まだ機能していません。

これまでの私の下手な作業は次のようになります。setofそれは間違いなく間違っています。どのように機能し、このセットから最短のリストを見つける方法を理解していただければ幸いです。ありがとう！

shortest(A,B,MinPath) :-
    setof(Path,path(A,B,Path),MinPath),
    min(length(Path), length(MinPath)).
4

1 に答える 1

6

これは、反復深化の古典的なケースです。トップレベルで入力するだけです：

?- length(Path, N), path(0, 2, Path).

最初の答えは、最短の長さになります。そして、それが Prolog で非常にエレガントにできることです:無限集合を列挙し始め、有限時間後に探しているものが見つかることを期待しています。

おそらくその長さのすべてのパスは同じように関心があるため、それらすべてが必要です。それ以外の場合は、上記に満足してください。また、さまざまなノードの最短パスを列挙する場合があるためnode/1、グラフで発生するノードである必要があります。たとえば、ノード 0 から 10 があり、次node/1のように定義できます。

node(N) :-
   between(0,10,N).

shortest(A,B, Minpath) :-
   setof(Min, Path ^ ( node(A), node(B),
                       once( ( length(Path, Min), path(A, B, Path) ) ) ), [Min]),
   length(Minpath, Min),
   path(A, B, Minpath).

ただし、このソリューションには問題があります。確かに、非常に醜いキャッチです。あなたが言った：

（いくらあっても）

パスがまったくない場合、このソリューションは永久にループします。あなたは警告されました。

編集：完全を期すために：path/3リストの長さが固定されている場合は終了すると想定しました。

そして結論として：具体的な単純なグラフの場合、サイクルを回避するより明示的な方法が望ましいです。ただし、サイクルが実際に何であるかがまったく明確でない状況が多くあります (いくつかの単純な機械をシミュレートすることを考えてください)。そのような状況では、反復的な深化は非常に効果的です。プロローグ。

パスがまったくない場合のループに関する最後の注意事項があります。この問題を克服するには、ある種のリソース制限計算が必要です。SICStus Prolog は を提供しますがlibrary(timeout)、他のシステムには多かれ少なかれ同等の機能があります。SWI は (最近)call_with_inference_limit/3この目的のために (非常に難解なインターフェースで) 導入されました。

于 2014-04-20T22:54:58.050 に答える