1

ですから、私には取り組むべき課題があり、私が混乱していることが1つあります。これは私が達成しようとしていることと同様の問題です。私がこれらのルールを持っているとしましょう：

size(3).
size(5).
size(7).
size(1).
size(2).
size(9).

そして、値3を取得して5と比較し、3を格納して7と比較し、次に1と比較し、1を格納して2と比較することにより、最小サイズを見つけたいと思います...値1を返します。

高次の手順なしでそれを行うことができる唯一の方法は、size（X）値がまだあり、サイズ変数を変更するたびに、何らかの形でバックトラックすることです。ただし、新しい最小値をバックトラックして保存する方法がわかりません。誰かが私を正しい軌道に乗せるのを手伝ってくれるかどうか疑問に思いました。

4

1 に答える 1

3

あなたの任務は、あなたにPrologの独特の制御フローについて考えさせることを目的としており、実際、あなたは今や要点に達しています。ソリューションをコーディングし、説明コメントを配置しました。省略記号を入力してコードを完成させます

find_min_size(MinSize) :-
    size(Hypothesis),
    !,  % without this cut the minimum is obtained more times...
    find_min_size(Hypothesis, MinSize).

find_min_size(SoFar, MinSize) :-
    % when I should keep searching?
    ...

% the exhaustive search come to end!
find_min_size(MinSize, MinSize).

私は、Prologでは「高次の手順」なしでO（N）のパフォーマンスを得ることができるとは思いません（findallなどを意味しますか？）。上記のコードはO（N ^ 2）で実行されます。size / 1はバインドされていない変数で再起動するため、インデックス作成は役割を果たしません。

興味深いO（N）の代替手段は、失敗駆動型ループと、@ falseがcall_nthを導入するときに非常によく説明した技術を使用することです（また、ここでフォローアップを参照してください）。これらはすべて、Prologの「不純な」領域にありますが...

ここで障害駆動ループを編集します

find_min_size(MinSize) :-
    State = (_, _),
    (   size(V),
        arg(1, State, C),
        ( ( var(C) ; V < C ) -> U = V ; U = C ),
        nb_setarg(1, State, U),
        fail
    ;   arg(1, State, MinSize)
    ).
于 2012-11-27T07:41:23.407 に答える