Prolog中的简化旅行推销员 [英] Simplified Travelling Salesman in Prolog
问题描述
我已经浏览了类似的问题,但是找不到与我的问题相关的任何内容.我正在努力寻找一个算法或一组循环",使用数据库
I've looked through the similar questions but can't find anything that's relevant to my problem. I'm struggling to find an algorithm or set of 'loops' that will find a path from CityA
to CityB
, using a database of
distance(City1,City2,Distance)
事实.到目前为止,我设法做到的是,但是它总是在write(X),
处回溯,然后完成最终的迭代,这是我希望它执行的操作,但仅在一定程度上进行.
facts. What I've managed to do so far is below, but it always backtracks at write(X),
and then completes with the final iteration, which is what I want it to do but only to a certain extent.
例如,我不希望它打印出任何死胡同的城市名称,或使用最终迭代.我希望它基本上建立从CityA
到CityB
的路径,并在路径上写下它要去的城市的名称.
For example, I don't want it to print out any city names that are dead ends, or to use the final iteration. I want it to basically make a path from CityA
to CityB
, writing the name of the cities it goes to on the path.
我希望有人能帮助我!
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).
推荐答案
我试图演示如何实现您正在从事的工作,以便您可以更好地了解其工作方式.因此,由于您的OP并不是很完整,所以我享有一些自由!这是我正在使用的事实:
I tried to demonstrate how you can achieve what you're working on so that you can understand better how it works. So since your OP wasn't very complete, I took some liberties ! Here are the facts I'm working with :
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 .它基本上称为工作谓词,它有两个累加器(一个累加点,一个累加的距离).
Here is the predicate we will call to find our paths, get_road/4. It basically calls the working predicate, that has two accumulators (one for the points already visited and one for the distance we went through).
get_road(Start, End, Visited, Result) :-
get_road(Start, End, [Start], 0, Visited, Result).
这是工作谓词,
get_road/6 :get_road(+开始,+结束,+航点,+ DistanceAcc,-Visited,-TotalDistance):
第一条说明如果我们的第一个点和最后一个点之间有一条路,我们可以在这里结束.
Here is the working predicate,
get_road/6 : get_road(+Start, +End, +Waypoints, +DistanceAcc, -Visited, -TotalDistance) :
The first clause tells that if there is a road between our first point and our last point, we can end here.
get_road(Start, End, Waypoints, DistanceAcc, Visited, TotalDistance) :-
road(Start, End, Distance),
reverse([End|Waypoints], Visited),
TotalDistance is DistanceAcc + Distance.
第二个子句告诉我们,如果在我们的第一个点和一个中间点之间有一条路,我们可以走这条路,然后求解get_road(intermediate,end).
The second clause tells that if there is a road between our first point and an intermediate point, we can take it and then solve get_road(intermediate, end).
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.
希望对您有所帮助.
这篇关于Prolog中的简化旅行推销员的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!