Busca avançada
Ano de início
Entree

Algoritmos de aproximação para o problema do caixeiro viajante

Processo: 18/13448-3
Linha de fomento:Bolsas no Brasil - Iniciação Científica
Vigência (Início): 01 de setembro de 2018
Vigência (Término): 31 de agosto de 2019
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Pesquisador responsável:Mário César San Felice
Beneficiário:Rodrigo Prata Salmen
Instituição-sede: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brasil
Assunto(s):Problema do caixeiro viajante (PCV)   Otimização combinatória   Algoritmos de aproximação   Programação linear inteira   Métrica

Resumo

O problema do caixeiro viajante (TSP), em que temos um conjunto de cidades e queremos saber qual é o circuito de comprimento mínimo que passa por todas elas exatamente uma vez, é central na área de otimização combinatória e possui diversas aplicações práticas em áreas como planejamento, logística e manufatura de microchips. Neste projeto estamos interessados tanto na sua versão mais famosa, o TSP métrico, quanto em casos particulares e generalizações deste. Este projeto tem por objetivo a introdução do candidato à pesquisa científica, bem como a complementação de sua formação em Ciência da Computação, aprofundando seu conhecimento na área de otimização combinatória. Além disso, pretendemos que esta Iniciação Científica gere um relatório técnico que seja útil para outros estudantes iniciando na área.