Ferramentas de Utilizador
inf05504: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 | ||
|
inf05504:trabalhos [2010/10/26 09:24] marcus |
inf05504:trabalhos [2010/12/03 17:08] (Actual) marcus |
||
|---|---|---|---|
| Linha 140: | Linha 140: | ||
| === Casos de teste === | === Casos de teste === | ||
| * Podem ser usados os mesmo casos de teste do primeiro trabalho. | * Podem ser usados os mesmo casos de teste do primeiro trabalho. | ||
| + | |||
| + | === Materias === | ||
| + | * {{:inf05504:rank-pairing_heaps_easier_.pdf|Artigo}} | ||
| + | |||
| ==== Trabalho 3 (Fluxo s-t máximo) ==== | ==== Trabalho 3 (Fluxo s-t máximo) ==== | ||
| Linha 343: | Linha 347: | ||
| === Casos de teste === | === Casos de teste === | ||
| - | * Gerar grafos bi-partidos completos com pesos aleatórios escolhidos uniformemente do intervalo [0,n^2]. | + | * 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. | ||
| === Convenções === | === Convenções === | ||
| Linha 356: | Linha 361: | ||
| com pij o peso entre vértice i do primeiro parte do grafo e vértice j do segundo parte. | com pij o peso entre vértice i do primeiro parte do grafo e vértice j do segundo parte. | ||
| + | |||
| + | |||
| + | ==== Trabalho 6 (Aproximação para o PCV métrico) ==== | ||
| + | |||
| + | Entrega: 22/11/2009 | ||
| + | |||
| + | === Objetivos === | ||
| + | * Implementar o algoritmo de Cristofides para aproximar o PCV. | ||
| + | * Documentar a implementação, em particular as estruturas de dados para a representação do problema. | ||
| + | * Conduzir testes para avaliar o tempo de execução e a qualidade da solução obtida. Em particular, comparar com os melhores resultados conhecidos das instâncias do {{http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/|TSPLIB}}. | ||
| + | |||
| + | === Casos de teste === | ||
| + | * Instâncias métricas do {{http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/|TSPLIB}}, entre eles gr96, gr202, gr229, gr431, ali535, gr666, dsj1000, pla7397, pla33810, pla85900. | ||
| + | |||
| + | === Convenções === | ||
| + | * As implementações do algoritmo devem aceitar uma instância de PCV no formato da TSPLIB na entrada padrão (stdin) e imprimir o valor da rota na saída padrão (stdout). | ||
| + | |||
| + | === Observações === | ||
| + | * Para conseguir resultados para as maiores instâncias uma representação do grafo por uma matriz de adjacência não é adequado. Faz parte do objetivo de trabalho conseguir resultados para instâncias desse tamanho. Como o grafo é completo, não é necessário representa-lo explicitamente. Nas instâncias acima, as distâncias também são dadas implicitamente e não precisam ser representadas. | ||
| + | * Não é o objetivo implementar um algoritmo de emparelhamento de peso máximo: usam {{http://www.cs.ucl.ac.uk/staff/V.Kolmogorov/software.html|Blossom V}}. Observem que o Blossom V tem apoio para grafos geometricos no formato do TSPLIB, então não é necessário nem aconsehável criar o grafo explicitamente. | ||
inf05504/trabalhos.1288092282.txt.gz · Esta página foi modificada pela última vez em: 2010/10/26 09:24 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
