4

そのため、Prolog でこの問題を解決しようとする課題が与えられましたが、先生は基本的なことしか説明しておらず、これは本質的に Prolog の唯一のプロジェクトです。私はそれを考えすぎているように感じます.そして、彼は初めてのPrologプログラムとして期待しすぎているだけです.

問題は次のとおりです。これを解決するにはどうすればよいですか?

次の文章題を解く Prolog プログラムを書きなさい。ソリューションの一部として、パドラーが最初にリストされた状態で、すべての交差点を出力する必要があります。

トム、ジャック、ビル、ジムは、2 人乗りのカヌーで川を渡らなければなりませんでした。
川の左岸から右岸への 3 回の渡河ではそれぞれ 2 人がカヌーに乗り、右岸から左岸への 2 回の渡河ではそれぞれ 1 人がカヌーに乗っていました。トムは、他の誰かが彼と一緒にカヌーに乗っているとき、パドルを漕ぐことができませんでした。
ビル以外の誰かが彼と一緒にカヌーに乗っているとき、ジャックは漕ぐことができませんでした。一人一人が少なくとも 1 回の横断をパドリングしました。

これは私がこれまでに持っているものですが、「機能する」とはいえ、誰もが少なくとも一度はパドルすることを保証するものではありません.

state(tom(Side),jim(Side),jack(Side),bill(Side),c(Side)).
initial(state(tom(l),jim(l),jack(l),bill(l),c(l))).
final(state(tom(r),jim(r),jack(r),bill(r),c(r))).

canoe(P):-P=p.
canoe(P,C):-P=p,C=c.

bad(state(tom(W),jim(X),jack(Y),bill(Z),c(C))):-
    C=l,(W=c;X=c;Y=c;Z=c).

move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W1),jim(X),jack(Y),bill(Z),c(C1))):-
    ((canoe(W1),W=r,W=C,C1=m);(canoe(W),W1=l,W1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W),jim(X1),jack(Y),bill(Z),c(C1))):-
    ((canoe(X1),X=r,X=C,C1=m);(canoe(X),X1=l,X1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W),jim(X),jack(Y1),bill(Z),c(C1))):-
    ((canoe(Y1),Y=r,Y=C,C1=m);(canoe(Y),Y1=l,Y1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W),jim(X),jack(Y),bill(Z1),c(C1))):-
    ((canoe(Z1),Z=r,Z=C,C1=m);(canoe(Z),Z1=l,Z1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W1),jim(X1),jack(Y),bill(Z),c(C1))):-
    ((canoe(X1,W1),W=l,W=X,W=C,C1=m);
    (canoe(X,W),W1=r,W1=X1,W1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W1),jim(X),jack(Y),bill(Z1),c(C1))):-
    ((canoe(Z1,W1),W=l,W=Z,W=C,C1=m);
    (canoe(Z,W),W1=r,W1=Z1,W1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W),jim(X1),jack(Y1),bill(Z),c(C1))):-
    ((canoe(X1,Y1),Y=l,Y=X,Y=C,C1=m);
    (canoe(X,Y),Y1=r,Y1=X1,Y1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W),jim(X1),jack(Y),bill(Z1),c(C1))):-
    ((canoe(Z1,X1);canoe(X1,Z1)),
     Z=l,Z=X,Z=C,C1=m);
    ((canoe(Z,X);canoe(X,Z)),Z1=r,Z1=X1,Z1=C1).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W),jim(X),jack(Y1),bill(Z1),c(C1))):-
    ((canoe(Y1,Z1);canoe(Z1,Y1)),
     Y=l,Y=Z,Y=C,C1=m);
    ((canoe(Y,Z);canoe(Z,Y)),Y1=r,Y1=Z1,Y1=C1).

find(Path):-initial(S),rez(S,Path).
bkt(State,Path,[Path|State]):-final(State).
bkt(State,Path,Sol):-move(State,Next),not(bad(Next)),
    not(member(Next,Path)),bkt(Next,[Path|Next],Sol).
rez(State,Sol):-bkt(State,[State],Sol).
start:-find(D),writef('%w\n',D).
4

1 に答える 1

2

(この回答は遅すぎるかもしれませんが、これは非常に古典的な問題/パズルであり、多くのバリエーションがあるため、問題を少し分解してみるとまだ役立つと思います.)

上記の回答で述べたように、リファクタリングを行い、この問題に対してよりシンプルで管理しやすいモデルを作成することをお勧めします。これが意味することは、たとえば、誰かがあなたのコードを統合するために「すぐに変更」するように頼んだ場合、たとえばパズルの 5 人目の人だとしたら、上記のコードをリファクタリングするのはあまり楽しくないということです。

リスト内の4人の男性の構成をエンコードすることから始めることができます-これはアイデアを提供するための1つのアプローチです-「l」または「r」を使用して、誰かが左側にいるか右側にいるかを指定します川岸の。これにより、次のような初期状態が得られます。

% Tom, Jack, Bill, and Jim are all on the left side
[l,l,l,l]

そして、目標の状態に到達したいと考えています:

% Tom, Jack, Bill, and Jim are all on the right side
[r,r,r,r]

これにより、非常に読みやすく、理解しやすいモデルが得られます (imo)。

次に、川岸間の実際の輸送をどのようにエンコードするかについてもう少し考えることができます。どの人物がどこにいるかを指定するリスト構成を作成したので、ある構成を別の構成に変換できる Prolog 述語が必要になります。まあ言ってみれば：

transport(StartState,[Persons],EndState)

さて、実装のために、(現在のコードで行っているように) すべての可能な動きを明示的に一致させる代わりに、何が起こっているのかを正確に一般化することを試みることは常に良い考えです (Prolog の楽しい部分:))。

複雑すぎるコードを一度に書くのではなく、問題を細かく分割します。

% Facts defining a crossing of the river
cross(l,r).
cross(r,l).

% Transport example for Tom
transport([X,Jack,Bill,Jim],[tom],[Y,Jack,Bill,Jim]) :- cross(X,Y).

ご覧のように、'transport' を非常に単純な方法で定義しました。Tom は自分で川を渡るだけであることがわかっているため、クロス ファクトを使用して彼の位置を変更します。(ジャック、ビル、ジムは、それらの人々がいる川岸を示すために「l」または「r」のいずれかを示す単なる変数であることに注意してください。トムは自分で横断するだけなので、これらの変数は変更されません!)。これをさらに抽象的に書くこともできますが、'tom' とは特に一致しませんが、この例では単純にしようとしています。

もちろん、どの交差が有効でどれが無効かを表現する必要があります。あなたの質問から：「川の左岸から右岸への 3 つの交差点のそれぞれで、カヌーは 2 人であり、右から左岸への 2 つの交差点のそれぞれで、カヌーは 1 人でした。」これらの条件は、'transport' 述語を使用して非常に簡単にコーディングできます。これは、初期状態 (最初の引数) が、左から右に横断しているか、またはその逆であるかを示し、2 番目の引数で横断する人物のリストを指定するためです。つまり、交差点の方向と乗客の数はすでにわかっており、これらの条件をここに書き留めるのは少し簡単に思えます。

次：「ビル以外の誰かが彼と一緒にカヌーに乗っていたとき、ジャックはパドルを漕ぐことができませんでした。」繰り返しますが、これは既に非常に簡単に「トランスポート」にまとめて記述されています (この特定の条件について気にしない情報を除外するためにワイルドカードを使用していることに注意してください。例を示すだけです。):

% Transport example for Jack (Persons length = min 1 - max 2)
transport([_,_,_,_],Persons,[_,_,_,_]) :-
    length(Persons,2),
    ( member(jack,Persons) ->
      member(bill,Persons)
    ;
      * other condition(s) *
    ).

% Alternative with pattern matching on Persons
transport([_,_,_,_],[A,B],[_,_,_,_]) :-
    * if jack is A or B, then bill is the other one *

別の簡単な例: 「Tom は他の誰かが彼と一緒にカヌーに乗っているとき、パドルを漕ぐことができませんでした。」

% Tom cannot peddle in a team of 2
transport([_,_,_,_],Persons,[_,_,_,_]) :-
    length(Persons,2),
    \+ member(tom,Persons).

お気づきかもしれませんが、モデルで非常に簡単に表現できるように、問題をほとんど完全に小片に分解しており、実際のソルバーを作成するのにそう遠くはありません。ただし、オンラインで見つけるのに十分なコード例があり、ここでこれ以上コードを作成する必要はないと思います。

古典的なキツネ - ガチョウ - 豆/キャベツのパズルを検索すると、さらにインスピレーションが得られます。

皆さん、頑張ってください！

于 2016-03-19T14:34:34.657 に答える