Set Partitionierung

Question

Ich versuche, ein gutes Verständnis mit diesem Problem zu bekommen, aber ich kämpfe. Nehmen wir an, ich habe ein S = {1,2,3,4,5}, ein L = {(1,3,4), (2,3), (4,5), (1,3) , (2), (5)} und ein anderes Tupel mit den Kosten von L wie C = {10,20,12,15,4,10}

Ich möchte ein Einschränkungsprogramm in Prolog machen, um Nehmen Sie die Lösung, die das Problem mit den minimalen Kosten löst. (In diesem Fall ist es die Gesamtsumme der Kosten der Teilmengen, die ich bekommen werde)

Mein Problem ist, dass ich nicht verstehen kann, wie ich meine Modellierung machen werde . Was ich weiß ist, dass ich eine Modellierung von binären Variablen {0,1} wählen sollte, aber ich verstehe kaum, wie ich es schaffen werde, es über Prolog auszudrücken.

Answer 1

Vielleicht ein explizites Modell für Ihren Problemfall macht die Dinge etwas klarer:

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. 

Sie können dieses Problem lösen z.B. in ECLiPSe:

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

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

Answer 2

Es gibt einen einfachen Weg, es zu tun: Sie können Boolean Indikatoren verwenden, um zu bezeichnen, welche Elemente eine Teilmenge umfassen. Zum Beispiel, in Ihrem Fall:

 
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} 

Ich verwende jetzt SICStus Prolog und seine Boolean constraint solver zu Satz Abdeckungen ausdrücken:

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

Für jede Untergruppe wird eine Boolesche Variable verwendet zu bezeichnen, ob dieser Teilmenge Teil der Abdeckung. Cardinality Constraints stellen sicher, dass jedes Element genau einmal   abgedeckt wird.

Beispiel Abfrage und das Ergebnis:

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

Ich lasse als einfache Übung eine Abdeckung mit minimal Kosten Kommissionierung.