Как ускорить эту программу? Это расчет держателя монеты

Итак, это программа, которая вычисляет наименьшее количество монет, которые можно носить с определенными значениями на этих монетах. Программа работает, но она слишком медленная... Когда вы заменяете длину значений 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))
    ).

Любая помощь приветствуется! Спасибо!


person user3390252    schedule 22.05.2014    source источник


Ответы (1)


Первое наблюдение: если поставить labeling(Coins) перед labeling(Values), время резко улучшится. Грубо говоря, это потому, что в этой задаче количество монет гораздо важнее, чем стоимость монет.

Второе наблюдение: вы не можете получить меньше 7 монет, независимо от того, сколько значений вы разрешаете. Это потому, что если вы запустите свою программу с 7 значениями, вы увидите, что каждая монета используется один раз в оптимальном решении. Так что если у вас больше 7 значений, то будут использоваться только 7 из них, либо количество монет будет больше 7 и решение будет не оптимальным.

Имея в виду эти наблюдения, вы можете просто изменить

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

to

bb_min((labeling(Coins), labeling(Values), check(Pockets)), Min, bb_options{from:7}).
person Sergii Dymchenko    schedule 22.05.2014