Comparação de algoritmos para o Problema dos K Menores Caminhos (2018)
- Authors:
- Autor USP: KYKUTA, DIOGO HARUKI - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Subjects: COMBINATÓRIA; OTIMIZAÇÃO COMBINATÓRIA
- Keywords: Caminho mínimo; Grafos; Grafos dirigidos com peso nos arcos; Graphs; K menores caminhos; K shortest paths; Shortest path; Weighted directed graph
- Agências de fomento:
- Language: Português
- Abstract: O Problema dos K Menores Caminhos é uma generalização do Problema do Menor Caminho, em que desejamos encontrar os K caminhos de menor custo entre dois vértices de um grafo. Estudamos e implementamos algoritmos que resolvem esse problema em grafos dirigidos, com peso nos arcos e que permitem apenas caminhos sem repetição de vértices na resposta. Comparamos seus desempenhos utilizando grafos do 9th DIMACS Implementation Challenge. Identificamos os pontos fortes e fracos de cada algoritmo, e propusemos uma variante híbrida dos algoritmos de Feng e de Pascoal. Essa variante proposta obteve desempenho superior aos algoritmos base em alguns grafos, e resultado superior a pelo menos um deles na grande maioria dos testes
- Imprenta:
- Data da defesa: 19.02.2018
-
ABNT
KYKUTA, Diogo Haruki. Comparação de algoritmos para o Problema dos K Menores Caminhos. 2018. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2018. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-20032018-003225/. Acesso em: 28 mar. 2024. -
APA
Kykuta, D. H. (2018). Comparação de algoritmos para o Problema dos K Menores Caminhos (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-20032018-003225/ -
NLM
Kykuta DH. Comparação de algoritmos para o Problema dos K Menores Caminhos [Internet]. 2018 ;[citado 2024 mar. 28 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-20032018-003225/ -
Vancouver
Kykuta DH. Comparação de algoritmos para o Problema dos K Menores Caminhos [Internet]. 2018 ;[citado 2024 mar. 28 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-20032018-003225/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas