Trabalho de conclusão de curso
O Problema do Carteiro Chinês
Aluno: Gabriel Fernandes de Oliveira
NUSP: 9345370
Supervisor: Prof. Carlos Eduardo Ferreira
Proposta
Motivação
O Problema do Carteiro Chinês é um problema da teoria dos grafos com muitas aplicações na área de logística de transportes e mesmo dentro da teoria dos grafos. O mesmo consiste em encontrar o circuito de menor custo em um grafo que percorra todas suas arestas ao menos uma vez.
Para o exemplo acima, uma solução ótima do problema é {A,B,D,C,A,D,C,B,A}, tal trajeto tem custo, ou distância, 12.
Este problema pode ser aplicado, por exemplo, ao planejamento de rotas de um caminhão de lixo ou rotas de entrega de cartas, serviços que comumente tem que realizar trajetos que percorram todas as ruas de um bairro ou cidade. Além disso, o mesmo também é dual de outro problema da área dos grafos: o problema de corte máximo em grafos planares.
Outro ponto interessante sobre o problema são suas muitas variações, como o problema do carteiro rural e a variação do problema com estradas íngrimes, para tais variações ainda não se conhece uma solução polinomial.
Objetivos
Este TCC dá continuidade a um estudo realizado em iniciação científica sobre o mesmo tema. São objetivos do trabalho:- Aprofundar os estudos já realizados na IC, criando pseudo-códigos, implementações e exemplos de execução, para os algoritmos descritos no trabalho.
- Abordar outras variações do problema, como o Problema do Carteiro Chinês Rural ou o Problema do Carteiro Íngreme (Windy Postman Problem) e conhecidas soluções heurísticas para os mesmos.
- Construir um material explicando o tema sem requerer conhecimento prévio sobre o problema. Pretendo ilustrar os problemas apresentados e suas soluções com muitos exemplos e explicá-los usando uma linguagem simples de se entender.
- Mostrar aplicações dos algoritmos estudados em problemas reais e em problemas teóricos de competições de programação.
- Procurar testar os algoritmos implementados, garantindo, do melhor modo possível, que os mesmos funcionem corretamente.
Cronograma
| Atividade | Abr | Mai | Jun | Jul | Ago | Set | Out | Nov | Dez | Jan |
|---|---|---|---|---|---|---|---|---|---|---|
| Adição de pseudo-códigos | • | • | • | • | ||||||
| Expandir e revisar a explicação do problema | • | |||||||||
| Introdução e estudo de variações do problema | • | • | • | |||||||
| Soluções aproximadas para variantes | • | • | • | |||||||
| Adição de exemplos e problemas solucionados | • | • | ||||||||
| Desenvolvimento de algoritmos | • | • | • | • | • | • | ||||
| Escrever a dissertação | • | • | • |
Tarefas em detalhe
Na aba tarefas pode-se encontrar algumas metas para cada um dos tópicos tratados no cronograma.
- Adição de pseudo-códigos: inicialmente para os algoritmos para o problema do carteiro chinês direcionado e não direcionado, que possuem solução polinomial e posteriormente para soluções aproximadas das variações.
- Expandir e revisar a explicação do problema: revisar o texto já produzido e adicionar informações sobre o problema das junções-T e sua relação com o problema do carteiro chinês.
- Introdução de variações do problema: tratar sobre mais variações do problema. Até o momento temos tratado em mais detalhes o problema do carteiro rural. Pretendo, ao menos, introduzir também as variações mais populares: o problema do carteiro hierárquico, e o problema do carteiro com ruas íngrimes.
- Soluções aproximadas para variantes: apresentar soluções com heurísticas para as variações tratadas ou casos específicos das mesmas.
- Adição de exemplos e problemas solucionados: ilustrar os conceitos já adicionados o texto com mais exemplos. Adicionar à seção "Problemas resolvidos" mais exemplos de problemas de juízes online solucionados que usem conceitos tratados no trabalho.
- Desenvolvimento de algoritmos: desenvolver códigos para os algoritmos explicados no texto, procurando também desenvolver testes para os mesmos.
Resultados
Apresentação para a SIICUSP 2020
Segue a apresentação de 8 minutos sobre o problema e os resultados obtidos na pesquisa.
Os slides usados na apresentação também estão disponíveis e podem ser acessados neste link.
Apresentação final
Slides adaptados da apresentação do SIICUSP para realizar a apresentação final da disciplina.