Attribution de groupes

Question

J'ai un problème où je dois attribuer des variables à des ensembles. Chaque ensemble a une limite de variables qui peuvent lui être affectées et chaque variable peut être affectée à un sous-ensemble des ensembles totaux.

Exemple:

• apeut être en ensembles AouB
• b peut être en ensembles B
• cpeut être en ensembles AouB
• d peut être en ensembles A

Ainsi, nous pouvons avoir A: a, d; B: b, cou A: c, d; B: a,b(l'ordre des variables dans l'ensemble n'a pas d'importance) /

Bien sûr, il y aura des moments où il sera impossible d'attribuer toutes les variables, des moments où nous avons plusieurs options et des moments avec une seule option.

J'ai l'impression qu'il existe une version simple de ce problème, mais je n'arrive pas à y mettre le doigt. Tous les pointeurs seraient appréciés.

Answer 1

Résolvable efficacement en utilisant un débit maximal. Préparer un réseau de flux avec un arc de capacité unitaire d'une source à chaque variable, un arc de capacité unitaire de chaque variable à chaque ensemble auquel elle peut appartenir, et un arc de chaque ensemble à un puits de capacité égale à la capacité de l'ensemble . Par exemple,

ARCS

tail head capacity
------------------
s    a    1
s    b    1
s    c    1
s    d    1
a    A    1
a    B    1
b    B    1
c    A    1
c    B    1
d    A    1
A    t    2
B    t    2

Utilisez votre algorithme de flux maximal préféré qui produit un flux intégral et extrayez l'affectation en fonction de la variable à définir les arcs qui ont un flux.

Answer 2

Ce problème est NP-complet, ce qui signifie qu'il n'y a pas de solution temporelle polynomiale pour cela. Vous devrez utiliser le retour en arrière dans ce cas.

Jetez un œil à ces liens:

https://www.geeksforgeeks.org/vertex-cover-problem-set-1-introduction-approximate-algorithm-2/ https://www.geeksforgeeks.org/set-cover-problem-set-1-greedy-approximate-algorithm/