3

我想在 Prolog 中实现一个迷宫求解算法。因此，我搜索了一些迷宫求解算法，发现以下内容：http ://www.cs.bu.edu/teaching/alg/maze/

查找路径（x，y）：

if (x,y outside maze) return false
if (x,y is goal) return true
if (x,y not open) return false
mark x,y as part of solution path
if (FIND-PATH(North of x,y) == true) return true
if (FIND-PATH(East of x,y) == true) return true
if (FIND-PATH(South of x,y) == true) return true
if (FIND-PATH(West of x,y) == true) return true
unmark x,y as part of solution path
return false

我已经在 prolog 中构建了一个矩阵，它代表一个迷宫，其中 0 是开放的，1 是墙，例如（起始位置是 (2|1)，目标位于 (4|1)）：

11111
10001
10101

此外，我还定义了一个名为 的子句mazeDataAt(Coord_X, Coord_Y, MazeData, Result)，它为我提供了某个位置上的矩阵值。

至今。但是现在我在 prolog 中实现该算法时遇到了问题。我已经尝试过“肮脏的方式”（通过使用嵌套的 if 语句一一翻译），但是这增加了复杂性，我认为这不是你在 prolog 中做的方式。

所以我尝试了这个：

isNotGoal(X, Y) :- 
    X = 19, Y = 2.

notOpen(X, Y, MazeData) :-
    mazeDataAt(X, Y, MazeData, 1). 
    
findPath(X, Y, MazeData) :- 
    isNotGoal(X, Y),
    notOpen(X, Y, MazeData),
    increase(Y, Y_New),
    findPath(X, Y_New, MazeData),
    increase(X, X_New),
    findPath(X_New, Y, MazeData),
    decrease(Y, Y_New),
    findPath(X, Y_New, MazeData),
    decrease(X, X_New),
    findPath(X, Y_New, MazeData).

但这种尝试并没有像预期的那样奏效。

实际上，这是上述算法的正确序言实现吗？我怎样才能看到这种方法是否真的找到了一条穿过迷宫的路？因此，我如何记录路径或获取解决方案路径（通过在上面的算法中标记/取消标记路径来完成什么）？

非常感谢您的帮助！

//更新

感谢您的回答！我采用了更类似于 prolog 的解决方案（请参阅此处）来解决我的问题。所以我现在有：

d([2,1], [2,2]).
d([2,2], [1,2]).
d([2,2], [2,3]).

go(From, To, Path) :-
go(From, To, [], Path).

go(P, P, T, T).
go(P1, P2, T, NT) :-
    (d(P1, P3) ; d(P3, P2)),
    \+ member(P3, T),
    go(P3, P2, [P3|T], NT).

到目前为止，这行得通。而且我想我理解为什么序言方式要好得多。但现在我还有一个小问题。

我希望我的知识库是“动态的”。我无法为迷宫中的每个航路点定义所有边缘。因此我写了一个子句，命名is_adjacent([X1, Y1], [X2, Y2])为当[X1, Y1]是的邻居时为真[X2, Y2]。

我还有一个列表Waypoints = [[2, 1], [2, 2]| ...]，其中包含我的迷宫中所有可能的航点。

现在的问题是：我如何使用它来使我的知识库“动态”？这样我就可以在go子句中使用它来查找路径？

谢谢你的帮助！

//更新2

好的，现在我将所有航点作为事实：

w(2, 1).
w(2, 2).
...

我从鲍里斯那里得到了他的答案之一：

d(X0, Y0, X , Y) :-
    w(X0, Y0),
    next_w(X0, Y0, X, Y),
    w(X, Y).

next_w(X0, Y0, X0, Y) :- Y is Y0 + 1.
next_w(X0, Y0, X0, Y) :- Y is Y0 - 1.
next_w(X0, Y0, X, Y0) :- X is X0 + 1.
next_w(X0, Y0, X, Y0) :- X is X0 - 1.

之后，我更新了go条款，使其适合：

go(X1, Y1, X2, Y2, Path) :-
go(X1, Y1, X2, Y2, [], Path).

go(X, Y, X, Y, T, T).
go(X1, Y1, X2, Y2, T, NT) :-
   (d(X1, Y1, X3, Y3) ; d(X3, Y3, X1, Y1)),
\+ member([X3, Y3], T),
go(X3, Y3, X2, Y2, [[X3, Y3]|T], NT).

但是如果我尝试询问go(2, 1, 19, 2, R)prolog 进入一个无限循环。如果我尝试一些更简单go(2, 1, 3, 8, R)的方法，比如它的工作原理，我会在R.

我究竟做错了什么？我忘记了什么？

4

1 回答 1

3

（此答案使用与此答案相同的寻路算法）

编辑 2

实际上，如果您的输入只是矩形矩阵的哪些单元不是墙，您需要以某种方式将其转换为“您可以从 A 到 B”的规则。如果您的航路点是：

w(2,1).
w(2,2).

等等，然后你可以将你最初指向的算法翻译成这样的 Prolog 规则：

% it is possible to move from (X0,Y0) to (X,Y)
d(X0,Y0,X,Y) :-
    w(X0,X0), % you can skip this check if you know for sure
              % that your starting point is a valid waypoint
              % or if you want to be able to start from inside
              % a wall :)
    next_w(X0,Y0,X,Y),
    w(X,Y).
% neighboring waypoints
next_w(X0,Y0,X0,Y) :- Y is Y0+1. % go up I guess
next_w(X0,Y0,X0,Y) :- Y is Y0-1. % go down
next_w(X0,Y0,X,Y0) :- X is X0+1. % go left
next_w(X0,Y0,X,Y0) :- X is X0-1. % go right

注意两点：

  1. 我正在使用 4-argument 规则来处理从正方形的可能移动（所以相应地调整）
  2. 魔术发生在next_w. 当d被调用时，它next_w会生成四个可能的相邻方格（假设你只能上/下/左/右），然后检查这个方格是否确实是一个航路点。您不再需要同时检查两种方式。

另一个编辑：完整代码

w(0,0).
w(0,1). w(1,1). w(2,1). w(3,1). w(4,1). w(5,1).
        w(1,2).         w(3,2).         w(5,2).
        w(1,3).         w(3,3).         w(5,3).
w(0,4). w(1,4). w(2,4).         w(4,4). w(5,4).
                w(2,5). w(3,5). w(4,5).

d(X0,Y0,X,Y) :- next_w(X0,Y0,X,Y), w(X,Y).
next_w(X0,Y0,X0,Y) :- Y is Y0+1.
next_w(X0,Y0,X,Y0) :- X is X0+1.
next_w(X0,Y0,X0,Y) :- Y is Y0-1.
next_w(X0,Y0,X,Y0) :- X is X0-1.

go(X,Y,X,Y,Path,Path).
go(X0,Y0,X,Y,SoFar,Path) :-
    d(X0,Y0,X1,Y1),
    \+ memberchk( w(X1,Y1), SoFar ),
    go(X1,Y1,X,Y,[w(X1,Y1)|SoFar],Path).

你可以调用它

? go(0,0,5,4,[],Path).

你应该得到两种可能的解决方案。

换句话说，我认为你的问题是分号；不再需要，因为您明确创建了所有可能的移动。

于 2013-04-18T12:55:24.410 回答