PUC-Rio Departamento de Informática
Projeto e Análise de Algoritmos 2001.1
Prof. Marcus Vinicius Poggi
3 de julho de 2001

2^o Trabalho Prático

Dados n objetos e a matriz de dissimilaridades D_{n × n} entre eles pede-se obter a partição destes n objetos em K conjuntos de modo que o maior diâmetro destes conjuntos seja minimizado.

O diâmetro de um conjunto C_j é dado pela expressão:

D( C_j ) =

max

o_p, o_q Î C_j

d[ o_p , o_q]

O diâmetro de uma K-partição , P_K={ C₁, C₂, ..., C_K } é dado por:

PD (P_K) =

max

j Î {1,2,...,K }

D(j)

Deseja-se P_K^* tal que PS( P_K^* ) = min_P_{_K} PD(P_K).

O problema de obtenção de uma 2-partição (K=2) ótima tem complexidade polinomial, e dois algoritmos com este fim são apresentados abaixo. Entretanto, para K ³ 3 o problema se torna NP-difícil.

Os algoritmos para obter a 2-partição ótima são:

Rao, 1971
1. Ordene as dissimilaridades em ordem não-crescente.
2. Inicialmente o grafo contem somente os vértices correspondentes aos objetos. Obedecendo a ordem obtida, insira as arestas e ache uma bi-coloração (i.e. uma coloração com 2 cores). Uma aresta não é inserida quando uma bi-coloração não é possível.
3. A bi-coloração final define a bi-partição ótima.
Hansen & Jaumard, 1991
1. Encontre a Árvore Geradora Máxima (MaxST).
2. Encontre uma bi-coloração (que existe sempre. Por que ?)
3. Esta bi-coloração define a bi-partição ótima.

Objetivos: Se possível encontrar a solução ótima do problema e provar que esta solução é ótima. Caso contrário, encontrar a melhor solução possível e estabelecer sua garantia de qualidade (distância percentual da solução ótima). Você precisa:

Propor e implementar uma relaxação do problema que será modificada dentro do seu esquema de enumeração;
Propor e implementar um algoritmo para encontrar (construir e melhorar) uma boa solução inicial para o problema;
Implementar um esquema de enumeração implícita (branch and bound).

As instâncias estão disponíveis na página web. Estas instâncias são coordenadas de pontos no plano e a dissimilaridade entre os pontos (objetos) é dada pela distância Euclidiana. Encontre os clusterings ótimos para estas instâncias para K=3 e K=5.

This document was translated from L^AT_EX by H^EV^EA.