Пролога: Попытка получить стоимость для данного пути

Question

Я новичок в Пролог

Я пытаюсь в Прологе правило, которое дает мне заданный путь от узла к другому, а также дает мне общий вес пути ,

Мне удалось получить все края пути, но я не могу показать вес пути. Я его дебютировал, и видно, что переменная S суммируется со всем весом пути, но на обратном пути удаляет все элементы. Моя идея заключается в том, чтобы добавить общий вес Р.

Код:

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). 

Спасибо за помощь.

Answer 1

Ваш предикат почти работает. Есть только две проблемы и некоторые детали, которые я хотел бы затронуть. Во-первых, это облегчило бы читаемость для разделения предикатов с разными уровнями. Так давайте поставить одно правило путь/5 перед двумя правилами пути/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) 

Глядя на ваш пример запроса путь/5, кажется, предикат, который вы хотите позвонить, чтобы найти пути , Во второй цели своего единственного правила (с пометкой % <-(1)) вы используете встроенный/2 с выражением S+W с правой стороны. Переменная W появляется здесь впервые и, следовательно, несвязана. Это приводит к ошибке экземпляра, как показано на следующем примере:

?- X is 1+W. 
    ERROR!! 
    INSTANTIATION ERROR- in arithmetic: expected bound value 

Однако, так как вы только используя путь/5 для вызова путь/6 нет необходимости в этой цели. Во-вторых, во втором правиле пути/6 в последней цели вы передаете S+W как аргумент, а не оцениваете его в первую очередь. Для того, чтобы посмотреть, что происходит, давайте уберем цель отмеченные % <-(1) от пути/5 и добавить пример графа к коду:

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 в качестве аргумента. В-третьих, вы используете встроенный (\ ==)/2 в своем предикате notIn/2. Это сравнение преуспевает или терпит неудачу без побочного эффекта или унификации. Это прекрасно, если оба аргумента привязаны к значениям, но являются проблематичными при использовании с несвязанными переменными. Рассмотрим следующие запросы:

?- X=Y, X\==Y. 
no 

терпит неудачу, как и ожидалось, но:

?- X\==Y, X=Y. 
X = Y 

X\==Y успешно, как не оказывает никакого влияния на переменные, так что они могут быть объединены в следующей цели. Это хорошая идея использовать диф/2 вместо:

?- X=Y, dif(X,Y). 
no 
    ?- dif(X,Y), X=Y. 
no 

Наконец, два незначительных предложения: Во-первых, так как вы используете 4-ый аргумент пути/5, чтобы пройти 0 в качестве начального значения для веса, вы также можете сделать это в единственной цели правила, тем самым упростив интерфейс к пути/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 

Answer 2

Вот как улучшить @tas's answer с помощью 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