时间戳

首页 > 解决方案 > Prolog 迷宫问题：代码给出了从头到尾的无限路径并且不会回溯

prolog - Prolog 迷宫问题：代码给出了从头到尾的无限路径并且不会回溯

问题描述

我正在尝试使用回溯解决 Prolog 中的迷宫。

我的问题是，当我运行程序时，它第一次正确运行，但之后它将结束位置作为起始位置并不断从那里寻找路径，因此进入无限循环。当 2 个位置之间不存在路径时，它可以正常工作。我已经尝试了很多东西，但似乎没有任何效果。这是我的代码：

path(Dest, Dest, _, [], _) :- !.

path([Row0,Col0],[Row1,Col1],M,Path,1) :-
    next_move([Row0,Col0],[Rnew,Cnew]),
    is_available(Rnew, Cnew,Ret),

    write(Rnew),
    write(Cnew),

    not(member([Rnew, Cnew], M)),
    path([Rnew, Cnew], [Row1, Col1], [[Rnew,Cnew]|M], Path, Ret).

path([X0,Y0], [X1,Y1], [[X0,Y0]|M], [[X,Y]|Path], 0) :-
    path([X,Y],[X1,Y1],M,Path,1).

样本输出：

?- solves([1,1],[1,7],P).
P = [[1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7]] ;
P = [[1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [2, 6], [2, 7], [2|...], 
    [...|...]|...] ;
P = [[1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [2, 6], [2, 7], [2|...], 
    [...|...]|...] ;
P = [[1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [2, 6], [2, 7], [2|...], 
    [...|...]|...] .

执行程序时，如果两个位置之间存在路径，则应显示所有路径。否则它应该返回 false 。正如您在上面看到的，我的代码进入无限循环并不断生成路径。

请帮忙，因为我在 Prolog 方面不是很有经验。谢谢。

标签： prologmaze

解决方案

谓词的第一个子句path/5及其第二个子句中的递归调用是错误的。它应该是：

path(Dest, Dest, _, [], _) :- !.

path([Row0,Col0],[Row1,Col1],M,[[Rnew,Cnew]|Path],1) :-
    next_move([Row0,Col0],[Rnew,Cnew]),
    is_available(Rnew, Cnew,Ret),

    write(Rnew),
    write(Cnew),

    \+ member([Rnew, Cnew], M),
    path([Rnew, Cnew], [Row1, Col1], [[Rnew,Cnew]|M], Path, Ret).

此外，使用 ISO Prolog 标准\+/1谓词而不是not/1旧谓词。

推荐阅读