4

私は現在、Prologで解決したい次の問題を抱えています。これは簡単な例であり、Java /C/その他で簡単に解決できます。私の問題は、Javaの考え方に縛られすぎて、Prologの論理力を利用する方法で実際に問題を定式化できないと信じていることです。

問題は..

左または右を指す6つの矢印のセットがあります。それらが次の開始構成にあると仮定しましょう。

->
<-
->
<-
->
<-

これで、2つの矢印が隣り合っている限り、それらを切り替えることができます。私の目標は、どの一連のアクションによって矢印の初期構成が次のようになるかを発見することです。

<-
<-
<-
->
->
->

問題を定式化する私の最初の試みは..

right(arrow_a).
left(arrow_b).
right(arrow_c).
left(arrow_d).
right(arrow_e).
left(arrow_f).

atPosition(1, arrow_a).
atPosition(2, arrow_b).
atPosition(3, arrow_c).
atPosition(4, arrow_d).
atPosition(5, arrow_e).
atPosition(6, arrow_f).

これは、矢印の初期構成が何であるかをPrologに伝えます。しかし、どうすれば追加のロジックを挿入できますか？たとえば、どのように実装しswitchArrows(Index)ますか？Prologでこのような初期条件を述べるのは正しいですか？後で、たとえばarrow_a位置6に設定しようとすると、干渉しませんatPosition(6, arrow_a)か？

4

4 に答える 4

7

問題は、構成間の一連の移行として定式化できます。まず、単一の構成をどのように表現するかを考えてください。これを行うには、リストを使用できます。たとえば、[->,<-,->,<-,->,<-] を使用して初期構成を表すことができます。単一の移動は、step(State0, State) として使用される関係 step/2 で記述でき、2 つの隣接する矢印を反転することによって互いに「到達可能」な 2 つの構成間の関係を記述します。一般に、非決定論的です。メインの述語は、初期状態から目的のターゲット状態に至る一連の状態遷移を記述します。(構成の) リストを記述したいので、DCG が適しています。

solution(State0, Target) -->
    (    { State0 == Target } -> []
    ;    { step(State0, State1) },
         [State1],
         solution(State1, Target)
    ).

そして、次のように、反復的な深化を使用して、解決策が存在する場合はそれを見つけます。

?- length(Solution, _), phrase(solution([->,<-,->,<-,->,<-], [<-,<-,<-,->,->,->]), Solution).

良い点は、指定された長さのすべてのシーケンスが試行され、ターゲット状態にまだ到達できない場合、Prolog が自動的にバックトラックすることです。step/2 を実装するだけで完了です。

于 2010-10-05T20:49:01.273 に答える
5

完全な解決策がすでに投稿されているので、ここに私のものがあります：

solution(State0, Target) -->
    (    { State0 == Target } -> []
    ;    { step(State0, State1) },
         [State1],
         solution(State1, Target)
    ).

flip(->, <-).
flip(<-, ->).

step([], []).
step([A|Rest0], [A|Rest]) :- step(Rest0, Rest).
step([A0,A1|Rest], [B0,B1|Rest]) :- flip(A0, B0), flip(A1, B1).

クエリの例:

?- length(Solution, _), phrase(solution([->,<-,->,<-,->,<-], [<-,<-,<-,->,->,->]), Solution).
Solution = [[->, <-, ->, <-, <-, ->],
            [->, <-, ->, ->, ->, ->],
            [->, ->, <-, ->, ->, ->],
            [<-, <-, <-, ->, ->, ->]].

反復的な深化が使用されるため、これよりも短い解 (4 ステップ未満) は不可能であることがわかっています。

また、あなたが言ったことについて、一般的なコメントがあります。

これは簡単な例で、Java/C などで簡単に解決できます。私の問題は、Java の考え方に縛られすぎて、Prolog の論理力を利用する方法で実際に問題を定式化できないと考えていることです。

個人的には、この例は、Java プログラマーなどの最初から期待できるものをすでにはるかに超えていると思います。この問題を Java/C などで解決してみて、どこまで到達できるかを確認してください。私の経験では、学生が「Javaの考え方に縛られすぎている」などと言うと、Javaでも問題を解決できません。Prolog は異なりますが、それを Java で解決する方法について明確なアイデアがあったとしても、それを直接 Prolog に変換できないほどの違いはありません。私のソリューションでは、Prolog の組み込み検索メカニズムを使用していますが、そうする必要はありません。Java の場合と同じように、検索を自分で実装できます。

于 2010-10-06T14:12:25.933 に答える
1

これが私の解決策です：

solution(Begin, End, PrevSteps, [Step | Steps]) :-
    Step = step(Begin, State1),
    Step,
    forall(member(step(S, _), PrevSteps),
           State1 \= S
          ), % prevent loops
    (   State1 == End
    ->  Steps = []
    ;   solution(State1, End, [Step | PrevSteps], Steps)
    ).

rev(->,<-).
rev(<-,->).

step([X,Y|T], [XX,YY|T]) :- rev(X,XX), rev(Y, YY).
step([A,X,Y|T], [A,XX,YY|T]) :- rev(X,XX), rev(Y, YY).
step([A,B,X,Y|T], [A,B,XX,YY|T]) :- rev(X,XX), rev(Y, YY).
step([A,B,C,X,Y|T], [A,B,C,XX,YY|T]) :- rev(X,XX), rev(Y, YY).
step([A,B,C,D,X,Y], [A,B,C,D,XX,YY]) :- rev(X,XX), rev(Y, YY).


run :-
    solution([->,<-,->,<-,->,<-], [<-,<-,<-,->,->,->],[],Steps),
    !,
    forall(member(Step,Steps),writeln(Step)).

見つかった解決策は最適ではなく、最初に機能するものだと思いますが、可能な限り最初の解決策のみを見つけます。

于 2010-10-06T12:30:51.593 に答える
0

マットのコードを水銀に変換することができました:

:- module arrows.

:- interface.

:- import_module io.

:- pred main(io, io).
:- mode main(di, uo) is cc_multi.

:- implementation.

:- import_module list, io, int.

:- type arrow ---> (->); (<-).

:- mode solution(in, in, in, in, out, in) is cc_nondet.
solution(State0, Target, MaxDepth, CurrentDepth) -->
    {CurrentDepth =< MaxDepth},
    (    { State0 = Target } -> []
    ;    { step(State0, State1) },
         [State1],
         solution(State1, Target, MaxDepth, CurrentDepth + 1)
    ).

flip(->, <-).
flip(<-, ->).

step([], []).
step([A|Rest0], [A|Rest]) :- step(Rest0, Rest).
step([A0,A1|Rest], [B0,B1|Rest]) :- flip(A0, B0), flip(A1, B1).

main -->
    (({
    member(N, 1..10),
        solution([->,<-,->,<-,->,<-], [<-,<-,<-,->,->,->], N, 0, Solution, [])
    }) 
    -> print(Solution)
    ; print("No solutions")
    ).

mmc --infer-all arrows.m でコンパイルして署名と決定論を推測する

于 2010-10-06T16:20:14.487 に答える