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/09/23 17:16] marcus |
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) ==== | ==== Trabalho 1 (Heaps binários e algoritmo de Dijkstra) ==== | ||
| Linha 281: | Linha 283: | ||
| {{https://upload.wikimedia.org/wikipedia/commons/8/83/Udachnaya_pipe.JPG?320}} | {{https://upload.wikimedia.org/wikipedia/commons/8/83/Udachnaya_pipe.JPG?320}} | ||
| - | Entrega: 5/10/2015 | + | Entrega: 12/10/2015 |
| === Objetivos === | === Objetivos === | ||
| Linha 321: | Linha 323: | ||
| </code> | </code> | ||
| + | ==== Trabalho 5 (Emparelhamentos) ==== | ||
| + | |||
| + | Entrega: 16/11/2015 | ||
| + | |||
| + | === 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/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 === | ||
| + | * 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 (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. | ||
inf05016/2015-2-trabalhos.1443039362.txt.gz · Esta página foi modificada pela última vez em: 2015/09/23 17:16 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
