2

このサイトで他の同様の質問と回答を読みましたが、特定の問題に対する回答が見つからないようです。Prolog で迷路をエンコードしようとしています。領域 0 から領域 1 または領域 3 に自由に移動できます。領域 3 から、領域 0、領域 4、領域 5 などに自由に移動できます。長さ 7 のすべてのパスを最初から最後（0から14まで）。SWI-Prolog で次の方法で問題をエンコードしました。

    region(0).
    region(1).
    region(2).
    region(3).
    region(4).
    region(5).
    region(6).
    region(7).
    region(8).
    region(9).
    region(10).
    region(11).
    region(12).
    region(13).
    region(14).
    region(15).

    connection(0,1).                %connection exists between these two regions
    connection(0,3).        
    connection(1,2).
    connection(1,8).
    connection(1,7).
    connection(3,4).
    connection(3,5).
    connection(7,9).
    connection(7,5).
    connection(7,8).
    connection(5,6).
    connection(8,10).
    connection(8,11).
    connection(11,12).
    connection(11,13).
    connection(13,15).
    connection(13,14).

    double_link(X,Y) :-
       region(X),
       region(Y),
       ( connection(X,Y) | connection(Y,X) ). %can go from region X to region Y, and vice versa

    path(X,Y) :-
       double_link(X,Y).
    path(X,Y) :-
       double_link(X,Z),
       path(Z,Y).

実行するpath(14,0).と が得られtrueます。ただし、path(0,14) を実行すると、ローカル スタック領域が不足します。それがどのようになるかわかりません。助けてくれてありがとう！

4

2 に答える 2

4

あなたが言った：

実行するpath(14,0).と が得られtrueます。

それは真実の半分です！ああ、それよりもさらに少ない！実際、true一度ではなく何度も取得できます。

?- path(14,0).
true ;
true ;
true ;
true ;
true ;
true ...

;タイピングやSPACE常時入力を避ける簡単な方法があります。単純にゴールを使用してfalseください。

    ?- パス(14,0)、偽
    **ループ**

falseそして今、そのような目標をプログラムに追加することもできます。このようにして、プログラムの一部を除外しています。残りの部分がまだループしている場合は、そこに問題があるはずです。これは私が得たものです：

地域 (0) :- false。
% ...
地域 (12) :- false。
リージョン(13)。
リージョン(14)。
地域 (15) :- false。

接続 (0,1) :- false。
% ...
接続 (13,15) :- false。
接続(13,14)。

double_link(X,Y) :-
   地域(X)、
   地域(Y),
   ( 接続(X,Y) ; 接続(Y,X) )。

path(X,Y) :- false、
    double_link(X,Y)。
パス (X、Y) :-
   double_link(X,Z),
   パス (Z、Y)、偽。

したがって、この残りの部分では、そのループに対処する必要があります。これで一目瞭然ですよね？

于 2014-08-26T15:56:18.253 に答える
2

問題が発生するのは、迷路内をぐるぐる回れるからです。たとえば、迷路には接続があります0 - 1 - 7 - 5 - 3 - 0。検索が盲目的にこれらの円をたどらないようにするための対策を講じていません。

通常のアプローチは、既にアクセスした領域 (最初は空) を含むパス述語に引数を追加することです。次に、そのリストにない新しい場所に行くときに確認する必要があります（例X：）。Xnonmember(X,Visited)

于 2014-08-26T14:31:20.770 に答える