10

このXKCDコミックで言及されている問題に対するこのECLiPSeソリューションを見ました。私はこれを純粋なPrologに変換しようとしました。

go:-
    Total = 1505,
    Prices = [215, 275, 335, 355, 420, 580],
    length(Prices, N),
    length(Amounts, N),
    totalCost(Prices, Amounts, 0, Total),
    writeln(Total).

totalCost([], [], TotalSoFar, TotalSoFar).
totalCost([P|Prices], [A|Amounts], TotalSoFar, EndTotal):-
    between(0, 10, A),
    Cost is P*A,
    TotalSoFar1 is TotalSoFar + Cost,
    totalCost(Prices, Amounts, TotalSoFar1, EndTotal).

これが、思いつくことができる最良の/最も宣言的な解決策ではないと思います。誰かが改善のための提案がありますか？前もって感謝します！

4

2 に答える 2

6

あなたはSWI-Prologに言及しているので、なぜですか

?- use_module(library(clpfd)).

とlibrary(lambda)

?- Total = 1505, Prices = [215, 275, 335, 355, 420, 580],
   maplist(\P^A^M^(P*A #= M, A #>=0),Prices,Amounts,Ms), sum(Ms, #=, Total).

これを述べると、リスト内のすべての変数はAmounts有限の範囲内にあります。そのため、上限について「計算を行う」必要はありません (これはとにかくうまくいかないことがよくあります)。具体的な解決策を確認するには、labeling/2 が必要です。

?- Total = 1505, Prices = [215, 275, 335, 355, 420, 580],
   maplist(\P^A^M^(P*A #= M, A #>=0),Prices,Amounts,Ms), sum(Ms, #=, Total),
   labeling([], Amounts).
    Total = 1505,
    Prices = [215,275,335,355,420,580],
    Amounts = [1,0,0,2,0,1],
    Ms = [215,0,0,710,0,580] ;
    Total = 1505,
    Prices = [215,275,335,355,420,580],
    Amounts = [7,0,0,0,0,0],
    Ms = [1505,0,0,0,0,0].
于 2011-06-07T14:43:59.747 に答える
5

生成とテストのアプローチは、数日以上の経験を持つ Prolog プログラマーなら誰でも理解できるはずです。ここにいくつかのマイナーな調整があります：

go(Amounts) :-
    Prices = [580, 420, 355, 335, 275, 215],
    totalCost(Prices, Amounts, 0, 1505),
    write(Amounts), nl.

totalCost([], [], Total, Total).
totalCost([P|Prices], [A|Amounts], SoFar, Total):-
    Upper is (Total-SoFar)//P,
    between(0,Upper,A),
    SoNear is SoFar + P*A,
    totalCost(Prices, Amounts, SoNear, Total).

go/0をgo/1に変更して、Prolog エンジンがバックトラックしてすべてのソリューション (2 つある) を生成するようにしました。length/2の呼び出しは省略できます。totalCost/4がリスト Amounts を作成して Price と同じ長さになるようにするためです。write/1とnl/0を使用して、もう少し移植性を高めました。

totalCost/4では、いくつかの変数/引数の名前を短くし、accumulator 引数に少し冗談めかした名前を付けました。アキュムレータが目的の Total を超えないというチェックを課した方法では、元の between/3への呼び出しを使用しますが、定数の代わりに計算された上限を使用します。私のマシンでは、実行時間が数分から数秒に短縮されました。

追加:上記のコメントで述べたことをここで言及する必要があります。メニュー項目は現在、最も高価なものから最も安価なものへと並べられています。SWI-Prolog のtime/1述語を使用すると、これにより作業が 1,923 回の推論から 1,070 回の推論に削減されることがわかります。主な (速度の) 改善は、すべての項目に対して 0 から 10 の範囲ではなく、A で計算された境界を使用することによるものです。

time((go(A),false)).

複合ゴールを囲む余分な括弧に注意してください。そうしないと、SWI-Prolog は未定義のtime/2述語を呼び出していると見なします。

于 2011-06-06T17:41:15.487 に答える