我想在Prolog中实现迷宫求解算法 . 因此我搜索了一些迷宫求解算法并发现了以下内容:http://www.cs.bu.edu/teaching/alg/maze/
FIND-PATH(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实现吗?我怎么能看到这种方法是否真的找到了通过迷宫的路径?因此,我如何记录路径或获取解决方案路径(通过在上面的算法中标记/取消标记路径来完成的操作)?
非常感谢您的帮助!
//更新
谢谢你的回答!我采用了一个更像prolog的解决方案(见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).
到目前为止,这是有效的 . 我想我理解为什么prolog的方式要好得多 . 但现在我还有一个小问题 .
我希望我的知识基础是"dynamic" . 我无法为迷宫中的每个航路点定义所有边缘 . 因此我写了一个名为 is_adjacent([X1, Y1], [X2, Y2])
的子句,当 [X1, Y1]
是 [X2, Y2]
的邻居时,这是正确的 .
我还有一个列表 Waypoints = [[2, 1], [2, 2]| ...]
,其中包含迷宫中所有可能的航路点 .
现在问题是:我如何使用它来 Build 我的知识基础"dynamic"?这样我可以在 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
的解决方案路径 .
我究竟做错了什么?我忘记了什么?
1 回答
(这个答案使用与this answer相同的路径查找算法)
EDIT 2
实际上,如果您的输入只是矩形矩阵的哪些单元格不是墙,那么您需要以某种方式将其转换为“您可以从A到B”的规则 . 如果您的航路点是:
等,然后您可以将您最初指向的算法转换为Prolog规则,如下所示:
注意两件事:
我正在使用一个4参数规则来进行正方形的可能移动(因此相应调整)
魔法发生在
next_w
. 当d
被调用时,它使用next_w
生成四个可能的邻居方块(假设你只能上/下/左/右),然后检查这个方格是否确实是一个路点 . 您不需要再检查两种方式 .ANOTHER EDIT: Full code
你可以用它来打电话
你应该得到两个可能的解决方案 .
换句话说,我认为你的问题是分号;它不再是必要的,因为你明确地创建了所有可能的动作 .