Pós- Graduado

Universidade Federal do Rio de Janeiro
Escola Politécnica – MBA em Engenharia de Software
EEL 650 – Análise e Implementação de Algoritmos
Turma ENGSOFT21 – Prof. Heraldo L. S. Almeida
Grupo:
Carlos Eduardo Mercante Moura
Gustavo Samico de Queiroz
Ricardo Malízia
Thiago Martins Anginho

Trabalho Prático para Avaliação de Aproveitamento
Tema:
Inspeção de Rotas (route inspection)
Formulação Teórica:
Dado um grafo orientado com n vértices v1, v2, ... vn , m arestas a1, a2, ... am e custos c1, c2, ... cm associados a cada aresta, determinar o roteiro de menor custo que percorre cada aresta pelo menos uma vez.

Exemplo Prático:
Os caminhões de uma empresa de coleta de lixo precisam percorrer diariamente m ruas a1, a2, ... am, cujos comprimentos são dados por c1, c2, ... cm, e que se interceptam em n esquinas.
Determinar um roteiro que minimize a quilometragem total rodada diariamente pelos caminhões da empresa. Referências de Pesquisa: http://en.wikipedia.org/wiki/Route_inspection_problem http://www.cs.sunysb.edu/~algorith/files/eulerian-cycle.shtml http://www.seas.gwu.edu/~simhaweb/cs151/lectures/module9/module9.html http://xlinux.nist.gov/dads//HTML/chinesePostman.html http://pt.wikipedia.org/wiki/Caminho_euleriano http://www.inf.ufsc.br/grafos/temas/euleriano/euleriano.htm http://br.answers.yahoo.com/question/index?qid=20090504111842AA6cDwZ http://arxiv.org/ftp/cs/papers/0505/0505031.pdf http://pt.scribd.com/doc/67766815/Roteirizacao-de-veiculos http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382009000200005 http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0103-65132006000300014 1) Escolher e descrever um problema cuja resolução requeira a execução de algoritmos computacionais que não sejam triviais.
O problema escolhido por nossa equipe foi o de Inspeção de Rotas (route inspection).
Em teoria dos grafos, um ramo da matemática, o Problema do carteiro chinês (PCC),circuito do carteiro ou problema da