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

たとえば、迷路を表し、0 が開いていて 1 が壁であるプロローグでマトリックスを既に作成しています (開始位置は (2|1) で、ゴールは (4|1) にあります)。

11111
10001
10101

さらに、 という名前の句を定義しましたmazeDataAt(Coord_X, Coord_Y, MazeData, Result)。これにより、特定の位置での行列の値が得られます。

ここのところ。しかし今、そのアルゴリズムをプロローグに実装する際に問題があります。私はすでに「汚い方法」を試しました（ネストされたifステートメントを使用して1つずつ翻訳します）が、複雑さが増し、プロローグで行う方法ではないと思います。

だから私はこれを試しました：

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

しかし、この試みは期待どおりには機能しませんでした。

実際、これは上記のアルゴリズムの正しいプロローグ実装ですか? このアプローチが本当に迷路を通る道を見つけるかどうかを確認するにはどうすればよいですか? したがって、パスを記録したり、ソリューション パスを取得したりするにはどうすればよいですか (上記のアルゴリズムでパスをマーク/マーク解除することによって何が行われますか)。

ご助力ありがとうございます！

//アップデート

あなたの答えに感謝します！私の問題を解決するために、よりプロローグのようなソリューション（こちらを参照）を採用しました。だから私は今持っています：

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

私は彼の答えの1つでボリスから解決策を取りました：

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)、無限ループに入ります。それが機能するような簡単なものを試してみると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

次の 2 点に注意してください。

  1. 正方形からの可能な移動に 4 引数ルールを使用しています (したがって、それに応じて調整します)
  2. で魔法が起こりnext_wます。がd呼び出されると、 を使用next_wして 4 つの可能な隣接四角形を生成し (上/下/左/右しか移動できないと仮定)、次に、この四角形が実際にウェイポイントであるかどうかを確認します。もう両方の方法をチェックする必要はありません。

別の編集: 完全なコード

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

2つの可能な解決策が得られるはずです。

言い換えれば、あなたの問題はセミコロンだと思います。可能なすべての移動を明示的に作成するため、これは不要になりました。

于 2013-04-18T12:55:24.410 に答える