Problema G - The Open Day

Autor: Luís Paquete (Universidade de Coimbra)
Tipo de problema: Branch and Bound (pesquisa com cortes)
Número de ficheiros de teste: 15

Apesar de o número de eventos parecer "pequeno", a verdade é não é possível pesquisar todas as combinações possíveis. De facto, este é um problema computacionalmente muito complicado, pois é NP-Hard!

Em particular, este é um problema onde temos de encontrar o maximum independent set de um grafo, que é equivalente a encontrar um maximum-size clique no grafo complementar. O grafo a considerar é um grafo onde os nós são os eventos e uma ligação existe quando os eventos são incompatíveis.

Aqui fica um exemplo de grafo e o respetivo maior conjunto independente de nós:

Como resolver então este problema. O "bruto" seria procurar todos os subconjuntos possíveis de nós e ver qual o maior que é independente. Isto não passa no tempo...

Para melhorar vamos ter que aplicar vários "cortes". Existiam várias possibilidades, mas uma solução que daria para resolver todos os testes do Mooshak de forma quase instantânea passaria por:

  1. Gerar uma única vez cada subconjunto (ex: gerar "por ordem")
  2. Apenas adicionar ao subconjunto nós que não "quebrem" a independência (saber quais são de forma eficiente)
  3. Parar a pesquisa quando a solução atual nunca pode vir a ser melhor que o melhor até agora ("quantos nós ainda não ligados faltam?" era uma heurística possível)

Era possível fazer melhor (e existem muitas publicações científicas relacionados com este problema) mas estes cortes chegavam para os testes e limites dados. Nota que sem o corte nº3, o programa não passava no tempo.

Ligações interessantes: