时间戳

首页 > 解决方案 > Prolog寻路在找到答案后陷入循环

prolog - Prolog寻路在找到答案后陷入循环

问题描述

我的代码可以在给定网格中从 A 点到 B 点找到所有可能的解决方案，我的问题是在找到所有解决方案之后，它将开始永远来回追踪。我想这是合法的，因为所有条件都满足了。但是，我很难给出一个可以阻止这种情况的条件。有什么帮助吗？

move([X,Y], e, [X1,Y]) :- X1 is X+1.
move([X,Y], n, [X,Y1]) :- Y1 is Y+1.
move([X,Y], s, [X,Y1]) :- Y1 is Y-1.

safe([Xn,Yn],[Xg,Yg]) :-
  Xg >= Xn,
  Xn > 0,
  Yg >= Yn,
  Yn > 0. %next state must be whit-in grid otherwise false

%% solve([X,Y],[TargetX,TargetY],[Xg,Yg],[FirstMove|OtherMoves])

solve([X,Y],[X,Y],_,[]) :- !.
solve([X,Y],[Xt,Yt],[Xg,Yg],[Fm|Om]) :-
  move([X,Y],Fm,[Xn,Yn]),
  safe([Xn,Yn],[Xg,Yg]),
  solve([Xn,Yn],[Xt,Yt],[Xg,Yg],Om).

输出：

?- solve([1,1],[2,2],[2,2],P).
P = [e, n] ;
P = [n, e] ;
P = [n, s, e, n] ;
P = [n, s, n, e] ;
P = [n, s, n, s, e, n] ;
P = [n, s, n, s, n, e] ;
P = [n, s, n, s, n, s, e, n] ;
P = [n, s, n, s, n, s, n, e] ;
P = [n, s, n, s, n, s, n, s, e|...] ;
P = [n, s, n, s, n, s, n, s, n|...] ;

标签： prolog

解决方案

solve(A,B,C,D):-
  solve(A,B,C,D,[]).

solve([X,Y],[X,Y],_,[],_) :- !.
solve([X,Y],[Xt,Yt],[Xg,Yg],[Fm|Om],Chars) :-
  move([X,Y],Fm,[Xn,Yn]),
  \+ member(Fm,Chars),
  safe([Xn,Yn],[Xg,Yg]),
  solve([Xn,Yn],[Xt,Yt],[Xg,Yg],Om, [Fm|Chars]).

?- solve([1,1],[2,2],[2,2],P).
P = [e, n] ;
P = [n, e] ;
false.

我所做的只是引入另一个变量Chars来保存访问过的节点（？），每次尝试移动时，它都会通过询问是否Fm不是列表的成员Chars（\+ member(Fm,Chars)）来检查是否已经采取了这种移动。Fm被添加到Chars递归调用中。

推荐阅读