尝试获取给定路径的成本
Trying to obtain cost for a given path
我是 Prolog 新手
我在 Prolog 中尝试一个规则，该规则为我提供了从一个节点到另一个节点的给定路径，还为我提供了该路径的总权重。
我已经成功获取了路径的所有边，但无法显示路径的权重。我对它进行了调试，可以看出变量 S 加起来就是路径的总重量，但在回来的路上，删除了所有元素。我的想法是把总权重加到P.
代码：
notIn(A,[]).
notIn(A,[H|T]):- A\==H,notIn(A,T).
path(X,X,_,[], S, P).
path(X,Y,[X|Cs], S, P) :-
path(X,Y,[X],Cs, S, P), P is S+W.
path(X,Y,Visited,[Z|Cs], S, P) :-
connection(X,Z,W),
notIn(Z,Visited),
path(Z,Y,[Z|Visited],Cs, S+W, P).
? path(ori, dest, X, 0, P).
您的谓词几乎可以工作。我只想解决两个问题和一些细节。首先，将具有不同属性的谓词分开会极大地提高可读性。所以让我们把 path/5 的一条规则放在 path/6 的两条规则前面，像这样：
path(X,Y,[X|Cs], S, P) :-
path(X,Y,[X],Cs, S, P),
P is S+W. % <-(1)
path(X,X,_,[], S, P).
path(X,Y,Visited,[Z|Cs], S, P) :-
connection(X,Z,W),
notIn(Z,Visited),
path(Z,Y,[Z|Visited],Cs, S+W, P). % <-(2)
查看您的示例查询 path/5 似乎是您要调用以查找路径的谓词。在其单一规则（标记为 % <-(1)）的第二个目标中，您使用内置的 is/2 和右侧的表达式 S+W。变量 W 第一次出现在这里，因此是未绑定的。这会导致实例化错误，如下例所示：
?- X is 1+W.
ERROR!!
INSTANTIATION ERROR- in arithmetic: expected bound value
但是，由于您仅使用 path/5 来调用 path/6，因此不需要该目标。其次，在 path/6 的第二条规则中，在最后一个目标中，您将 S+W 作为参数传递，而不是先对其求值。为了看看会发生什么，让我们从 path/5 中删除标记为 % <-(1) 的目标，并在您的代码中添加一个示例图：
connection(ori,a,2).
connection(a,b,5).
connection(b,a,4).
connection(b,dest,1).
现在考虑带有额外目标的示例查询：
?- path(ori, dest, X, 0, P), Weight is P.
P = 0+2+5+1,
Weight = 8,
X = [ori,a,b,dest] ? ;
no
如您所见，参数 S+W 导致最终权重成为表达式而不是值。考虑在递归目标之前添加目标 S1 is S+W 并将 S1 作为参数传递。第三，您在谓词 notIn/2 中使用了内置的 (\==)/2。这种比较成功或失败没有副作用或统一。这很好，只要两个参数都绑定到值，但在与未绑定变量一起使用时会出现问题。考虑以下查询：
?- X=Y, X\==Y.
no
按预期失败但是：
?- X\==Y, X=Y.
X = Y
成功，因为X\==Y对变量没有影响，可以在下一个目标统一。最好使用 dif/2 代替：
?- X=Y, dif(X,Y).
no
?- dif(X,Y), X=Y.
no
最后，两个小建议：首先，由于您使用 path/5 的第 4 个参数来传递 0 作为权重的起始值，您不妨在规则的单一目标，从而将界面简化为 path/4。其次，最好为谓词取一个更具描述性的名称来反映其声明性质，比如 start_end_path_weight/4。所以你的代码看起来像这样：
notIn(A,[]).
notIn(A,[H|T]):-
dif(A,H),
notIn(A,T).
start_end_path_weight(X,Y,[X|Cs], P) :-
path(X,Y,[X],Cs, 0, P).
path(X,X,_,[], P, P).
path(X,Y,Visited,[Z|Cs], S, P) :-
connection(X,Z,W),
notIn(Z,Visited),
S1 is S+W,
path(Z,Y,[Z|Visited],Cs, S1, P).
经过这些修改，您的示例查询如下所示：
?- start_end_path_weight(ori,dest,X,W).
W = 8,
X = [ori,a,b,dest] ? ;
no
以下是如何改进 by using clpfd 的算术而不是 (is)/2：
:- use_module(library(clpfd)).
start_end_path_weight(X,Y,[X|Cs], P) :-
path(X,Y,[X],Cs, 0, P).
path(X,X,_,[], P, P).
path(X,Y,Visited,[Z|Cs], S, P) :-
connection(X,Z,W),
notIn(Z,Visited)
maplist(dif(Z),Visited),
S1 is S+W
S1 #= S+W, S1 #=< P,
path(Z,Y,[Z|Visited],Cs, S1, P).
限制最大成本？ 小菜一碟！
考虑以下 InterRail 子集...
...翻译成序言...
connection(X,Y,D) :- to_fro_dt(X,Y,D).
connection(X,Y,D) :- to_fro_dt(Y,X,D).
to_fro_dt(aberdeen,edinburgh,140). to_fro_dt(amsterdam,berlin,370). to_fro_dt(amsterdam,brussels,113). to_fro_dt(amsterdam,cologne,158). to_fro_dt(amsterdam,copenhagen,675). to_fro_dt(ancona,igoumenitsa,900). to_fro_dt(athens,patras,215). to_fro_dt(athens,/* for consistency */piraeus,5). to_fro_dt(athens,thessaloniki,265). to_fro_dt(bar,belgrade,572). to_fro_dt(barcelona,madrid,170). to_fro_dt(barcelona,marseille,280). to_fro_dt(barcelona,sevilla,330). to_fro_dt(barcelona,valencia,175). to_fro_dt(bari,igoumenitsa,570). to_fro_dt(bari,rome,240). to_fro_dt(belfast,dublin,240). to_fro_dt(belgrade,bucharest,730). to_fro_dt(belgrade,budapest,450). to_fro_dt(belgrade,sarajevo,540). to_fro_dt(belgrade,skopje,525). to_fro_dt(belgrade,sofia,485). to_fro_dt(bergen,oslo,405). to_fro_dt(berlin,cologne,260). to_fro_dt(berlin,hamburg,95). to_fro_dt(berlin,munich,345). to_fro_dt(berlin,prague,275). to_fro_dt(berlin,warsaw,365). to_fro_dt(bern,frankfurt,235). to_fro_dt(bern,lyon,230). to_fro_dt(bern,milan,240). to_fro_dt(birmingham,edinburgh,265). to_fro_dt(birmingham,holyhead,245). to_fro_dt(birmingham,london,105). to_fro_dt(bologna,florence,37). to_fro_dt(bologna,milan,60). to_fro_dt(bordeaux,lyon,375). to_fro_dt(bordeaux,madrid,660). to_fro_dt(bordeaux,paris,180). to_fro_dt(bristol,london,105). to_fro_dt(brussels,cologne,107). to_fro_dt(brussels,frankfurt,190). to_fro_dt(brussels,london,140). to_fro_dt(brussels,paris,85). to_fro_dt(bucharest,budapest,830). to_fro_dt(bucharest,sofia,540). to_fro_dt(bucharest,zagreb,365). to_fro_dt(budapest,ljubljana,540). to_fro_dt(budapest,vienna,165). to_fro_dt(budapest,warsaw,680). to_fro_dt(budapest,zagreb,365). to_fro_dt(catania,naples,450). to_fro_dt(cologne,frankfurt,82). to_fro_dt(copenhagen,hamburg,270). to_fro_dt(copenhagen,oslo,520). to_fro_dt(copenhagen,stockholm,315). to_fro_dt(cork,dublin,165). to_fro_dt(dublin,holyhead,195). to_fro_dt(dublin,westport,210). to_fro_dt(edinburgh,glasgow,50). to_fro_dt(faro,lisbon,230). to_fro_dt(florence,rome,95). to_fro_dt(florence,venice,123). to_fro_dt(frankfurt,hamburg,220). to_fro_dt(frankfurt,munich,190). to_fro_dt(frankfurt,paris,235). to_fro_dt(hamburg,munich,350). to_fro_dt(helsinki,rovaniemi,570). to_fro_dt(helsinki,turku,110). to_fro_dt(heraklion,piraeus,390). to_fro_dt(igoumenitsa,patras,360). to_fro_dt(istanbul,sofia,775). to_fro_dt(istanbul,thessaloniki,720). to_fro_dt(kiruna,stockholm,960). to_fro_dt(lisbon,madrid,610). to_fro_dt(lisbon,porto,165). to_fro_dt(ljubljana,venice,540). to_fro_dt(ljubljana,zagreb,140). to_fro_dt(london,paris,135). to_fro_dt(london,penzance,305). to_fro_dt(lyon,marseille,100). to_fro_dt(lyon,paris,115). to_fro_dt(madrid,'málaga',165). to_fro_dt(madrid,pamplona,180). to_fro_dt(madrid,santander,270). to_fro_dt(madrid,santiago,425). to_fro_dt(madrid,sevilla,155). to_fro_dt(madrid,valencia,105). to_fro_dt(marseille,montpellier,140). to_fro_dt(marseille,nice,155). to_fro_dt(milan,munich,465). to_fro_dt(milan,nice,310). to_fro_dt(milan,venice,155). to_fro_dt(munich,prague,365). to_fro_dt(munich,venice,425). to_fro_dt(munich,vienna,250). to_fro_dt(naples,rome,70). to_fro_dt(oslo,stockholm,380). to_fro_dt(paris,rennes,120). to_fro_dt(piraeus,rhodes,710). to_fro_dt(prague,vienna,270). to_fro_dt(prague,warsaw,520). to_fro_dt(sarajevo,zagreb,550). to_fro_dt(skopje,sofia,540). to_fro_dt(skopje,thessaloniki,240). to_fro_dt(sofia,thessaloniki,400). to_fro_dt(split,zagreb,335). to_fro_dt(stockholm,/* added by hand */turku,725). to_fro_dt(stockholm,'östersund',420). to_fro_dt(trondheim,'östersund',230). to_fro_dt(venice,vienna,440). to_fro_dt(vienna,warsaw,450).
...让我们找到
的路径
从维也纳开始
包括至少 2 个其他城市
并且累计旅行时间为 10 小时（或更短）！
?- W #=< 600, Path = [_,_,_|_], start_end_path_weight(vienna, _, Path, W).
W = 530, Path = [vienna,budapest,zagreb] ;
W = 595, Path = [vienna,munich,berlin] ;
W = 440, Path = [vienna,munich,frankfurt] ;
W = 522, Path = [vienna,munich,frankfurt,cologne] ;
W = 600, Path = [vienna,munich,hamburg] ;
W = 545, Path = [vienna,prague,berlin] ;
W = 563, Path = [vienna,venice,florence] ;
W = 600, Path = [vienna,venice,florence,bologna] ;
W = 595, Path = [vienna,venice,milan] ;
false. % terminates universally fast
我是 Prolog 新手
我在 Prolog 中尝试一个规则，该规则为我提供了从一个节点到另一个节点的给定路径，还为我提供了该路径的总权重。
我已经成功获取了路径的所有边，但无法显示路径的权重。我对它进行了调试，可以看出变量 S 加起来就是路径的总重量，但在回来的路上，删除了所有元素。我的想法是把总权重加到P.
代码：
notIn(A,[]).
notIn(A,[H|T]):- A\==H,notIn(A,T).
path(X,X,_,[], S, P).
path(X,Y,[X|Cs], S, P) :-
path(X,Y,[X],Cs, S, P), P is S+W.
path(X,Y,Visited,[Z|Cs], S, P) :-
connection(X,Z,W),
notIn(Z,Visited),
path(Z,Y,[Z|Visited],Cs, S+W, P).
? path(ori, dest, X, 0, P).
您的谓词几乎可以工作。我只想解决两个问题和一些细节。首先，将具有不同属性的谓词分开会极大地提高可读性。所以让我们把 path/5 的一条规则放在 path/6 的两条规则前面，像这样：
path(X,Y,[X|Cs], S, P) :-
path(X,Y,[X],Cs, S, P),
P is S+W. % <-(1)
path(X,X,_,[], S, P).
path(X,Y,Visited,[Z|Cs], S, P) :-
connection(X,Z,W),
notIn(Z,Visited),
path(Z,Y,[Z|Visited],Cs, S+W, P). % <-(2)
查看您的示例查询 path/5 似乎是您要调用以查找路径的谓词。在其单一规则（标记为 % <-(1)）的第二个目标中，您使用内置的 is/2 和右侧的表达式 S+W。变量 W 第一次出现在这里，因此是未绑定的。这会导致实例化错误，如下例所示：
?- X is 1+W.
ERROR!!
INSTANTIATION ERROR- in arithmetic: expected bound value
但是，由于您仅使用 path/5 来调用 path/6，因此不需要该目标。其次，在 path/6 的第二条规则中，在最后一个目标中，您将 S+W 作为参数传递，而不是先对其求值。为了看看会发生什么，让我们从 path/5 中删除标记为 % <-(1) 的目标，并在您的代码中添加一个示例图：
connection(ori,a,2).
connection(a,b,5).
connection(b,a,4).
connection(b,dest,1).
现在考虑带有额外目标的示例查询：
?- path(ori, dest, X, 0, P), Weight is P.
P = 0+2+5+1,
Weight = 8,
X = [ori,a,b,dest] ? ;
no
如您所见，参数 S+W 导致最终权重成为表达式而不是值。考虑在递归目标之前添加目标 S1 is S+W 并将 S1 作为参数传递。第三，您在谓词 notIn/2 中使用了内置的 (\==)/2。这种比较成功或失败没有副作用或统一。这很好，只要两个参数都绑定到值，但在与未绑定变量一起使用时会出现问题。考虑以下查询：
?- X=Y, X\==Y.
no
按预期失败但是：
?- X\==Y, X=Y.
X = Y
成功，因为X\==Y对变量没有影响，可以在下一个目标统一。最好使用 dif/2 代替：
?- X=Y, dif(X,Y).
no
?- dif(X,Y), X=Y.
no
最后，两个小建议：首先，由于您使用 path/5 的第 4 个参数来传递 0 作为权重的起始值，您不妨在规则的单一目标，从而将界面简化为 path/4。其次，最好为谓词取一个更具描述性的名称来反映其声明性质，比如 start_end_path_weight/4。所以你的代码看起来像这样：
notIn(A,[]).
notIn(A,[H|T]):-
dif(A,H),
notIn(A,T).
start_end_path_weight(X,Y,[X|Cs], P) :-
path(X,Y,[X],Cs, 0, P).
path(X,X,_,[], P, P).
path(X,Y,Visited,[Z|Cs], S, P) :-
connection(X,Z,W),
notIn(Z,Visited),
S1 is S+W,
path(Z,Y,[Z|Visited],Cs, S1, P).
经过这些修改，您的示例查询如下所示：
?- start_end_path_weight(ori,dest,X,W).
W = 8,
X = [ori,a,b,dest] ? ;
no
以下是如何改进 (is)/2：
:- use_module(library(clpfd)).
start_end_path_weight(X,Y,[X|Cs], P) :-
path(X,Y,[X],Cs, 0, P).
path(X,X,_,[], P, P).
path(X,Y,Visited,[Z|Cs], S, P) :-
connection(X,Z,W),
notIn(Z,Visited)
maplist(dif(Z),Visited),
S1 is S+W
S1 #= S+W, S1 #=< P,
path(Z,Y,[Z|Visited],Cs, S1, P).
限制最大成本？ 小菜一碟！ 考虑以下 InterRail 子集...
...翻译成序言...
connection(X,Y,D) :- to_fro_dt(X,Y,D). connection(X,Y,D) :- to_fro_dt(Y,X,D). to_fro_dt(aberdeen,edinburgh,140). to_fro_dt(amsterdam,berlin,370). to_fro_dt(amsterdam,brussels,113). to_fro_dt(amsterdam,cologne,158). to_fro_dt(amsterdam,copenhagen,675). to_fro_dt(ancona,igoumenitsa,900). to_fro_dt(athens,patras,215). to_fro_dt(athens,/* for consistency */piraeus,5). to_fro_dt(athens,thessaloniki,265). to_fro_dt(bar,belgrade,572). to_fro_dt(barcelona,madrid,170). to_fro_dt(barcelona,marseille,280). to_fro_dt(barcelona,sevilla,330). to_fro_dt(barcelona,valencia,175). to_fro_dt(bari,igoumenitsa,570). to_fro_dt(bari,rome,240). to_fro_dt(belfast,dublin,240). to_fro_dt(belgrade,bucharest,730). to_fro_dt(belgrade,budapest,450). to_fro_dt(belgrade,sarajevo,540). to_fro_dt(belgrade,skopje,525). to_fro_dt(belgrade,sofia,485). to_fro_dt(bergen,oslo,405). to_fro_dt(berlin,cologne,260). to_fro_dt(berlin,hamburg,95). to_fro_dt(berlin,munich,345). to_fro_dt(berlin,prague,275). to_fro_dt(berlin,warsaw,365). to_fro_dt(bern,frankfurt,235). to_fro_dt(bern,lyon,230). to_fro_dt(bern,milan,240). to_fro_dt(birmingham,edinburgh,265). to_fro_dt(birmingham,holyhead,245). to_fro_dt(birmingham,london,105). to_fro_dt(bologna,florence,37). to_fro_dt(bologna,milan,60). to_fro_dt(bordeaux,lyon,375). to_fro_dt(bordeaux,madrid,660). to_fro_dt(bordeaux,paris,180). to_fro_dt(bristol,london,105). to_fro_dt(brussels,cologne,107). to_fro_dt(brussels,frankfurt,190). to_fro_dt(brussels,london,140). to_fro_dt(brussels,paris,85). to_fro_dt(bucharest,budapest,830). to_fro_dt(bucharest,sofia,540). to_fro_dt(bucharest,zagreb,365). to_fro_dt(budapest,ljubljana,540). to_fro_dt(budapest,vienna,165). to_fro_dt(budapest,warsaw,680). to_fro_dt(budapest,zagreb,365). to_fro_dt(catania,naples,450). to_fro_dt(cologne,frankfurt,82). to_fro_dt(copenhagen,hamburg,270). to_fro_dt(copenhagen,oslo,520). to_fro_dt(copenhagen,stockholm,315). to_fro_dt(cork,dublin,165). to_fro_dt(dublin,holyhead,195). to_fro_dt(dublin,westport,210). to_fro_dt(edinburgh,glasgow,50). to_fro_dt(faro,lisbon,230). to_fro_dt(florence,rome,95). to_fro_dt(florence,venice,123). to_fro_dt(frankfurt,hamburg,220). to_fro_dt(frankfurt,munich,190). to_fro_dt(frankfurt,paris,235). to_fro_dt(hamburg,munich,350). to_fro_dt(helsinki,rovaniemi,570). to_fro_dt(helsinki,turku,110). to_fro_dt(heraklion,piraeus,390). to_fro_dt(igoumenitsa,patras,360). to_fro_dt(istanbul,sofia,775). to_fro_dt(istanbul,thessaloniki,720). to_fro_dt(kiruna,stockholm,960). to_fro_dt(lisbon,madrid,610). to_fro_dt(lisbon,porto,165). to_fro_dt(ljubljana,venice,540). to_fro_dt(ljubljana,zagreb,140). to_fro_dt(london,paris,135). to_fro_dt(london,penzance,305). to_fro_dt(lyon,marseille,100). to_fro_dt(lyon,paris,115). to_fro_dt(madrid,'málaga',165). to_fro_dt(madrid,pamplona,180). to_fro_dt(madrid,santander,270). to_fro_dt(madrid,santiago,425). to_fro_dt(madrid,sevilla,155). to_fro_dt(madrid,valencia,105). to_fro_dt(marseille,montpellier,140). to_fro_dt(marseille,nice,155). to_fro_dt(milan,munich,465). to_fro_dt(milan,nice,310). to_fro_dt(milan,venice,155). to_fro_dt(munich,prague,365). to_fro_dt(munich,venice,425). to_fro_dt(munich,vienna,250). to_fro_dt(naples,rome,70). to_fro_dt(oslo,stockholm,380). to_fro_dt(paris,rennes,120). to_fro_dt(piraeus,rhodes,710). to_fro_dt(prague,vienna,270). to_fro_dt(prague,warsaw,520). to_fro_dt(sarajevo,zagreb,550). to_fro_dt(skopje,sofia,540). to_fro_dt(skopje,thessaloniki,240). to_fro_dt(sofia,thessaloniki,400). to_fro_dt(split,zagreb,335). to_fro_dt(stockholm,/* added by hand */turku,725). to_fro_dt(stockholm,'östersund',420). to_fro_dt(trondheim,'östersund',230). to_fro_dt(venice,vienna,440). to_fro_dt(vienna,warsaw,450).
...让我们找到
的路径从维也纳开始
包括至少 2 个其他城市
并且累计旅行时间为 10 小时（或更短）！
?- W #=< 600, Path = [_,_,_|_], start_end_path_weight(vienna, _, Path, W). W = 530, Path = [vienna,budapest,zagreb] ; W = 595, Path = [vienna,munich,berlin] ; W = 440, Path = [vienna,munich,frankfurt] ; W = 522, Path = [vienna,munich,frankfurt,cologne] ; W = 600, Path = [vienna,munich,hamburg] ; W = 545, Path = [vienna,prague,berlin] ; W = 563, Path = [vienna,venice,florence] ; W = 600, Path = [vienna,venice,florence,bologna] ; W = 595, Path = [vienna,venice,milan] ; false. % terminates universally fast