Ferramentas de Utilizador
inf05016:2015-2-trabalhos
Diferenças
Esta página mostra as diferenças entre as duas revisões da página.
| Ambos os lados da revisão anterior Revisão anterior Próxima revisão | Revisão anterior | ||
|
inf05016:2015-2-trabalhos [2015/11/18 11:03] marcus [Trabalho 6 (O algoritmo de Cristofides)] |
inf05016:2015-2-trabalhos [2015/12/10 15:23] (Actual) marcus |
||
|---|---|---|---|
| Linha 1: | Linha 1: | ||
| - | Status das entregas (15/11/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 ^ T3 ^ T4 ^ | ||
| - | | 21893 | s | s | | | | ||
| - | | 174872 | | | | | | ||
| - | | 181098 | | | | | | ||
| - | | 193031 | s | | | | | ||
| - | | 193276 | s | s | s | s | | ||
| - | | 193693 | s | s | s | s | | ||
| - | | 194049 | s | | | | | ||
| - | | 194636 | s | s | s | s | | ||
| - | | 195843 | s | s | | | | ||
| - | | 219436 | | | | | | ||
| - | | 220640 | s | s | s | s | | ||
| - | | 228395 | s | s | s | s | | ||
| - | | 228450 | s | s | s | s | | ||
| ==== Trabalho 1 (Heaps binários e algoritmo de Dijkstra) ==== | ==== Trabalho 1 (Heaps binários e algoritmo de Dijkstra) ==== | ||
| Linha 357: | Linha 359: | ||
| === Casos de teste === | === Casos de teste === | ||
| - | * Disponíveis na {{http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95|TSPLIB}}. | + | * 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. | * 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. | * Informar o tempo de execução em segundos. | ||
| Linha 369: | Linha 371: | ||
| * 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 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. | ||
inf05016/2015-2-trabalhos.1447851835.txt.gz · Esta página foi modificada pela última vez em: 2015/11/18 11:03 por marcus
Ferramentas de Página
Excepto menção em contrário, o conteúdo neste wiki está sob a seguinte licença: CC Attribution-Noncommercial-Share Alike 4.0 International
