时间戳

首页 > 解决方案 > Prolog中的寻路递归耗尽内存

prolog - Prolog中的寻路递归耗尽内存

问题描述

我编写了这个 prolog 程序来查找网格中所有可能的路径：

travel([X,Y],[X,Y1]) :- Y1 is Y+1.
travel([X,Y],[X,Y0]) :- Y0 is Y-1.
travel([X,Y],[X1,Y]) :- X1 is X+1.

move([X,Y],n,[X,Y1]) :- travel([X,Y],[X,Y1]).
move([X,Y],s,[X,Y0]) :- travel([X,Y],[X,Y0]).
move([X,Y],e,[X1,Y]) :- travel([X,Y],[X1,Y]).

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

%% 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， [X,Y] 是当前位置。所以我的结束状态是当前位置等于目标位置时。但是，当我运行它时，我得到了内存不足的错误。知道我做错了什么吗？任何帮助表示赞赏！

?- solve([1,2],[4,2],[3,4],P).
ERROR: Stack limit (1.0Gb) exceeded
ERROR:   Stack sizes: local: 0.5Gb, global: 0.4Gb, trail: 29.0Mb
ERROR:   Stack depth: 951,746, last-call: 0%, Choice points: 1,903,475
ERROR:   Possible non-terminating recursion:
ERROR:     [951,746] user:solve([length:2], [length:2], [length:2], _114212638)
ERROR:     [951,745] user:solve([length:2], [length:2], [length:2], [length:1|_114212704])

?- length(P,4),solve([1,2],[4,2],[3,4],P).
false.

?- length(P,5),solve([1,2],[4,2],[3,4],P).
false.

标签： prolog

解决方案

您的程序在南北运动之间无限循环。move尝试删除and中的南子句travel，它会起作用。

要调试这是如何发生的，请尝试使用trace并查看对您的递归调用，solve您可以看到发生了什么。

   Exit: (15) move([1, 3], n, [1, 4]) ? 
   Call: (15) safe([1, 4], [4, 4]) ? s
   Exit: (15) safe([1, 4], [4, 4]) ? 
   Call: (15) solve([1, 4], [3, 4], [4, 4], _3490) ? 
   Call: (16) move([1, 4], _3804, [_3822, _3828]) ? s
   Exit: (16) move([1, 4], n, [1, 5]) ? 
   Call: (16) safe([1, 5], [4, 4]) ? s
   Fail: (16) safe([1, 5], [4, 4]) ? 
   Redo: (16) move([1, 4], _3804, [_3822, _3828]) ? s
   Exit: (16) move([1, 4], s, [1, 3]) ? 
   Call: (16) safe([1, 3], [4, 4]) ? s
   Exit: (16) safe([1, 3], [4, 4]) ? 
   Call: (16) solve([1, 3], [3, 4], [4, 4], _3806) ? 
   Call: (17) move([1, 3], _4326, [_4344, _4350]) ? s
   Exit: (17) move([1, 3], n, [1, 4]) ? 
   Call: (17) safe([1, 4], [4, 4]) ? s
   Exit: (17) safe([1, 4], [4, 4]) ? 
   Call: (17) solve([1, 4], [3, 4], [4, 4], _4328) ? 
   Call: (18) move([1, 4], _4642, [_4660, _4666]) ? s
   Exit: (18) move([1, 4], n, [1, 5]) ? 
   Call: (18) safe([1, 5], [4, 4]) ? s
   Fail: (18) safe([1, 5], [4, 4]) ?

此外，您似乎正在模式匹配变量名称move :- travel，这也不起作用。move(P1, n, P2)将尝试北和南子句，而不仅仅是第一个子句（尝试move([2, 2], s, X)看看第一个解决方案是北移动）。这将起作用，但使用南子句，您将有无限递归。

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

推荐阅读