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

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

  1. Escolha um conjunto com o elemento desejado
  2. 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
  3. 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.

    
por phsource 06.12.2015 / 01:01
fonte

1 resposta

3

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.

    
por 06.12.2015 / 03:41
fonte