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/05/24 13:20] marcus [Trabalho 3 (Fluxo s-t máximo)] |
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 290: | Linha 288: | ||
| ==== Trabalho 4 (Emparelhamentos) ==== | ==== Trabalho 4 (Emparelhamentos) ==== | ||
| - | Entrega: 14/10/2013 | + | Entrega: 13/6/2017 |
| === Objetivos === | === Objetivos === | ||
| - | * Implementar o algoritmo de Hopcroft/Karp que resolve o problema do emparelhamento máximo em grafos bi-partidos. | + | * Implementar o algoritmo de Hopcroft-Karp que resolve o problema do emparelhamento máximo em grafos bi-partidos. |
| * Documentar a implementação, em particular as estruturas de dados para a representação do problema. | * 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(sqrt(n)m). Em particular: estudar a variação de n e m independentemente e verificar as complexidades O(sqrt(n)) e O(m). | + | * Conduzir testes, que demonstram que a complexidade do algoritmo é O(sqrt(n)(n+m)). Em particular: complexidades O(sqrt(n)) para o número de fases e O(n+m) para a extração de um conjunto maximál de caminhos aumentantes. |
| + | * Decidir experimentalmente: a abordagem por redução para um problema de fluxo é mais eficiente? | ||
| === Casos de teste === | === Casos de teste === | ||
| Linha 365: | Linha 364: | ||
| } | } | ||
| </code> | </code> | ||
| + | |||
| + | ==== Trabalho 5 (O algoritmo de Cristofides) ==== | ||
| + | |||
| + | Entrega: 7/7/2017 | ||
| + | |||
| + | === 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 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. | ||
| + | * 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}}. | ||
| + | * 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.1495642833.txt.gz · Esta página foi modificada pela última vez em: 2017/05/24 13:20 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
