Como particionar um conjunto em um determinado número de subconjuntos independentes, sujeito a algumas condições?

11

Recebi um conjunto A{1,,k} , um número inteiro sk e números inteiros não negativos aij . Meu problema é encontrar s subconjuntos Sj de {1,,k} modo que:

  1. j=1sSj=A ; e
  2. |Sj|aij para todos iSj e j=1,,s .

Como resolver este problema? É difícil encontrar uma solução viável?

Acho que não é fácil resolver o problema, porque tentei algum procedimento que começa com j{1,,n} e atribui i{1,,k} até o número de i atribuído a j é maior que aij para alguns que i designei. Mas isso não está correto, porque eu poderia ficar com alguns i que não pudessem ser atribuídos a nenhum j (por causa do aij que não poderia ser satisfeito).

O método da força bruta, quando tenho que gerar todos os subconjuntos de A e testar cada um, funciona para mim ( k=8,n=3 ), mas muito ineficiente.

drzbir
fonte
Verifique se a edição corresponde à pergunta que você deseja fazer. Além disso, de onde vem ? É uma constante fixa (não faz parte da entrada, mas é fixa para todos os tempos) ou faz parte da entrada? Finalmente, você está procurando uma solução prática? ou você está procurando a complexidade teórica desse problema? No primeiro, você já tentou usar programação linear inteira? amax
DW

Respostas:

10

Esse problema é difícil de NP por redução do Vertex Cover.

No problema da cobertura de vértices, recebemos um gráfico e um número , e nossa tarefa é determinar se existe algum subconjunto de no máximo vértices de modo que todas as arestas em sejam incidentes. em pelo menos um vértice em . (Equivalentemente: é possível eliminar todas as arestas em excluindo no máximo vértices?)r U r V E U G rG=(V,E)rUrVEUGr

Primeiro, o particionamento em subconjuntos disjuntos é equivalente a atribuição de cada elemento em exatamente uma das possíveis etiquetas. A idéia básica da redução é criar um rótulo para cada vértice em e "permitir" que cada borda seja atribuída apenas a um dos dois rótulos correspondentes aos seus pontos finais, no seguinte sentido: atribuir uma borda a um correspondente A etiqueta não apresenta restrição (genuína) sobre quais outras arestas podem ser atribuídas à mesma etiqueta, enquanto a atribuição de uma borda a uma etiqueta não correspondente impede que qualquer outra borda seja atribuída à mesma etiqueta - o que, obviamente, tem o efeito de aumentar o número de etiquetas distintas necessárias.s A s S j v j VAsAsSjvjV

Para construir uma instância do seu problema a partir de uma instância do Vertex Cover:( G , r )(A,a,s)(G,r)

  1. Defina comoE criar um elemento de para cada aresta em . (Esses pares podem ser considerados os números inteiros ; qualquer bijeção entre eles serve.)| E | ( i , j ) A v i v j E 1 , , kk|E|(i,j)AvivjE1,,k
  2. Defina comose ou ; caso contrário, defina como 1. | E | d = b d = c a ( b , c ) , da(b,c),d|E|d=bd=ca(b,c),d
  3. Defina .s=r

Se é uma instância YES do Vertex Cover, é fácil ver que a instância recém- do seu problema também é uma instância YES: basta escolher os rótulos correspondentes aos vértices em qualquer solução e para cada aresta atribua o elemento correspondente que um dos rótulos ou foi selecionado (escolha arbitrariamente se os dois rótulos foram selecionados). Esta solução utiliza subconjuntos, e é válida porque a única em vigor são aqueles para os correspondentesS j v j U v b v cE ( b , c ) A S b S c s a i j(G,r)SjvjUvbvcE(b,c)ASbScsaijrótulos com efeito (não) de impedir mais debordas sendo atribuídas à mesma etiqueta.|E|

Resta mostrar que uma instância YES do seu problema implica que o original é uma instância YES da Vertex Cover. Isso é um pouco mais complicado, uma vez que uma solução válida de a pode, em geral, atribuir uma borda um rótulo não correspondente , ou seja, , o que significa que não podemos necessariamente "lido" a cobertura do vértice válida de uma solução válida .( G , r ) Y X ( i , j )X=(A,a,s)(G,r)YX(i,j) m { i , j } U YSmm{i,j}UY

No entanto, atribuir um rótulo não correspondente tem um alto custo que limita severamente a estrutura da solução: sempre que uma borda recebe esse rótulo , com , o fato que garante que deve ser a única aresta atribuída a esse rótulo. Portanto, em qualquer solução contenha uma borda não correspondentemente rotulada , poderíamos construir uma solução alternativa seguinte maneira:S m m { i , j } a ( i , j ) , m = 1(i,j)Smm{i,j}a(i,j),m=1( i , j ) S m Y Y(i,j)SmY

  1. Arbitrariamente escolher o novo rótulo para para ser ou .Sz(i,j)SiSj
  2. Atribua esse novo rótulo. Se isso resultar em uma solução inválida, deve ser porque exatamente uma outra aresta , já recebeu o rótulo . Nesse caso, defina e vá para a etapa 1.(i,j)(i,j)z{i,j}Sz(i,j)=(i,j)

O algoritmo acima deve terminar de uma de duas maneiras: seja encontrado um novo rótulo que não introduz contradição ou seja encontrado um ciclo completo de vértices. No primeiro caso, uma nova solução válida com conjuntos é encontrada, enquanto no último caso uma nova solução válida com conjuntos é encontrada; de qualquer maneira, construímos uma nova solução válida com pelo menos mais uma borda atribuída a um rótulo correspondente . Depois de repetir todo esse processo no máximovezes, teremos produzido uma solução válida partir da qual uma solução para o problema original da Vertex Cover pode ser lida.Szs1s|E|Y

Essa construção é claramente um tempo polinomial; portanto, seu problema é difícil para o NP.

j_random_hacker
fonte
Obrigado pela ajuda. Você tem alguma idéia de como alguém pode resolver (aproximadamente) esse problema? (Como, por exemplo, posso usar técnicas para o problema de cobertura de vértices para resolvê-lo?) Tentei uma abordagem gananciosa, mas, às vezes, falha em gerar uma solução viável. (A maneira que eu escolher o torna a abordagem gananciosos falha onde uma solução poderia existir.)Sj
drzbir
Bem, espera-se que uma abordagem gananciosa às vezes falhe na saída de uma solução viável, pois, se sempre acontecesse, você resolveria um problema difícil de NP em tempo poli ;-) Lembre-se de que não é necessariamente errado se não puder encontre uma solução: pode ser que não exista uma solução viável.
Jrandom_hacker
Em relação às técnicas de solução, uma que eu gosto é chamada busca por feixe. Esse é basicamente um tipo de ramificação e vinculação que "esquece" soluções parciais suficientemente ruins para limitar o uso de memória. (O B&B é, por si só, uma abordagem muito boa e, às vezes, resolve problemas rapidamente, e é um pouco mais simples que a busca por feixes, portanto vale a pena tentar - mas, como é um método exato, é claro que pode levar milênios em algumas instâncias.)
j_random_hacker
(Todos os itens abaixo também se aplicam à pesquisa por vigas e ao B&B.) O B&B é uma técnica muito geral. O principal é explorar as especificidades do problema para organizar as decisões que você toma para que, na medida do possível, decisões ruins (ou seja, decisões que não levam a soluções viáveis) sejam tomadas no início da árvore de pesquisa. (Essas decisões serão tomadas em algum lugar , e cada nível mais profundo que elas serão feitas duplica o número de vezes que elas são tomadas.) Para o seu problema, sugiro primeiro classificar os elementos em em ordem decrescente de "maldade", onde. ..A
j_random_hacker
... a maldade do elemento que poderia ser, por exemplo, o mínimo de sobre todos os , quebrando os laços pelo segundo mínimo, depois pelo terceiro mínimo, etc. Grosso modo, o elemento "pior" será o elemento que restringe mais severamente qualquer conjunto ao qual é adicionado. Em cada nó na profundidade na árvore de pesquisa, você terá uma solução parcial na qual os primeiros (e, portanto, "piores") elementos já foram atribuídos aos conjuntos; você precisará escolher para qual dos conjuntos atribuir o ésimo elemento: ou seja, você precisará de até chamadas recursivas. ("Até", porque esperamos que tenhamos, ...iaijjddn(d+1)n
j_random_hacker