Atribuindo grupos

Question

Eu tenho um problema onde devo atribuir variáveis ​​a conjuntos. Cada conjunto tem um limite de variáveis ​​que podem ser atribuídas a ele e cada variável pode ser atribuída a algum subconjunto dos conjuntos totais.

Exemplo:

• apode ser em conjuntos AouB
• bpode ser em conjuntosB
• cpode ser em conjuntos AouB
• dpode ser em conjuntosA

Assim, podemos ter A: a, d; B: b, cou A: c, d; B: a,b(a ordem das variáveis ​​dentro do conjunto não importa)/

Claro, haverá momentos em que será impossível atribuir todas as variáveis, momentos em que teremos várias opções e momentos com apenas 1 opção.

Sinto que existe uma versão simples desse problema, mas não consigo identificar. Quaisquer dicas seriam apreciadas.

Answer 1

Solucionável eficientemente usando fluxo máximo. Prepare uma rede de fluxo com um arco de capacidade unitária de uma fonte para cada variável, um arco de capacidade unitária de cada variável para cada conjunto ao qual ela pode pertencer e um arco de cada conjunto para um sumidouro de capacidade igual à capacidade do conjunto . Por exemplo,

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 seu algoritmo de fluxo máximo favorito que produz um fluxo integral e extraia a atribuição de acordo com qual variável definir os arcos têm fluxo.

Answer 2

Este problema é NP-completo, o que significa que não há solução de tempo polinomial para isso. Você teria que usar backtracking neste caso.

Dê uma olhada nestes links:

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/