设置分区

Question

我试图很好地理解这个问题，但我很吃力。假设我有一个 S={1,2,3,4,5}，一个 L={(1,3,4),(2,3),(4,5),(1,3), (2),(5)} 和另一个具有 L 成本的元组，例如 C={10,20,12,15,4,10}

我想在Prolog中做一个约束程序，以便以最小的成本得到解决问题的解决方案。（在这种情况下，它是我将得到的子集的成本总和）

我的问题是我无法理解我进行建模的方式。我所知道的是我应该选择二进制变量 {0,1} 的模型化，但我几乎不明白我将如何设法通过 Prolog 来表达它。

Answer 1

有一种简单的方法：您可以使用布尔值指标来表示哪些元素构成子集。例如，在您的情况下：

subsets(Sets) :-
    Sets = [[1,0,1,1,0]-10,  % {1,3,4}
            [0,1,1,0,0]-20,  % {2,3}
            [0,0,0,1,1]-12,  % {4,5}
            [1,0,1,0,0]-15,  % {1,3}
            [0,1,0,0,0]-4,   % {2}
            [0,0,0,0,1]-10]. % {5}

我现在使用 SICStus Prolog 及其 Boolean constraint solver 来表达集合封面：

:- use_module(library(lists)).
:- use_module(library(clpb)).

setcover(Cover, Cost) :-
        subsets(Sets),
        keys_and_values(Sets, Rows, Costs0),
        transpose(Rows, Cols),
        same_length(Rows, Coeffs),
        maplist(cover(Coeffs), Cols),
        labeling(Coeffs),
        phrase(coeff_is_1(Coeffs, Rows), Cover),
        phrase(coeff_is_1(Coeffs, Costs0), Costs),
        sumlist(Costs, Cost).

cover(Coeffs, Col) :-
        phrase(coeff_is_1(Col,Coeffs), Cs),
        sat(card([1],Cs)).

coeff_is_1([], []) --> [].
coeff_is_1([1|Cs], [L|Ls]) --> [L], coeff_is_1(Cs, Ls).
coeff_is_1([0|Cs], [_|Ls]) --> coeff_is_1(Cs, Ls).

对于每个子集，一个布尔变量用于表示该子集是否是封面的一部分。基数约束确保每个元素恰好被覆盖一次。

示例查询及其结果：

| ?- setcover(Cover, Cost).
Cover = [[0,0,0,1,1],[1,0,1,0,0],[0,1,0,0,0]],
Cost = 31 ? ;
Cover = [[1,0,1,1,0],[0,1,0,0,0],[0,0,0,0,1]],
Cost = 24 ? ;
no

我把选择一个成本最低的封面作为一个简单的练习。

Answer 2

也许您的问题实例的显式模型可以使事情变得更清楚：

cover(SetsUsed, Cost) :-

    SetsUsed = [A,B,C,D,E,F],       % a Boolean for each set
    SetsUsed #:: 0..1,

    A         + D         #= 1,     % use one set with element 1
        B         + E     #= 1,     % use one set with element 2
    A + B     + D         #= 1,     % use one set with element 3
    A     + C             #= 1,     % use one set with element 4
            C         + F #= 1,     % use one set with element 5

    Cost #= 10*A + 20*B + 12*C + 15*D + 4*E + 10*F.

你可以解决这个问题，例如在 ECLiPSe:

?- cover(SetsUsed,Cost), branch_and_bound:minimize(labeling(SetsUsed), Cost).

SetsUsed = [1, 0, 0, 0, 1, 1]
Cost = 24
Yes (0.00s cpu)

设置分区

Set partitioning

optimization

partitioning

prolog

constraint-programming