1

我必须找到两个州之间的路线，并且我到达了这里，但到目前为止我遇到了关于堆栈外的错误帮助我

% state 1 is border of state 2
% borders(A , B). 
borders(sasktchewan, alberta).
borders(saskatchewan, manitoba).
borders(saskatchewan, nwt).
borders(alberta, british_columbia).
borders(alberta, saskatchewan).
borders(alberta, nwt).
borders(british_coumbia, yukon).
borders(british_coumbia, nwt).
borders(british_coumbia, alberta).
borders(nwt, saskatchewan).
borders(nwt, alberta).
borders(nwt, british_columbia).
borders(nwt, yukon).
borders(nwt, manitoba).
borders(manitoba, saskatchewan).
borders(manitoba, nwt).

route( A, B, [ go(A,B) ] ) :-   borders( A, B ). 
route( A, B, [ go(A,Z) | ZtoB ] ) :-   borders( A, Z ),   route( Z, B, ZtoB ).
4

1 回答 1

2

问题是你没有在你已经去过的地方记账。现在说你正在寻找从sasktchewan到manitoba。Prolog 会将其评估为：

(sasktchewan) <--------------
 `--(alberta)                \
     `--(british_columbia)   |
        |--(yukon) fail!     |
        `--(nwt)             |
           `-(sasktchewan)---/

现在，由于您不告诉 prolog 您不能进入循环，因此它将继续附加(sasktchewan) -> (alberta) -> (nwt)到路径并且永远找不到目标。

演示：

?- route(sasktchewan,manitoba,L).
L = [go(sasktchewan, alberta), go(alberta, saskatchewan), go(saskatchewan, manitoba)] ;
L = [go(sasktchewan, alberta), go(alberta, saskatchewan), go(saskatchewan, manitoba), go(manitoba, nwt), go(nwt, manitoba)] ;
L = [go(sasktchewan, alberta), go(alberta, saskatchewan), go(saskatchewan, nwt), go(nwt, manitoba)] ;
L = [go(sasktchewan, alberta), go(alberta, nwt), go(nwt, manitoba)] ;
L = [go(sasktchewan, alberta), go(alberta, nwt), go(nwt, saskatchewan), go(saskatchewan, manitoba)] ;
L = [go(sasktchewan, alberta), go(alberta, nwt), go(nwt, manitoba), go(manitoba, saskatchewan), go(saskatchewan, manitoba)] ;

你需要做的是使用一个累加器，列出你去过的所有地方。每次您从访问该城市的那一刻起进行会员检查，您就会崩溃。因此：

%We start a route with being in city A
route(A, B, L) :-
    route(A, B,[A], L).

%In case we find a city with a border, don't hesitate and go to the city!
route( A, B,_,[go(A,B)]) :-
    borders(A,B).
%Too bad, now looking for an extra city
route(A,B,Been,[go(A,Z)|ZtoB]) :-
    borders(A,Z), %hahaa, we can access city Z
    \+ member(Z,Been), %hold on! Did we already visit Z. No! we didn't
    route(Z,B,[Z|Been],ZtoB). %Log city Z and look for a root from Z to B

这不是最优的：一旦访问城市a在一条路径上失败，如果您选择另一条路径到该城市，它也会失败。您可以使用non-bactrackable store 来维护您访问过的城市列表，以便将其转换为O(n 2 )算法。实施取决于方言。

于 2015-02-23T17:23:28.283 回答