I希望您能在Prolog中实现迷宫求解算法。因此,我搜索了一些迷宫求解算法,并找到了以下内容:http://www.cs.bu.edu/teaching/alg/maze/
寻找路径(x,y):
进一步地,我定义了一个名为的子句,它可以给我在某个位置上矩阵的值。
到目前为止都还好。但现在我在尝试在Prolog中实现这个算法时遇到了问题。我已经尝试过“脏方法”(使用嵌套的if语句逐个翻译),但随着复杂度的增加,我认为这不是在Prolog中解决问题的方式。
所以我尝试了这个:
但是这次尝试并没有像预期的那样有效。
实际上,这是上述算法的正确Prolog实现吗?我该如何确定这种方法是否真的能在迷宫中找到路径?因此,我该如何记录路径或获取解决方案路径(通过在上述算法中标记/取消标记路径完成)?
非常感谢您的帮助!
//更新
感谢您的答案!我采用了更像Prolog的解决方案(请参见此处)来解决我的问题。所以现在我有:
到目前为止,这个程序可以工作。我认为我明白了为什么Prolog的方式更好。但现在我还有一个小问题。我想让我的知识库是“动态的”。我不能为迷宫中的每个路标定义所有边缘。因此,我编写了一个叫做
但是,如果我尝试询问
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
进一步地,我定义了一个名为的子句,它可以给我在某个位置上矩阵的值。
到目前为止都还好。但现在我在尝试在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的解决方案(请参见此处)来解决我的问题。所以现在我有:
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的方式更好。但现在我还有一个小问题。我想让我的知识库是“动态的”。我不能为迷宫中的每个路标定义所有边缘。因此,我编写了一个叫做
is_adjacent([X1, Y1], [X2, Y2])
的子句,当 [X1, Y1]
是 [X2, Y2]
的邻居时,它就为真。我还有一个列表 Waypoints = [[2, 1], [2, 2]| ...]
,其中包含迷宫中所有可能的路标。现在问题来了:我该如何使用它来使我的知识库“动态”?这样我就可以在 go
子句中使用它来查找路径了吗?感谢您的帮助! //更新2 现在,我已经将所有路标作为事实得到了。w(2, 1).
w(2, 2).
...
我从Boris在他的一个回答中采用了解决方案:
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
中得到解决方案路径。
我做错了什么?我忘了什么?
d(From, To)
的事实表示可能的转换。 - user1812457