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

算术表达式是 Prolog 中的一种特殊情况，不希望与未绑定的参数一起使用，因此您不能简单地要求path(s,e,D,P), D < 50，因为is- 子句需要实例化其所有右侧参数。

您可以使用 Prolog 的有限域 (FD) 约束扩展（例如在 GNU Prolog 中）：只需将您的更改is为 FD-equivalent #=，然后询问：

/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 以及路径：

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

虽然我认为有限域约束在这里最好使用，但您可以通过对代码进行少量修改来实现您想要的。

在第一个子句中，您可以使用一个新变量，而不是将输入参数与 的第三个参数travel/5统一，然后检查您当前的距离 ( ) 是否大于或等于这个新变量。Dconnected/3D

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