我想在 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) 的子句，它为我提供了矩阵在某个位置的值。
到目前为止。但是现在我在序言中实现该算法时遇到了问题。我已经尝试过“肮脏的方式”(通过使用嵌套的 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).
但是这次尝试并没有像预期的那样奏效。
实际上，这是上述算法的正确序言实现吗？ 我如何才能看到这种方法是否真的找到了穿过迷宫的路径？ 因此我如何记录路径或获取解决方案路径(通过标记/取消标记上述算法中的路径来完成什么)？
非常感谢您的帮助!
//更新
感谢您的回答!我采用了更像序言的解决方案(参见 here)来解决我的问题。所以我现在有:
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 中获得解决方案路径。
我做错了什么？我忘记了什么？
最佳答案
(此答案使用与 this answer 相同的寻路算法)
编辑 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
注意两点:
- 我正在使用一个 4 参数规则来计算可能的正方形移动(因此相应地进行调整)
- 奇迹发生在
next_w中。当调用d时，它使用next_w生成四个可能的相邻方 block (假设你只能上/下/左/右)然后检查这个方 block 是否是确实是一个航路点。您将不再需要检查这两种方式。
另一个编辑:完整代码
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).
你应该得到两种可能的解决方案。
换句话说，我认为你的问题是分号；它不再是必需的，因为您明确地创建了所有可能的移动。
关于algorithm - Prolog迷宫求解算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16076778/