optimization - 设置分区

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

有一种简单的方法可以做到这一点:您可以使用 bool 指示符 来表示哪些元素组成了一个子集。例如，在您的情况下:

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).

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

示例查询及其结果:

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

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