Prolog的简化旅行推销员

Question

我查看了类似的问题但找不到与我的问题相关的任何内容.我在努力寻找"回路",将找到一个路径的算法或设置CityA到CityB,使用数据库的

distance(City1,City2,Distance)

事实.到目前为止我设法做的是下面,但它总是回溯,write(X),然后在最后的迭代中完成,这是我想要它做的但只是在一定程度上.

例如,我不希望它打印出任何死胡同的城市名称,或者使用最后的迭代.我希望它基本上建立一条路径,CityA在路径上CityB写下它所去的城市的名称.

我希望有人可以帮助我!

all_possible_paths(CityA, CityB) :-
    write(CityA),
    nl,
    loop_process(CityA, CityB).

loop_process(CityA, CityB) :- 
    CityA == CityB.
loop_process(CityA, CityB) :-
    CityA \== CityB,
    distance(CityA, X, _),
    write(X),
    nl,
    loop_process(X, CityB).

Answer 1

我试图演示如何实现您正在进行的工作,以便您更好地了解它的工作原理.所以既然你的OP不是很完整,我就取得了一些自由!以下是我正在使用的事实:

road(birmingham,bristol, 9).
road(london,birmingham, 3).
road(london,bristol, 6).
road(london,plymouth, 5).
road(plymouth,london, 5).
road(portsmouth,london, 4).
road(portsmouth,plymouth, 8).

这是我们将调用以查找路径的谓词get_road/4.它基本上调用工作谓词,它有两个累加器(一个用于已经访问的点,一个用于我们经过的距离).

get_road(Start, End, Visited, Result) :-
    get_road(Start, End, [Start], 0, Visited, Result).

这是工作谓词,
get_road/6:get_road(+ Start,+ End,+ Waypoints,+ DistanceAcc,-Visited,-TotalDistance):
第一个子句告诉我们如果我们的第一个点和最后一个点之间有一条道路,我们可以在这里结束.

get_road(Start, End, Waypoints, DistanceAcc, Visited, TotalDistance) :-
    road(Start, End, Distance),
    reverse([End|Waypoints], Visited),
    TotalDistance is DistanceAcc + Distance.

第二个条款告诉我们如果我们的第一个点和一个中间点之间有一条道路,我们可以接受它然后解决get_road(中间,结束).

get_road(Start, End, Waypoints, DistanceAcc, Visited, TotalDistance) :-
    road(Start, Waypoint, Distance),
    \+ member(Waypoint, Waypoints),
    NewDistanceAcc is DistanceAcc + Distance,
    get_road(Waypoint, End, [Waypoint|Waypoints], NewDistanceAcc, Visited, TotalDistance).

用法如下:

?- get_road(portsmouth, plymouth, Visited, Distance).

收益率:

Visited = [portsmouth, plymouth],
Distance = 8 ;
Visited = [portsmouth, london, plymouth],
Distance = 9 ;
Visited = [portsmouth, plymouth, london, plymouth],
Distance = 18 ;
false.

我希望它对你有所帮助.