Diferenças

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

--- inf05016:2015-2-trabalhos [2015/10/18 20:42]
marcus [Trabalho 4 (Open pit mining)]
+++ inf05016:2015-2-trabalhos [2015/12/10 15:23] (Actual)
marcus
@@ Linha 1: / Linha 1: @@
-Status das entregas (23/9/2015):
+Status das entregas (10/12/2015):
+^    No. ^ T1 ^ T2 ^ T3 ^ T4 ^ T5 ^ T6 ^
+|   21893 | s  | s  |    |    |    |    |
+|  174872 |    |    |    |    |    |    |
+|  181098 |    |    |    |    |    |    |
+|  193031 | s  |    |    |    |    |    |
+|  193276 | s  | s  | s  | s  | s  |    |
+|  193693 | s  | s  | s  | s  | s  | s  |
+|  194049 | s  |    |    |    |    |    |
+|  194636 | s  | s  | s  | s  | s  |    |
+|  195843 | s  | s  |    |    |    |    |
+|  219436 |    |    |    |    |    |    |
+|  220640 | s  | s  | s  | s  | s  |    |
+|  228395 | s  | s  | s  | s  | s  |    |
+|  228450 | s  | s  | s  | s  | s  |    |
-^    No. ^ T1 ^ T2 ^
-|   21893 | s  | s  |
-|  174872 |    |    |
-|  181098 |    |    |
-|  193031 | s  |    |
-|  193276 | s  | s  |
-|  193693 | s  | s  |
-|  194049 | s  |    |
-|  194636 | s  | s  |
-|  195843 | s  | s  |
-|  219436 |    |    |
-|  220640 | s  | s  |
-|  228395 | s  | s  |
-|  228450 | s  | s  |
 ==== Trabalho 1 (Heaps binários e algoritmo de Dijkstra) ====
@@ Linha 332: / Linha 334: @@
 === 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.
+  * {{http://www.inf.ufrgs.br/~mrpritt/aa/data.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 o peso total da solução correta.
 === Convenções ===
@@ Linha 346: / Linha 348: @@
+==== Trabalho 6 (O algoritmo de Cristofides) ====
+Entrega: 10/12/2015 (Observação: esta data não será prorrogada)
+=== Objetivos ===
+  * Implementar o algoritmo de Cristofides
+  * Testar duas variantes: a) usando um emparelhamento perfeito máximo, b) usando um emparelhamento perfeito obtido por um algoritmo guloso que seleciona cada vez a aresta livre de maior peso.
+  * Conduzir testes que avaliam o desempenho do algoritmo em termos de qualidade e tempo.
+=== Casos de teste ===
+  * Disponíveis na {{http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95|TSPLIB}}. Aplicar pelo menos nas instâncias gr96, gr202, gr229, gr431, ali535, gr666, dsj1000, pla7397, pla33810, pla85900.
+  * Para avaliar a qualidade: relatar o desvio relativo percentual (v-b)/b de uma solução com valor v e melhor valor conhecido b.
+  * Informar o tempo de execução em segundos.
+=== Convenções ===
+  * A implementação deve aceitar uma instância na entrada padrão (stdin) e imprimir o valor da rota obtida pelo algoritmo de Cristofides na saída padrão (stdout).
+  * O formato das instâncias é o mesmo formato usado na {{http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95|TSPLIB}}: uma documentação está {{http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/DOC.PS|aqui}}
+=== Materiais ===
+  * Para calcular o matching, usar o software {{http://pub.ist.ac.at/~vnk/software/blossom5-v2.05.src.tar.gz|Blossom V}}. (O algoritmo Húngaro da questão 5 não serve, porque é necessário determinar um matching no grafo não-bipartido.)
+  * Para facilitar a leitura de instâncias da TSPLIB, {{http://www.inf.ufrgs.br/~mrpritt/aa/tspParse.H}} e {{http://www.inf.ufrgs.br/~mrpritt /aa/tspParse.C}} mostram um exemplo em C++, que pode ser adaptado.

Marcus Ritt

Ferramentas de Utilizador

Ferramentas de Site

Diferenças

Ferramentas de Página