Как решить проблему ранца в CLP (B)

Question

Интересно, есть ли способ решить проблему ранца в CLP (B).CLP (B) кажется подходящим, поскольку упаковка элемента может быть смоделирована как логическая переменная.

Пример:
x1, x2, x3, x4, x5 e {0,1}
x1 * 12 + x2 * 2 + x3 * 1 + x4 * 1 + x5 *4 = <15 <br>увеличить x1 * 4 + x2 * 2 + x3 * 2 + x4 * 1 + x5 * 10

Я немного растерялся, как сформулировать условие стороныограниченная вместимость ранца.Похоже, что SWI-Prolog имеет weighted_maximum / 3, что позволило бы оптимизировать.

Изображение с https://en.wikipedia.org/wiki/Knapsack_problem

Answer 1

Вы можете смоделировать ограничения размера (веса), введя новые переменные для учета веса, затем использовать ограничение card для моделирования вместимости рюкзака и, наконец, использовать weighted_maximum/2 для максимизации цели:

:- use_module(library(clpb)).

knapsack_sample([X1,X2,X3,X4,X5], Maximum):-
  knapsack([X1-12/4,X2-2/2,X3-1/2,X4-1/1,X5-4/10], 15, Maximum).

% Data is a list of BucketVar-Value/Weight
knapsack(Data, Capacity, Maximum):-
  buckets(Data, [], [], Buckets, AndEqAll, Weights, Xs),
  sat(card([0-Capacity], Buckets)),
  sat(AndEqAll),
  weighted_maximum(Weights, Xs, Maximum).

buckets([], [EqAll|LEqAll], LBuckets, Buckets, AndEqAll, [], []):-
  foldl(andall, LEqAll, EqAll, AndEqAll),
  append(LBuckets, Buckets).
buckets([X-Count/Weight|Counts], LEqAll, LBuckets, Buckets, AndEqAll, [Weight|Weights], [X|Xs]):-
  length([B|Bs], Count),
  foldl(eqall(X), Bs, (X=:=B), EqAll),
  buckets(Counts, [EqAll|LEqAll], [[B|Bs]|LBuckets], Buckets, AndEqAll, Weights, Xs).

eqall(B, X, Y, (B=:=X)*Y).

andall(X, Y, X*Y).

Так что в вашем примере вы бы назвали рюкзак с Data=[X1-12/4,X2-2/2,X3-1/2,X4-1/1,X5-4/10] и 15 емкостью:

?- knapsack([X1-12/4,X2-2/2,X3-1/2,X4-1/1,X5-4/10], 15, Maximum).
X1 = 0,
X2 = X3, X3 = X4, X4 = X5, X5 = 1,
Maximum = 15.

---

ОБНОВЛЕНИЕ:

На самом деле card ограничения отлично справляются с повторениями, поэтому нет необходимости добавлять новые переменные, и решение становится проще:

knapsack2(Data, Capacity, Maximum):-
  maplist(knap, Data, LBuckets, Weights, Xs),
  append(LBuckets, Buckets),
  sat(card([0-Capacity], Buckets)),
  weighted_maximum(Weights, Xs, Maximum).

knap(X-Value/Weight, Ws, Weight, X):-
  length(Ws, Value),
  maplist(=(X), Ws).

Пример выполнения:

?- knapsack2([X1-12/4,X2-2/2,X3-1/2,X4-1/1,X5-4/10], 15, Maximum).
X1 = 0,
X2 = X3, X3 = X4, X4 = X5, X5 = 1,
Maximum = 15.

Answer 2

Я недавно добавил псевдо / 4 ограничения в свой CLP (B), аналогично ограничению scalar_product / 4 из CLP (FD), которое не будет создавать схему, но вместо этого будет поддерживать ограничение более традиционным способом.Затем код гласит:

knapsack([X1,X2,X3,X4,X5], M) :-
   pseudo([12,2,1,1,4], [X1,X2,X3,X4,X5], =<, 15),
   weighted_maximum([4,2,2,1,10], [X1,X2,X3,X4,X5], M).

Я сравнил с формулировкой карты / 2.В отличие от формулировки псевдо / 4, формулировка карты / 2 создаст контур под капотом.Это относится как к моей системе, так и к SWI-Proilog:

knapsack3([X1,X2,X3,X4,X5], M) :-
   sat(card([0-15],[X1,X1,X1,X1,X1,X1,X1,X1,X1,X1,X1,X1,X2,X2,X3,X4,X5,X5,X5,X5])),
   weighted_maximum([4,2,2,1,10], [X1,X2,X3,X4,X5], M).

Я провел несколько тестов, также измеряя время настройки модели.Новое ограничение псевдо / 4 кажется победителем в этом примере.Вот результаты в моей системе:

Jekejeke Prolog 3, Runtime Library 1.3.8 (May 23, 2019)

?- time((between(1,100,_), knapsack(_,_), fail; true)).
% Up 95 ms, GC 3 ms, Thread Cpu 93 ms (Current 07/05/19 20:03:05)
Yes

?- time((between(1,100,_), knapsack3(_,_), fail; true)).
% Up 229 ms, GC 5 ms, Thread Cpu 219 ms (Current 07/05/19 20:02:58)
Yes

А вот результат в SWI-Prolog:

?- time((between(1,100,_), knapsack3(_,_), fail; true)).
% 8,229,000 inferences, 0.656 CPU in 0.656 seconds (100% CPU, 12539429 Lips)