简化的旅行推销员

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（ +启动， +end， +Waypoints， +distanceacc， - visited， - totaldAltance）：
第一个条款告诉我们，如果我们的第一点和最后一点之间有一条道路，我们可以在这里结束。

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.

我希望这对您有帮助。

Answer 2

请将纯部分与不纯的部分分开（I/O，喜欢 write/1, nl/0 但是也 (==)/2 和 (\==)/2）。只要它们完全与您的纯代码交织在一起，您就不会期望太多。

可能您需要在起点，终点和两者之间的路径之间存在关系。

那路应该是无环 还是您允许周期?

确保元素 X 不在列表中 Xs 使用目标 maplist(dif(X),Xs).您不需要进一步的辅助谓词就可以使其成为一个很好的关系！

Answer 3

您应该将成功的列表返回为all_possible_path中的OUT变量。然后写出该列表。不要在相同的过程中同时执行两者。