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/18 12:49] 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 375: | Linha 380: | ||
| === 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. 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. | * 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}}. | + | * 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.1290091740.txt.gz · Esta página foi modificada pela última vez em: 2010/11/18 12:49 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
