Diferenças

Esta página mostra as diferenças entre as duas revisões da página.

--- inf05504:trabalhos [2010/10/06 08:53]
marcus
+++ inf05504:trabalhos [2010/12/03 17:08] (Actual)
marcus
@@ Linha 140: / Linha 140: @@
 === Casos de teste ===
   * Podem ser usados os mesmo casos de teste do primeiro trabalho.
+=== Materias ===
+  * {{:inf05504:rank-pairing_heaps_easier_.pdf|Artigo}}
 ==== Trabalho 3 (Fluxo s-t máximo) ====
@@ Linha 254: / Linha 258: @@
 </a>
 </html>
 ==== Trabalho 4 (Emparelhamentos) ====
@@ Linha 334: / Linha 337: @@
 </code>
+==== Trabalho 5 (Emparelhamentos) ====
+Entrega: 08/11/2009
+=== Objetivos ===
+  * Implementar o algoritmo Húngaro que resolve o problema do emparelhamento de maior peso em grafos bi-partidos ponderados.
+  * Documentar a implementação, em particular as estruturas de dados para a representação do problema.
+  * Conduzir testes, que demonstram que a complexidade do algoritmo é O(mn^2), usando Bellman-Ford para busca de caminhos aumentantes.
+=== Casos de teste ===
+  * Gerar grafos bi-partidos completos com pesos aleatórios escolhidos uniformemente no intervalo [0,n^2].
+  * {{http://www.inf.ufrgs.br/~mrpritt/data1.tgz|Casos de teste com soluções}} para a emparelhamento ponderado perfeito mínimo (para comparar com emparelhamento perfeito máximo: multiplicar os valores por -1). O formato corresponde com o que está descrito nas convenções abaixo com a última linha informando ainda o valor peso total da solução correta.
+=== Convenções ===
+  * As implementações do algoritmo devem aceitar um grafo bi-partido não-direcionado completo na entrada padrão (stdin) e imprimir o maior peso de um emparelhamento na saída padrão (stdout). O formato é
+<code>
+n
+p11 p12 p13 ... p1n
+p21 p22 p23 ... p2n
+...
+pn1 pn2 pn3 ... pnn
+</code>
+com pij o peso entre vértice i do primeiro parte do grafo e vértice j do segundo parte.
+==== Trabalho 6 (Aproximação para o PCV métrico) ====
+Entrega: 22/11/2009
+=== Objetivos ===
+  * Implementar o algoritmo de Cristofides para aproximar o PCV.
+  * Documentar a implementação, em particular as estruturas de dados para a representação do problema.
+  * Conduzir testes para avaliar o tempo de execução e a qualidade da solução obtida. Em particular, comparar com os melhores resultados conhecidos das instâncias do {{http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/|TSPLIB}}.
+=== Casos de teste ===
+  * Instâncias métricas do {{http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/|TSPLIB}}, entre eles gr96, gr202, gr229, gr431, ali535, gr666, dsj1000, pla7397, pla33810, pla85900.
+=== Convenções ===
+  * As implementações do algoritmo devem aceitar uma instância de PCV no formato da TSPLIB na entrada padrão (stdin) e imprimir o valor da rota na saída padrão (stdout).
+=== Observações ===
+  * Para conseguir resultados para as maiores instâncias uma representação do grafo por uma matriz de adjacência não é adequado. Faz parte do objetivo de trabalho conseguir resultados para instâncias desse tamanho. Como o grafo é completo, não é necessário representa-lo explicitamente. Nas instâncias acima, as distâncias também são dadas implicitamente e não precisam ser representadas.
+  * Não é o objetivo implementar um algoritmo de emparelhamento de peso máximo: usam {{http://www.cs.ucl.ac.uk/staff/V.Kolmogorov/software.html|Blossom V}}. Observem que o Blossom V tem apoio para grafos geometricos no formato do TSPLIB, então não é necessário nem aconsehável criar o grafo explicitamente.

Marcus Ritt

Ferramentas de Utilizador

Ferramentas de Site

Diferenças

Ferramentas de Página