集合划分

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表达它。

- JAM AICA

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和它的布尔约束求解器来表达集合覆盖：

:- 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

我留下选择最小成本覆盖的练习。

- mat

---

虽然我不太理解SICStus和布尔约束求解器的部分，但还是感谢你的回答。我希望我能成功实现自己想要的东西。 - JAM AICA

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)

- jschimpf

---

对于未知列表，我会检查每个数字所包含的列表，以便使用该数字创建约束集？例如，如果数字3在第1、2和4个列表中...我会检查初始集合，并在任何地方找到数字3时存储它，以便创建约束A+B+D #=1 ??? 非常感谢。 - JAM AICA