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/11/08 10:22] 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 358: | Linha 363: | ||
| - | ==== Trabalho 6 (Aproximação para o PCV) ==== | + | ==== Trabalho 6 (Aproximação para o PCV métrico) ==== |
| Entrega: 22/11/2009 | Entrega: 22/11/2009 | ||
| Linha 368: | Linha 373: | ||
| === Casos de teste === | === Casos de teste === | ||
| - | * Instâncias do {{http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/|TSPLIB}}, no mínimo brazil58, d18512, dsj1000, eil101, kroB200, pla7397, pla33810, pla85900, swiss42, usa13509. | + | * 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 === | === Convenções === | ||
| Linha 374: | Linha 379: | ||
| === Observações === | === 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. | + | * 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.1289218940.txt.gz · Esta página foi modificada pela última vez em: 2010/11/08 10:22 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
