Busca avançada
Ano de início
Entree

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

Processo: 18/13448-3
Modalidade de apoio: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
Palavra(s)-Chave do Pesquisador:Algoritmos de Aproximação | Problema do Caixeiro-Viajante | programação linear inteira | Otimização combinatória

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.

Matéria(s) publicada(s) na Agência FAPESP sobre a bolsa:
Matéria(s) publicada(s) em Outras Mídias (0 total):
Mais itensMenos itens
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)