1

したがって、これは、これらのコインに特定の値を使用して、運ぶコインの最小数を計算するプログラムです。プログラムは動作しますが、遅すぎます... 値の長さを 7 以下に置き換えると動作します... しかし 8 以上になると、本当に非常に遅くなります。このプログラムを高速化する方法はありますか?

% LIBRARIES NEEDED FOR FUNCTION TO WORK
:- lib(ic).
:- lib(ic_global).
:- lib(branch_and_bound).

questionSix(Values, Coins) :-
    init_vars(Values, Coins),
    coin_cons(Values, Coins, Pockets),
    clever_cons(Values, Coins),
    Min #= sum(Coins),
    minimize((labeling(Values), labeling(Coins), check(Pockets)), Min).

init_vars(Values, Coins) :-
    length(Values, 8),
    occurrences(5, Values, 1),
    Values :: 1..99,
    increasing(Values),
    length(Coins, 8),
    Coins :: 0..99.

increasing(List) :-
    ( fromto(List, [This, Next | Rest], [Next | Rest], [_])
    do
        This #< Next
    ).

clever_cons(Values, Coins) :-
    ( fromto(Values, [V1 | NV], NV, []), 
      fromto(Coins, [N1 | NN], NN, [])
     do
        ( NV = [V2 | _]
            -> N1*V1 #< V2;
            N1*V1 #< 100
        )
    ).

coin_cons(Values, Coins, Pockets) :-
    ( for(Price, 1, 99),
    foreach(CoinsforPrice, Pockets),
    param(Coins, Values)
    do
        price_cons(Price, Coins, Values, CoinsforPrice)
    ).

price_cons(Price, Coins, Values, CoinsforPrice) :-
    ( foreach(V, Values), foreach(C, CoinsforPrice), foreach(Coin, Coins),
    foreach(Prod, ProdList)
    do
        Prod = V*C,
        0 #=< C,
        C #=< Coin
    ),
    Price #= sum(ProdList).

check(Pockets) :-
    ( foreach(CoinsforPrice, Pockets)
    do
        once(labeling(CoinsforPrice))
    ).

どんな助けでも大歓迎です！ありがとう！

4

1 に答える 1

1

最初の観察:のlabeling(Coins)前に置くlabeling(Values)と、時間が劇的に改善されます。大まかに言えば、この問題ではコインの価値よりもコインの数が重要だからです。

2 番目の観察: 許可する値の数に関係なく、7 枚未満のコインを取得することはできません。これは、プログラムを 7 つの値で実行すると、すべてのコインが最適解で 1 回使用されることがわかるからです。したがって、値が 7 つを超える場合は、そのうちの 7 つだけが使用されるか、コインの数が 7 つを超えて、最適な解が得られません。

これらの観察を念頭に置いて、変更することができます

minimize((labeling(Values), labeling(Coins), check(Pockets)), Min).

に

bb_min((labeling(Coins), labeling(Values), check(Pockets)), Min, bb_options{from:7}).
于 2014-05-22T20:42:31.210 に答える