2

次のコードを書いていますが、完璧な結果が得られています。

edge(s,a,300).
edge(s,d,20).
edge(a,d,400).
edge(a,b,1500).
edge(b,c,9).
edge(b,e,200).
edge(c,d,2000).
edge(c,g,12).
edge(d,e,3).
edge(e,f,400).
edge(f,g,800).

connected(X,Y,D) :- edge(X,Y,D) ; edge(Y,X,D).

path(A,B,D,Path) :- 
    travel(A,B,D,[A],Q),
    reverse(Q,Path).

travel(A,B,D,P,[B|P]) :-
    connected(A,B,D).

travel(A,B,D,Visited,Path) :-
    connected(A,X,D1),
    X \== B,
    \+member(X,Visited),
    D2 is D - D1,
    travel(X,B,D2,[X|Visited],Path).

ここで次のようにクエリすると

| ?- path(s,e,23,P).
P = [s,d,e] ? ;
no
| ?-

私は正しい応答を取得します。しかし、いいえ、D<50 の結果を取得したいと思います。実行する方法？

4

3 に答える 3

4

path(s,e,D,P), D < 50算術式は Prolog の一種の特殊なケースであり、バインドされていない引数で動作することは想定されていないため、単純に を要求することはできませんis。-clause では右側の引数をすべてインスタンス化する必要があるためです。

Prolog の有限領域 (FD) 制約拡張を使用できます ( GNU Prolog など):isを FD に相当するものに変更して、次の#=ように尋ねます。

/Users/stolz/test.pl compiled, 27 lines read - 3180 bytes written, 8 ms
| ?- fd_domain(D,0,50), path(s,e,D,P).

D = 23
P = [s,d,e] ? ;

no
于 2012-11-06T11:18:06.060 に答える
2

Prolog に距離 D と Path を計算させる必要があります。

travel(A,B,D,Visited,Path) :-
    connected(A,X,D1),
    X \== B,
    \+member(X,Visited),
    travel(X,B,D2,[X|Visited],Path),
    D is D2 + D1.

その後、クエリを実行できます

?- path(Start, Stop, D, P), D < 50.

D < 50 のすべてのパスを (バックトラックで) 取得します。

?- path(s,e,X,P),X<50.
X = 23,
P = [s, d, e] ;
false.
于 2012-11-06T17:53:52.157 に答える
1

ここでは有限ドメイン制約を使用するのが最適だと思いますが、コードを少し変更するだけで目的を達成できます。

入力引数をの3番目の引数とtravel/5統合する代わりに、の最初の句で、新しい変数を使用して、現在の距離（ ）がこの新しい変数以上であるかどうかを確認できます。Dconnected/3D

travel(A,B,D,P,[B|P]) :-
    connected(A,B,TD),
    D >= TD.
于 2012-11-06T14:59:16.780 に答える