Asignación de grupos

Question

Tengo un problema donde debo asignar variables a conjuntos. Cada conjunto tiene un límite de variables que se le pueden asignar y cada variable se puede asignar a algún subconjunto de los conjuntos totales.

Ejemplo:

• apuede ser en conjuntos AoB
• bpuede estar en conjuntosB
• cpuede ser en conjuntos AoB
• dpuede estar en conjuntosA

Por lo tanto, podemos tener A: a, d; B: b, co A: c, d; B: a,b(el orden de las variables dentro del conjunto no importa)/

Por supuesto, habrá momentos en los que sea imposible asignar todas las variables, momentos en los que tengamos múltiples opciones y momentos con solo 1 opción.

Siento que hay una versión simple de este problema, pero parece que no puedo identificarlo. Cualquier indicador sería apreciada.

Answer 1

Solucionable de manera eficiente utilizando el flujo máximo. Prepare una red de flujo con un arco de capacidad unitaria desde una fuente a cada variable, un arco de capacidad unitaria desde cada variable a cada conjunto al que puede pertenecer, y un arco desde cada conjunto a un sumidero de capacidad igual a la capacidad del conjunto . Por ejemplo,

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

Use su algoritmo de flujo máximo favorito que produce un flujo integral y extraiga la asignación de acuerdo con la variable para establecer que los arcos tengan flujo.

Answer 2

Este problema es NP-completo, lo que significa que no hay una solución de tiempo polinomial para esto. Tendrías que usar backtracking en este caso.

Echa un vistazo a estos enlaces:

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/