1

オランダ国旗問題のソルバーを作ろうとしています。基本的には、リストを与えられて、赤白青の順に並べ替えたいと思います。赤、白、青は述語 (つまり、赤 (x)、白 (x) など) によって定義されます。現在、次のコードがあります。

red(1).
white(2).
blue(3).

dutch(Xs,Ys):- 
    getRed(Xs,[], Red), getWhite(Xs,[],White), getBlue(Xs,[],Blue), 
    append([], Red, Y1), append(Y1, White, Y2), append(Y2, Blue, Ys).

getRed([],Rs,Rs).
getRed([X|Rest], Acc, Rs) :- red(X), getRed(Rest, [X,Acc] , Rs).
getRed([X|Rest], Acc, Rs) :- getRed(Rest, Acc, Rs).

getWhite([],Rs,Rs).    
getWhite([X|Rest], Acc, Rs) :- white(X), getWhite(Rest, [X,Acc], Rs).
getWhite([X|Rest], Acc, Rs) :- getWhite(Rest, Acc, Rs).

getBlue([],Rs,Rs).
getBlue([X|Rest], Acc, Rs) :- blue(X), getBlue(Rest, [X,Acc], Rs).    
getBlue([X|Rest], Acc, Rs) :- getBlue(Rest, Acc, Rs).

私の出力は次のようになります。

?- dutch([1,2,3],R).
R = [1, [], 2, [], 3, []]
R = [1, [], 2, []]
R = [1, [], 3, []]
R = [1, []]
R = [2, [], 3, []]
R = [3, []]
R = []

私が欲しいのは、それが次のようになることです：

R = [1, 2, 3]

出力を希望どおりにするためにいくつかの方法を試しましたが、どこにも近づくことができませんでした。

編集:すべての可能なセットを並べ替え、セットが「オランダの旗」の順序であるかどうかを評価するブルート フォース ソリューションを使用して解決できるようです。しかし、より良い解決策はありますか？

4

2 に答える 2

1

純粋なソリューション

序文

既存のソリューションに純粋なリレーショナルソリューションを追加したいと考えています。

理想的には、すべての方向でProlog 述語を使用できます。次に、これを可能にする実装を示します。基準に従ってインスタンス化されたリストをソートできるだけでなく、ソリューションを生成して、部分的にインスタンス化されたソリューションを完成させることもできます。 .

これを行うために、メタ述語if_/3fromを使用していlibrary(reif)ます。

具体化された述語

私はあなたの述語の具体化されたバージョンから始めます。また、よりわかりやすい名前を自由に使用しred、色を示しますwhite。blue

red(R, T) :- =(R, red, T)。

white(W, T) :- =(W, ホワイト, T)。

blue(B, T) :- =(B, 青, T)。

(=)/3を使用していることに注意してくださいlibrary(reif)。

DCG を使用してリストを記述する

次に、純粋に便宜上、目的のサブシーケンスを記述するために表記を使用しています。

reds([]) --> [].
レッド(Rs) -->
        [R]、
        { if_(red(R), Rs = [R|Rest], Rs = Rest) },
        レッズ（レスト）。

whites([]) --> [].
whites(Ws) --> [W],
        { if_(white(W), Ws = [W|Rest], Ws = Rest) },
        白人（残り）。

ブルース([]) --> [].
ブルース(Bs) --> [B],
        { if_(blue(B), Bs = [B|Rest], Bs = Rest) },
        ブルース（レスト）。

簡単な演習として、これをより簡潔にすることにします。

解決

これらの構成要素を使用して、全体的なソリューションを表現できます。

オランダ語 (色、Ds) :-
        フレーズ（赤（Rs）、色）、
        フレーズ（白（Ws）、色）、
        フレーズ(ブルース(Bs)、カラーズ)、
        フレーズ（（Rs、Ws、Bs）、Ds）。

例

もちろん、これは次のような単純なインスタンス化されたケースで機能します。

?- オランダ語([赤,白,青], Ds).
Ds = [赤、白、青] ;
間違い。

ポイント: これは、すべての引数が変数である最も一般的なケースでも機能します。

?-長さ(Cs, _), オランダ語(Cs, Ds) .
Cs = Ds、Ds = [] ;
Cs = Ds、Ds = [赤] ;
Cs = Ds、Ds = [白] ;
Cs = Ds、Ds = [青] ;
Cs = [_G1322]、
Ds = []、
dif(_G1322, 青),
dif(_G1322, 白),
dif(_G1322, 赤) ;
Cs = Ds、Ds = [赤、赤] ;
Cs = Ds、Ds = [赤、白] ;
Cs = Ds、Ds = [赤、青] ;
Cs = [赤, _G1340],
Ds = [赤],
dif(_G1340, 青),
dif(_G1340, 白),
dif(_G1340, 赤) .

さらに目標を追加することで、このクエリを特殊化して、現在生成されている具体的なソリューションを観察できます。

?- 長さ(Cs, _), Cs = [_,_,_|_] , オランダ語(Cs, Ds),地面(Cs) .
Cs = Ds、Ds = [赤、赤、赤] ;
Cs = Ds、Ds = [赤、赤、白] ;
Cs = Ds、Ds = [赤、赤、青] ;
Cs = [赤、白、赤]、
Ds = [赤、赤、白] ;
Cs = [赤、青、赤]、
Ds = [赤、赤、青] .

これを、ソリューションを公平に列挙するために使用できない他の回答と比較してください。

?-長さ(Xs, _), Xs = [_,_,_|_], オランダ語(Xs, Ys) .
Xs = Ys、Ys = [1, 1, 1] ;
Xs = Ys、Ys = [1, 1, 1, 1] ;
Xs = Ys、Ys = [1, 1, 1, 1, 1] ;
Xs = Ys、Ys = [1, 1, 1, 1, 1, 1] ;
Xs = Ys、Ys = [1, 1, 1, 1, 1, 1, 1] .

概要

を保持することにより、あらゆる方向で使用できる、より一般的な論理プログラムが得られます。

確かに、あなたはこの一般性を求めていません。しかし、私たちがそれをしている間、なぜそれを放棄するのですか?

于 2016-10-26T09:10:37.517 に答える
0

コードに 2 つのエラーが表示されます。

1) 終端句getRed([],Rs,Rs), getWhite([],Rs,Rs),getBlue([],Rs,Rs)値の結果として空のリストを受け入れる (が にRs等しい場合[]); それらを次のように書き直すことをお勧めします

getRed([],Rs,Rs)   :- Rs \= [].
getWhite([],Rs,Rs) :- Rs \= [].
getBlue([],Rs,Rs)  :- Rs \= [].

2）受け入れ句（X検索された色の場合）で、パイプを使用する必要がある場合は、アキュムレータにカンマで追加します（[X,Acc];べき（[X|Acc]）;私はそれらを次のように書き直すことをお勧めします

getRed([X|Rest], Acc, Rs)   :- red(X),   getRed(Rest, [X|Acc], Rs).
getWhite([X|Rest], Acc, Rs) :- white(X), getWhite(Rest, [X|Acc] , Rs).
getBlue([X|Rest], Acc, Rs)  :- blue(X),  getBlue(Rest, [X|Acc], Rs).

トピック外:Red空のリストに追加する理由はありません。結果リスト ( Y1) はRedそれ自体です。単純化することをお勧めします

append([], Red, Y1), append(Y1, White, Y2), append(Y2, Blue, Ys)

次のように

append(Red, White, Mid), append(Mid, Blue, Ys)

- - 編集 - -

あなたが正確に何を望んでいるのかはわかりませんが、3 番目のバージョン句の 3 番目のエラーが疑われます: whenXは累積されません。

X検索された色ではないことを確認するためにチェックを追加する必要があると思います。次のように書き直すことをお勧めします

getRed([X|Rest], Acc, Rs)   :- \+ red(X),   getRed(Rest, Acc, Rs).
getWhite([X|Rest], Acc, Rs) :- \+ white(X), getWhite(Rest, Acc, Rs).
getBlue([X|Rest], Acc, Rs)  :- \+ blue(X),  getBlue(Rest, Acc, Rs).

--- 編集 2 ---

getRed/3あなたの, getWhite/3andgetBlue/3句にアキュムレータが必要だとは思いません。

引数が 2 つのみのバージョンを提案します

red(1).
white(2).
blue(3).

dutch(Xs,Ys):- 
    getRed(Xs, Red), getWhite(Xs, White), getBlue(Xs, Blue), 
    append(Red, White, Mid), append(Mid, Blue, Ys).

getRed([],[]).
getRed([X|Rest], [X|Rs]) :- red(X),    getRed(Rest, Rs).
getRed([X|Rest], Rs)     :- \+ red(X), getRed(Rest, Rs).

getWhite([],[]).
getWhite([X|Rest], [X|Rs]) :- white(X),    getWhite(Rest, Rs).
getWhite([X|Rest], Rs)     :- \+ white(X), getWhite(Rest, Rs).

getBlue([],[]).
getBlue([X|Rest], [X|Rs]) :- blue(X),    getBlue(Rest, Rs).
getBlue([X|Rest], Rs)     :- \+ blue(X), getBlue(Rest, Rs).
于 2016-10-25T13:33:15.443 に答える