Ferramentas de Utilizador
inf05016:2017-1-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:2017-1-trabalhos [2017/06/19 12:06] marcus [Trabalho 4 (Emparelhamentos)] |
inf05016:2017-1-trabalhos [2017/07/25 07:36] (Actual) |
||
|---|---|---|---|
| Linha 1: | Linha 1: | ||
| - | Status das entregas (8 de abril 2017): | + | Status das entregas (25 de julho 2017): |
| - | + | ||
| - | ^ Cartão ^ T1 ^ T2 ^ | + | |
| - | | 120921 | s | s | | + | |
| - | | 161896 | s | s | | + | |
| - | | 205691 | s | s | | + | |
| - | | 205798 | | | | + | |
| - | | 213917 | | | | + | |
| - | | 218319 | s | | | + | |
| - | | 218326 | s | s | | + | |
| - | | 219436 | | | | + | |
| - | | 220505 | s | s | | + | |
| - | | 228401 | s | | | + | |
| - | | 228483 | s | s | | + | |
| - | | 228527 | s | s | | + | |
| - | | 242239 | s | | | + | |
| - | | 242249 | s | | | + | |
| - | | 242274 | s | s | | + | |
| - | | 259094 | s | s | | + | |
| - | | 262528 | s | | | + | |
| - | | 264311 | s | | | + | |
| - | | 273103 | s | s | | + | |
| - | | 282838 | s | | | + | |
| - | | 286120 | s | s | | + | |
| - | | 286134 | s | s | | + | |
| - | | 286244 | s | | | + | |
| - | | 291000 | s | s | | + | |
| + | ^ Cartão ^ T1 ^ T2 ^ T3 ^ T4 ^ T5 ^ | ||
| + | | 120921 | s | s | s | s | s | | ||
| + | | 161896 | s | s | s | s | s | | ||
| + | | 205691 | s | s | s | s | s | | ||
| + | | 205798 | | | | | | | ||
| + | | 213917 | | | | | | | ||
| + | | 218319 | s | | | | | | ||
| + | | 218326 | s | s | s | s | s | | ||
| + | | 219436 | | | | | | | ||
| + | | 220505 | s | s | s | s | s | | ||
| + | | 228401 | s | | | | | | ||
| + | | 228483 | s | s | s | s | s | | ||
| + | | 228527 | s | s | s | s | s | | ||
| + | | 242239 | s | | | | | | ||
| + | | 242249 | s | | | | | | ||
| + | | 242274 | s | s | s | s | s | | ||
| + | | 259094 | s | s | s | s | s | | ||
| + | | 262528 | s | | | | | | ||
| + | | 264311 | s | | | | | | ||
| + | | 273103 | s | s | | | | | ||
| + | | 282838 | s | | | | | | ||
| + | | 286120 | s | s | s | s | s | | ||
| + | | 286134 | s | s | s | s | s | | ||
| + | | 286244 | s | | s | s | s | | ||
| + | | 291000 | s | s | s | s | s | | ||
| ==== Trabalho 1 (Heaps binários e algoritmo de Dijkstra) ==== | ==== Trabalho 1 (Heaps binários e algoritmo de Dijkstra) ==== | ||
| Linha 367: | Linha 365: | ||
| </code> | </code> | ||
| - | ==== Trabalho 6 (O algoritmo de Cristofides) ==== | + | ==== Trabalho 5 (O algoritmo de Cristofides) ==== |
| Entrega: 7/7/2017 | Entrega: 7/7/2017 | ||
| Linha 378: | Linha 376: | ||
| === Casos de teste === | === 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. | + | * Disponíveis na {{http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95|TSPLIB}}. Aplicar pelo menos nas instâncias berlin52, vm1748, pr2392, pcb3038, fnl4461, rl5934, rl5915, usa13509, brd14051, d18512. |
| * 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 391: | Linha 389: | ||
| * Para calcular o matching, usar o software {{http://pub.ist.ac.at/~vnk/software/blossom5-v2.05.src.tar.gz|Blossom V}}. | * Para calcular o matching, usar o software {{http://pub.ist.ac.at/~vnk/software/blossom5-v2.05.src.tar.gz|Blossom V}}. | ||
| * 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. | * 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. | ||
| + | * {{http://www.inf.ufrgs.br/~mrpritt/aa/blossom.patch-2|Um patch}} contra blossom5 para trabalhar com coordenadas reais (e um bugfix). | ||
inf05016/2017-1-trabalhos.1497884787.txt.gz · Esta página foi modificada pela última vez em: 2017/06/19 12:06 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
