Prolog 图找不到路径

Question

我在通过 Prolog 程序链接新西兰小镇时遇到问题。我得到了一组数据，这些数据是道路、它们的往返和距离。我认为第一个问题是直截了当的，但我已经为此苦苦思索了几个小时，但运气不佳，我所要做的就是打印出一条给定路线的可行路径。为什么下面的解决方案找不到正确的路径？

road('Wellington', 'Palmerston North', '143').
road('Palmerston North', 'Wanganui', '74').
road('Palmerston North', 'Napier', '178').
road('Palmerston North', 'Taupo', '259').
road('Wanganui', 'Taupo', '231').
road('Wanganui', 'New Plymouth', '163').
road('Wanganui', 'Napier', '252').
road('Napier', 'Taupo', '147').
road('Napier', 'Gisborne', '215').
road('New Plymouth', 'Hamilton', '242').
road('New Plymouth', 'Taupo', '289').
road('Taupo', 'Hamilton', '153').
road('Taupo', 'Rotorua', '82').
road('Taupo', 'Gisborne', '334').
road('Gisborne', 'Rotorua', '291').
road('Rotorua', 'Hamilton', '109').
road('Hamilton', 'Auckland', '126').

route(Current, Finish, []) :- route(Current, Finish, [Current]).    
route(Current, Finish, _) :- Current==Finish.    
route(Current, Finish, Visits) :- traverse(Current, Next, Visits), route(Next, Finish, Visits).

traverse(Current, Next, [Next|_]) :- road(Current, Next, _).

每当我调用：route('Wellington','Napier', X). 尽管有一条路径 Wellington->Palmerston North->Napier 但它还是失败了。在此先感谢，我知道我可能在做一些愚蠢的事情，因为我是 Prolog 的新手。

Answer 1

我认为您有一些不需要的额外条款：

route(Current, Current, [Current]).    
route(Current, Finish, [Current|T]) :- road(Current, Next, _),
                                       route(Next, Finish, T).

示例：

?- route('Wellington','Napier', X).
X = ['Wellington', 'Palmerston North', 'Wanganui', 'Napier'] ;
X = ['Wellington', 'Palmerston North', 'Napier'] ;
false.

请注意，road('X','Y'). 形式的定义子句表示从 'X' 到 'Y' 有一条路，反之则不然：

?- route('Palmerston North','Wellington',L).
false.

所以你声明的道路是单向的。

如果添加 foe example 子句：

road('Palmerston North','Wellington', '143').

那么如果你查询：

?- route('Wellington','Wellington', X).
X = ['Wellington'] ;
X = ['Wellington', 'Palmerston North', 'Wellington'] ;
X = ['Wellington', 'Palmerston North', 'Wellington', 'Palmerston North', 'Wellington'] ;
X = ['Wellington', 'Palmerston North', 'Wellington', 'Palmerston North', 'Wellington', 'Palmerston North', 'Wellington']

然后继续....所以它陷入了圈子。要解决这个问题，您可以这样写：

route2(X,Y,L,N):- length(L,N),route(X,Y,L),sort(L,L).

所以你给出路径的长度（因为它会因为循环而永远搜索）并使用 sort(L,L).

只接受不同城市的路径

Prolog 图找不到路径

Prolog graph not finding path

graph-theory

prolog