Localizando a menor sub-coleção de conjuntos que se cruzam para produzir um elemento

Question

Localizando a menor sub-coleção de conjuntos que se cruzam para produzir um elemento

#1 resposta do (3 votos)

5

Eu criei um problema semelhante ao problema Definir capa , mas que não posso reduzir a nenhum sabe problema. Alguém tem um bom algoritmo para resolver isso?

Dado um conjunto de elementos U = {1, 2, ..., m} (o universo) e uma coleção S de n conjuntos cuja união é igual ao universo, qual é a menor sub-coleção de S que intercepta para produzir um único elemento?

Por exemplo:

U = {1, 2, 3, 4, 5}
S = {{1, 4}, {2, 4}, {5, 2}, {1, 4, 5}}

Se quisermos a menor interseção que produz 4, precisaríamos cruzar pelo menos dois conjuntos {1, 4} e {2, 4} .

O atual algoritmo ingênuo que eu tenho que fazer isso envolve

Escolha um conjunto com o elemento desejado
Iterar todos os conjuntos não escolhidos, tentar cruzar com eles e ver se a interseção produz menos elementos que o conjunto original, mas ainda incluir o elemento desejado
Para aqueles que cruzam e reduzem o número de elementos, repetimos o processo com o conjunto interceptado recursivamente até que tentamos todos os conjuntos ou estamos no elemento

Para uma aplicação concreta: Estou tentando encontrar o conjunto mínimo de classes CSS em um elemento HTML que selecionará apenas esse elemento.

algorithms css

por phsource 06.12.2015 / 01:01

fonte

1 resposta

Tags algorithms css

Usando macros para implementar um vetor genérico (matriz dinâmica) em C. Essa é uma boa ideia? No SPA, o que acontece em termos de memória e desempenho quando o usuário pula em todas as páginas?

score 3 · Accepted Answer

Infelizmente sua tarefa é NP completa.

É óbvio que todos os conjuntos de sua solução devem conter esse único elemento (vamos chamar de x ). Também é óbvio que conjuntos que não contenham x não podem ser incluídos na solução, então vamos concordar que eles não estarão presentes em S.

Permite criar uma nova coleção de conjuntos S '= {S' _k | S _k ∈S | S '_k = U \ S _k} (ou seja, cada conjunto consiste daqueles itens do universo que ele não continha inicialmente). Em outras palavras, S '_k define os elementos de U que serão removidos da interseção se tomarmos S _k.

Agora, para resolver a tarefa, você deve selecionar o número mínimo de conjuntos de S 'que cobrirá U . Qual é a definição do problema da Cobertura de Conjuntos que você mencionou no começo.