Prolog的迷宫求解算法 [英] Prolog maze solving algorithm

问题描述

我想实现的Prolog迷宫求解算法。因此，我搜索了一些迷宫求解算法，发现如下： HTTP：//www.cs .bu.edu /教育/ ALG /迷宫/

I want to implement a maze solving algorithm in Prolog. Therefore i searched for some maze solving algorithms and found the following: http://www.cs.bu.edu/teaching/alg/maze/

Find-PATH（X，Y）：

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 

我已经建立一个矩阵的序言，从而重新presents一个迷宫，其中0是开放的，1是墙壁，例如（起始位置将是（2 | 1），目标位于（4 | 1））：

I already build a matrix in prolog, which represents a maze and where 0 is open and 1 is the wall, for example (starting position would be (2|1) and the goal is located at (4|1)):

11111
10001
10101

更进一步我定义了一个名为条款 mazeDataAt（Coord_X，Coord_Y，MazeData，结果），这使我在一定的位置矩阵的值。

Further more i defined a clause named mazeDataAt(Coord_X, Coord_Y, MazeData, Result), which gives me the value of the matrix on a certain position.

到目前为止。但现在我有执行该算法在序言中的一个问题。我已经尝试过的肮脏的方式（把它翻译逐一通过使用嵌套的if语句），但升级的复杂性，我不认为这是你做的序言的方式。

So far. But now i have a problem implementing that algorithm in prolog. I already tried "the dirty way" (translate it one by one by use of nested if statements), but that escalated complexity and i don't think it's the way you do it in 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).

但这种尝试没有工作像预期的。

But this attempt didn't work like expected.

其实，这是一个正确的序言实现上述算法的？ 我怎么可以看到，如果这个办法真的通过迷宫找到一个路径？ 因此，我怎么能（通过标记/不标记上面的算法中的路径做了什么）记录路径或得到解决途径？

Actually, is this a correct prolog implementation of the algorithm above? How can i see if this approach really finds a path through the maze? Therefore how can i record the path or get the solution path (what is done by marking / unmarking the path in the algorithm above)?

非常感谢您的帮助！

感谢您的回答！我采用了类似的解决方案更序言中（参见<一href="http://stackoverflow.com/questions/8672046/not-member-rule-in-prolog-doesnt-work-as-expected">here)解决我的问题，所以我现在有：

Thanks to your answers! I adopted a more prolog like solution (see here) to solve my problem. So i now have:

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).

到目前为止，这工作。我想我明白为什么序言的方式要好得多。 但现在我有一个小问题就走了。

So far, this works. And i think i understand why the prolog way is much better. But now i have a small problem left.

我希望我的知识基础是动态的。我不能定义为在迷宫中的每一个航路点的所有边缘。因此，我写了一个名为条款 is_adjacent（[X1，Y1]，[X2，Y2]）这是真实的，当 [X1，Y1] 是 [x2，y2] 。

I want my knowledge base be "dynamic". I can't define all the edges for every single waypoint in the maze. Therefore i wrote a clause named is_adjacent([X1, Y1], [X2, Y2]) which is true when [X1, Y1] is a neighbor of [X2, Y2].

我也有一个List 航点= [[2,1]，[2,2] | ...] 包含在我的迷宫中所有可能的航点。

I also have a list Waypoints = [[2, 1], [2, 2]| ...] which contains all possible waypoints in my maze.

现在的问题是：我该如何使用它来使我的知识基础动？这样我就可以在去子句中使用它寻找路径？

Now the question: How can i use this to make my knowledge base "dynamic"? So that i can use it in the go clause for finding the path?

感谢您的帮助！

好了，现在我把所有航点的事实：

Ok, now i got all waypoints as facts:

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

我从鲍里斯的解决方案在他的回答中的一个：

I took the solution from Boris in one of his answers:

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.

在这之后，我更新了去子句，因此它适合：

After that, I updated the go clause, so that it fits:

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).

但是，如果我试着问去（2，1，19，2，R）序言进入一个无限循环。如果我尝试一些更容易喜欢去（2，1，3，8，R）它的工作原理，我得到研究。

But if i try to ask go(2, 1, 19, 2, R) prolog enters an infinite loop. If i try something easier like go(2, 1, 3, 8, R) it works and i get the solution path in R.

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

What am i doing wrong? What did i forget?

推荐答案

（这个答案使用相同的路径寻找算法作为<一个href="http://stackoverflow.com/questions/8672046/not-member-rule-in-prolog-doesnt-work-as-expected">this答案）

(this answer uses the same path finding algorithm as this answer)

编辑2

事实上，如果你输入的就是它是方形矩阵的细胞没有围墙，你就需要以某种方式把此样的规则，你可以从A到B。如果您的航点，则：

Indeed, if your input is just which cells of the rectangular matrix are not walls, you would need to somehow translate this to rules of the kind "you can get from A to B". If your waypoints are then:

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

等等，那么你就可以转换您最初指着成Prolog的规则是这样的算法：

etc, then you can translate the algorithm you originally pointed to into a Prolog rule like this:

% 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论证规则（因此相应调整）
2. 魔术在 next_w 发生。当 D 被调用，它使用了 next_w 生成四种可能的邻居方块（假设你只能去向上/向下/左/右），然后检查此方是否确实是一个航点。你不会需要任何更多的检查两种方式。

1. I am using a 4-argument rule for the possible moves from a square (so adjust accordingly)
2. The magic happens in next_w. When d is called, it uses next_w to generate the four possible neighbor squares (assuming you can only go up/down/left/right) and then checks whether this square is indeed a waypoint. You would not need to check both ways any more.

另一个编辑：全code

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).

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

and you should get the two possible solutions.

在换句话说，我觉得你的问题是分号;它不再是必要的，因为你明确地创造一切可能的行动。

In other words, I think your problem is the semicolon; it is no longer necessary, because you explicitly create all possible moves.

这篇关于Prolog的迷宫求解算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！