Prolog中的简化旅行商问题

Question

Prolog中的简化旅行商问题

prologbacktrackingtraveling-salesmanprolog-dif

9

我已经查阅了类似的问题，但是没有找到与我的问题相关的任何内容。我正在努力寻找一种算法或一组“循环”，以使用数据库从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).

- g.a.kilby

3个回答

4

请将纯部分与不纯部分（I/O，如write/1，nl/0，但也包括(==)/2和(\==)/2）分开。只要它们完全交织在您的纯代码中，您就不能指望太多。

可能您希望有一个起点、终点和路径之间的关系。

该路径应该是无环的吗？

为了确保元素X不会出现在列表Xs中，请使用目标maplist(dif(X),Xs)。您不需要任何其他辅助谓词来使其成为一个好的关系！

- false

一旦一个城市被使用，它就不能在同一路径中再次使用。因此是无环的。另外，您所说的纯净和不纯净是什么意思？ - g.a.kilby

我在上面添加了一个解释。 - false

1

你应该在 all_possible_paths 函数中返回一个成功的列表作为输出变量，然后将该列表写出。不要在同一个过程中同时执行这两个操作。

- projectshave

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- m09 · Accepted Answer

我试图演示如何实现你正在努力解决的问题，以便你能更好地理解它是如何工作的。因此，由于你的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(+起点, +终点, +途经点, +距离累计, -访问过的点, -总距离) :
第一个子句表明如果我们的第一个点和最后一个点之间有一条道路，我们可以在此结束。

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

第二条款说明了如果我们的第一个点和中间点之间有一条道路，我们可以沿着这条道路走，并解决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.

我希望这对你有所帮助。