1

私は Prolog を勉強していますが、教授が提案したスライドを解釈するのに苦労しています。

グラフの2つのノード間のパスが存在するかどうかを示す古典的なプログラムから始めて、これは次のとおりです。

edge(a,b).
edge(b,c).
edge(a,e).
edge(c,d).
edge(d,e).
edge(f,e).

path(X,Y) :- edge(X,Y).

path(X,Y) :- path(X,Z),
             edge(Z,Y).

彼は述語: path(X,Y,Path)を使用する新しいバージョンを導入しました。これは、グラフに X と Y の間のパスが存在し、Pathが訪問したノードのリストである場合に TRUE になります。

そこで彼は、以前のプログラムの次の新しいバージョンを私にくれました。

/* BASE CASE: exist an edge between X and Y, so the Path is
              the couple [X,Y]
*/
path(X,Y,[X,Y]) :- edge(X,Y).

path(X,Y,P) :- path(X,Z,P1),
               edge(Z,Y),
               lastelem(P,Y,P1).

基本ケースは非常に単純です。X と Y を接続するエッジが存在する場合、X から Y へのパスが存在し、訪問したノードのリストが [X,Y] であることは真です。

2 番目のルールにはいくつか問題があります。X と Y が 1 つのエッジだけで接続されていない場合、X と Y の間にパスが存在する場合、X と他のノード Z の間にパスが存在する必要があります (そして P1 はこのパスで訪問したノードのリスト) Z を最終ノード Y に接続するエッジ。

これは非常に単純です...問題は、スライドで提供されていない最後の述語lastelem/3にあります(そのため、それが何をするのか正確にはわかりません):

lastelem(P,Y,P1).

P1 に Y を挿入して P を生成するか、そのようなものだと思います...

それについてもう少し正確な考えと、この述語の可能な実装はありますか?

4

3 に答える 3

0

Y教授はおそらく次のように追加したいと考えていますP:

lastelem(Lst0, X, Lst) :-
    append(Lst0, [X], Lst).

[しかし、リストへの追加には線形時間がかかるため、これはかなりばかげた考えです。一定時間の解決策は、要素を先頭に追加することです。

% I wouldn't actually write a predicate for this, but nevertheless:
lastelem(Lst, X, [X|Lst]).

これは逆の順序でパスを提供しますが、単一reverse/2で解決します。]

于 2013-05-01T16:56:28.420 に答える