Cobertura exata

Na matemática, dada uma coleção ${\mathcal {S}}$ de subconjuntos de um conjunto X, uma cobertura exata é uma subcoleção de ${\mathcal {S}}^{*}$ de ${\mathcal {S}}$ tal que cada elemento de X está contido em exatamente um subconjunto em ${\mathcal {S}}^{*}$ . Pode-se dizer que cada elemento de X é coberto por exatamente um subconjunto em ${\mathcal {S}}^{*}$ . Uma cobertura exata é um tipo de cobertura.

Em ciência da computação, o problema da cobertura exata é um problema de decisão para determinar se uma cobertura exata existe. O problema da cobertura exata é NP-completo ^[1]e é um dos 21 problemas NP-completos de Karp.^[2] O problema da cobertura exata é um tipo de problema de satisfação de restrições.

Um problema de cobertura exata pode ser representado por uma matriz de incidência ou por um grafo bipartido.

O Algoritmo X de Knuth é um algoritmo que encontra todas as soluções de um problema de cobertura exata. Dancing Links, comumente conhecido como DLX, é uma técnica sugerida por Donald Knuth para implementar eficientemente seu Algoritmo X em um computador.^[3]

O problema da cobertura exata padrão pode ser generalizado ligeiramente para envolver não apenas "exatamente uma" restrição, mas também "no máximo uma" restrição.

Encontrar blocos de pentaminós e resolver Sudoku são exemplos dignos de nota de problemas de cobertura exata. O problema das 8 damas é um problema de cobertura exata ligeiramente generalizado.

Definição formal[editar | editar código-fonte]

Dada uma coleção ${\mathcal {S}}$ de subconjuntos de um conjunto X, uma cobertura exata de X é uma subcoleção ${\mathcal {S}}^{*}$ de ${\mathcal {S}}$ que satisfaz duas condições:

A interseção de qualquer subconjuntos distintos em ${\mathcal {S}}^{*}$ é vazia, ou seja, os subconjuntos em ${\mathcal {S}}^{*}$ são disjuntos. Em outras palavras, cada elemtento em X está contido em no máximo um subconjunto em ${\mathcal {S}}^{*}$ .
A união dos subconjuntos em ${\mathcal {S}}^{*}$ é X, ou seja, os subconjuntos em ${\mathcal {S}}^{*}$ cobrem X. Em outras palavras, cada elemento em X está contido em pelo menos um subconjunto em ${\mathcal {S}}^{*}$ .

Brevemente, uma cobertura exata é "exata" no sentido de que cada elemento em X está contido em exatamente um subconjunto em ${\mathcal {S}}^{*}$ .

Equivalentemente, uma cobertura exata de X é uma subcoleção ${\mathcal {S}}^{*}$ de ${\mathcal {S}}$ que particiona X.

Para uma cobertura exata de X existir, é necessário que:

A união dos subconjuntos em ${\mathcal {S}}$ seja X. Em outras palavras, cada elemento em X está contido em pelo menos um subconjunto em ${\mathcal {S}}$ .

Se o conjunto vazio ∅ está contido em ${\mathcal {S}}$ , então não faz diferença ser ou não uma cobertura exata. Portanto é típico assumir que:

O conjunto vazio não está em ${\mathcal {S}}^{*}$ . Em outras palavras, cada subconjunto em ${\mathcal {S}}^{*}$ contém pelo menos um elemento.

Exemplos básicos[editar | editar código-fonte]

Seja ${\mathcal {S}}$ = {N, O, E, P} uma coleção de subconjuntos de um conjunto X = {1, 2, 3, 4} tal que:

N = { },
O = {1, 3},
E = {2, 4} e
P = {2, 3}.

A subcoleção {O, E} é uma cobertura exata de X, uma vez que os subconjuntos O = {1, 3} e E = {2, 4} são disjuntos e a união deles é X = {1, 2, 3, 4}.

A subcoleção {N, O, E} é também uma cobertura exata de X. Incluindo o conjunto vazio N = { } não faz diferença, pois é disjunto de todos os subconjuntos e não altera a união.

A subcoleção {E, P} não é uma cobertura exata de X. A interseção dos subconjuntos E e P, {2}, não é vazia: os subconjuntos E e P não são disjuntos. Além disso, a união dos subconjuntos E e P, {2, 3, 4}, não é X = {1, 2, 3, 4}: Nem E nem P cobrem o elemento 1.

Por outro lado, não há cobertura exata—de fato, não há sequer uma cobertura—de Y = {1, 2, 3, 4, 5} porque $\bigcup {\mathcal {S}}$ = {1, 2, 3, 4} é um subconjunto próprio de Y: nenhum dos subconjuntos em ${\mathcal {S}}$ contem o elemento 5.

Exemplo detalhado[editar | editar código-fonte]

Seja ${\mathcal {S}}$ = {A, B, C, D, E, F} a coleção de subconjuntos de um conjunto X = {1, 2, 3, 4, 5, 6, 7} tal que:

A = {1, 4, 7},
B = {1, 4},
C = {4, 5, 7},
D = {3, 5, 6},
E = {2, 3, 6, 7} e
F = {2, 7}.

Então a subcoleção ${\mathcal {S}}^{*}$ = {B, D, F} é uma cobertura exata, uma vez que cada elemento em X está contido em exatamente um dos subconjuntos:

B = {1, 4},
D = {3, 5, 6} ou
F = {2, 7}.

Além disso, {B, D, F} é o única cobertura exata, como o seguinte argumento demonstra: porque A e B são os únicos subconjuntos contendo 1, uma cobertura exata deve conter A ou B, mas não ambos. Se uma cobertura exata contém A, então esta não contém B, C, E ou F, pois cada um desses subconjuntos tem um elemento em comum com A. Então D é o único subconjunto restante, mas a coleção {A, D} não cobre o elemento 2. Em conclusão, não há cobertura exata contendo A. Por outro lado, se uma cobertura exata contém B, então ela não contém A ou C, pois cada um desses subconjuntos têm um elemento em comum com B. Porque D é o único subconjunto restante contento 5, D deve ser parte de uma cobertura completa. Se uma cobertura completa contém D, então ela não contém E, pois E tem um elemento em comum com D. Então F é o único subconjunto restante, e a coleção {B, D, F} é de fato uma cobertura exata. Veja o exemplo no artigo do Algoritmo X do Knuth para a versão da matriz base desse argumento.

Representações[editar | editar código-fonte]

Um problema de cobertura completa é definido por uma relação binária "contém" entre subconjuntos em ${\mathcal {S}}$ e elementos em X. Existem diferentes modos equivalentes de representar essa relação.

Representação padrão

A maneira padrão de representar a relação "contém" é listar os elementos em cada subconjunto.

Por exemplo, o exemplo detalhado acima usa esta representação padrão:

A = {1, 4, 7};
B = {1, 4};
C = {4, 5, 7};
D = {3, 5, 6};
E = {2, 3, 6, 7}; e
F = {2, 7}.

Novamente, a subcoleção \mathcal{S}^*= {B, D, F} é uma cobertura exacta, uma vez que cada elemento está contido em exatamente um subconjunto selecionado, como o realce torna claro.

Representação inversa

A relação "contém" entre os subconjuntos e elementos pode ser invertida, listando os subconjuntos cada elemento está contido.

Por exemplo, a relação "contem" no exemplo acima detalhado pode ser representado ao listar os subconjuntos cada elemento está contido em:

1 está contido em A, B;
2 está contido em E, F;
3 está contido em D, E;
4 é contido em A, B, C;
5 está contido em C, D;
6 está contido em D, E; e
7 está contido em A, C, E, F.

Mais uma vez, a subcoleção \mathcal{S}^*= {B, D, F} é uma cobertura exata, uma vez que cada elemento está contido em exatamente um subconjunto selecionado, como o realce torna claro.

Quando resolver um problema de cobertura exata , muitas vezes é útil alternar entre o padrão e as representações inversas.

Representações em Matriz e Hiper-grafos

A relação "contém" pode ser representada por uma matriz de incidência.

A matriz inclui uma linha para cada subconjunto em \mathcal{S} e uma coluna para cada elemento em X. A entrada em uma linha e coluna particular é 1 se o subconjunto correspondente contém o elemento correspondente, e é 0 de outra forma. À medida que cada linha representa os elementos contidos no subconjunto correspondente e cada coluna representa os subconjuntos que contém o elemento correspondente, uma matriz de incidência eficazmente fornece tanto representações padrão e inversas.

Na representação matriz, uma cobertura exata é uma seleção de linhas de modo que cada coluna contém um 1 em exatamente uma linha selecionada.

Por exemplo, a relação "contém" no exemplo detalhado acima pode ser representado por uma matriz 6 × 7 de incidência: ^[4]

	1	2	3	4	5	6	7
A	1	0	0	1	0	0	1
B	1	0	0	1	0	0	0
C	0	0	0	1	1	0	1
D	0	0	1	0	1	1	0
E	0	1	1	0	0	1	1
F	0	1	0	0	0	0	1

Novamente, a subcoleção \mathcal{S}^*= {B, D, F} é uma cobertura exata, uma vez que cada elemento está contido em exatamente um subconjunto selecionado, isto é, cada coluna contém um 1 em exatamente uma linha selecionada , como o realce deixa claro.

Veja o exemplo no artigo sobre Algoritmo X de Knuth para uma solução baseada na matriz para o exemplo detalhado acima.

Por sua vez, a matriz de incidência pode ser visto também como a descrição de um hipergrafo. O hipergrafo inclui um nó para cada elemento em X e uma aresta para cada subconjunto em \mathcal{S} ; cada nó está incluído em exatamente uma das arestas que formam a cobertura.

Representação por Grafos

A relação "contém" pode ser representada por um grafo bipartido.

Os vértices do grafo são divididos em dois conjuntos disjuntos, um representando os subconjuntos em \mathcal{S} e outro que representa os elementos em X. Se um subconjunto contém um elemento, uma linha conecta os vértices correspondentes no grafo.

Na representação por grafo, uma cobertura exata é uma seleção de vértices correspondentes aos subconjuntos de tal modo que cada vértice correspondente a um elemento está ligado a exatamente um vértice selecionado.

Por exemplo, a relação "contém" no exemplo detalhado acima pode ser representado por um grafo bipartido com 6 + 7 = 13 vértices:

Mais uma vez, o subcoleção \mathcal{S}^*= {B, D, F} é uma cobertura exata, uma vez que cada elemento está contido em exatamente um subconjunto selecionado, isto é, o vértice correspondente a cada elemento em X é conectado a exatamente um vértice selecionado, como o realce deixa claro.

Problemas equivalentes[editar | editar código-fonte]

Embora o problema canônico de cobertura exata envolve uma coleção de subconjuntos de um conjunto X, a lógica não depende da presença de subconjuntos contendo elementos. Um "problema abstrato de cobertura exata" surge sempre que há uma relação binária entre dois conjuntos P e Q e o objetivo é selecionar um subconjunto de P* de P tal que cada elemento em Q está relacionado com exatamente um elemento em P*. Em geral, os elementos da P representam escolhas e os elementos de Q representam "exatamente um" restrições sobre essas escolhas.

Mais formalmente, dada a relação binária R contido próprio em P × Q entre as séries P e Q, pode-se chamar um subconjunto P* de P uma "cobertura exata abstrata" de Q se cada elemento em Q é R^(−1) relacionada com a exatamente um elemento em P*. Aqui R^(−1) é o inverso de R.

Em geral, R^(−1) restrito a Q × P* é uma função de Q para P*, que mapeia cada um dos elementos Q para o elemento único em que P* que é R-relacionado a aquele elemento em Q. Esta função é para, a menos que P* contenha o "conjunto vazio", ou seja, um elemento que não está relacionado-R a qualquer elemento em Q.

No problema canônico de cobertura exata, P é um conjunto \mathcal{S}

de subconjuntos de X, Q é o conjunto X, R é a relação binária "contém" entre os subconjuntos e elementos, e R−1 restrito a Q × P* é a função "está contida no" a partir de elementos de subconjuntos selecionados.

Conjunto de acerto exato[editar | editar código-fonte]

Em matemática, dada uma coleção \mathcal{S} de subconjuntos de um conjunto X, um conjunto de acerto exato X * é um subconjunto de X tal que cada subconjunto em \mathcal{S}

contém exatamente um elemento em X* . Diz-se que cada subconjunto em \mathcal{S} é atingido por exatamente um elemento em X*.

Em ciência da computação, o problema de conjunto de acerto exato é um problema de decisão para encontrar um conjunto de acerto exato ou então não existência de um.

O problema de conjunto de acerto exato é um problema abstrato de cobertura exata. Na notação acima, P é o conjunto X, Q é uma coleção \mathcal{S} de subconjuntos de X, R é a relação binária "está contido no" entre os elementos e subconjuntos, e R^(-1) restrito a Q × P* é a função "contém" a partir de subconjuntos de elementos selecionados.

Considerando que o problema de cobertura exata envolve a seleção de subconjuntos e da relação "contém" a partir de subconjuntos de elementos, um problema de conjunto de acerto exato envolve a seleção de elementos e a relação "está contida no" a partir de elementos para subconjuntos. Em certo sentido, um problema de conjunto de acerto exato é o inverso do problema de cobertura exata envolvendo o mesmo conjunto e coleção de subconjuntos.

Exemplo de Conjunto de Acerto Exato

Tal como no exemplo de cobertura exata a cima, seja \mathcal{S} = {A, B, C, D, E, F} um conjunto de subconjuntos de um conjunto X = {1, 2, 3, 4, 5, 6, 7} de tal modo que:

A = {1, 4, 7};
B = {1, 4};
C = {4, 5, 7};
D = {3, 5, 6};
E = {2, 3, 6, 7}; e
F = {2, 7}.

Então X* = {1, 2, 5} é um conjunto de acerto exato, uma vez que cada subconjunto em \mathcal{S} contém exatamente um elemento em X *, como o realce deixa claro.

Além disso, {1, 2, 5} é o único conjunto de acerto exato, como demonstra o seguinte argumento: Porque 2 e 7 são os únicos elementos que atingiram F, um conjunto de acerto exato deve conter 2 ou 7, mas não ambos. Se um conjunto de acerto exato contém 7, em seguida, que não contém 1, 2, 3, 4, 5, ou 6, uma vez que cada um destes elementos estão contidos em um subconjunto contendo também 7. Então já não existem mais elementos restantes, mas {7} não é exatamente um conjunto de acerto, pois não atingiu B ou D. Em conclusão, não há um conjunto de acerto exato contendo 7. Por outro lado, se um conjunto de acerto exato contém 2, então não contém 3, 6 ou 7, como cada um desses elementos estão contidos em um subconjunto também contendo 2. Porque 5 é o elemento único remanescente que atinge D, o conjunto de acerto exato deve conter 5. Se um conjunto de acerto exato contém 5, então ele não contém 4, já que ambos atingiram C. Porque 1 é o elemento único remanescente que atinge A, o conjunto de acerto exato deve conter 1. Então, não há mais elementos remanescentes, e {1, 2, 5} é de fato um conjunto de acerto exato.

Embora neste exemplo envolva o mesmo conjunto de subconjuntos como o exemplo da cobertura exata detalhado acima, é essencialmente um problema diferente. Em certo sentido, o problema de conjunto de acerto exato é o inverso do problema de cobertura exata correspondente acima, como a representação em matriz deixa claro:

	A	B	C	D	E	F
1	1	1	0	0	0	0
2	0	0	0	0	1	1
3	0	0	0	1	1	0
4	1	1	1	0	0	0
5	0	0	1	1	0	0
6	0	0	0	1	1	0
7	1	0	1	0	1	1

Exemplo Duplo

Mas há um outro problema de conjunto de acerto exato que é essencialmente o mesmo que o exemplo cobertura exata detalhado acima, em que elementos numerados tornam-se subconjuntos e subconjuntos de letras tornam-se elementos, efetivamente invertendo a relação entre subconjuntos e elemento.

Por exemplo, como o subconjunto B contém os elementos 1 e 4 no problema da cobertura exato, os subconjuntos I e IV contêm o elemento b no duplo problema de conjunto de acerto exato.

Em particular, seja {\ mathcal {S}} = {I, II, III, IV, V, VI, VII} um conjunto de subconjuntos de um conjunto X = {a, b, c, d, e, f} de tal modo que:

I = {a, b}
II = {e, f}
III = {d, e}
IV = {a, b, c}
V = {c, d}
VI = {d, e}
VII = {a, c, e, f}

Então X * = {b, d, f} é um conjunto de acerto exato, uma vez que cada subconjunto de {\ mathcal {S}} contém (é atingido por) exatamente um elemento em X *, como o realce deixa claro.

O conjunto exato de acerto X* = {b,d,f} aqui é essencialmente o mesmo que a cobertura exata = {B,D,F} acima, como a representação da matiz se faz claro:

	I	II	III	IV	V	VI	VII
a	1	0	0	1	0	0	1
b	1	0	0	1	0	0	0
c	0	0	0	1	1	0	1
d	0	0	1	0	1	1	0
e	0	1	1	0	0	1	1
f	0	1	0	0	0	0	1

Referências

↑ ^ M.R. Garey; D.S.Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 0-7167-1045-5.Esse livro é um classico, desenvolvimento da teoria, então cataloga muitos problemas NP-Completos.
↑ Richard M. Karp (1972). "Reducibility among combinatorial problems". In R.E. Miller and J.W. Thatcher (editors). Complexity of Computer Computations. Proc. of a Symp. on the Complexity of Computer Computations. New York: Plenum. pp. 85–103. ISBN 0-3063-0707-3.
↑ Knuth, Donald (2000). "Dancing links". arXiv:cs/0011047.
↑ Donald Knuth in his paper "Dancing Links" gives this example, as equation (3), only with the rows reordered.

Dahlke, K. «Exact cover». Math Reference Project. Consultado em 21 de junho de 2008

Ligações externas[editar | editar código-fonte]

Implementation of an Exact Cover solver in C# - uses Algorithm X and Dancing Links.[1]

[1] M.R. Garey; D.S.Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 0-7167-1045-5.Esse livro é um classico, desenvolvimento da teoria, então cataloga muitos problemas NP-Completos.

[2] Richard M. Karp (1972). "Reducibility among combinatorial problems". In R.E. Miller and J.W. Thatcher (editors). Complexity of Computer Computations. Proc. of a Symp. on the Complexity of Computer Computations. New York: Plenum. pp. 85–103. ISBN 0-3063-0707-3.

[3] Knuth, Donald (2000). "Dancing links". arXiv:cs/0011047.

[4] Donald Knuth in his paper "Dancing Links" gives this example, as equation (3), only with the rows reordered.

[1]

[2]

[3]

[4]