Um caminhão precisa recolher o lixo das ruas de um certo bairro. Por questões econômicas e ambientais, a empresa IMJ, responsável pela coleta, planeja as rotas de recolhimento, de modo que o caminhão percorra a menor distância possível, passando em cada rua exatamente uma vez, entrando e saindo de cada ponto. Quando isso não é possível, busca-se repetir o menor número possível de ruas na rota. Na figura, temos um esquema no qual os pontos representam esquinas, e as linhas representam as ruas.
Considere que cada rua mede 150 m de comprimento e que a rota do caminhão comece e termine no ponto A, passando por todas as ruas do esquema.
A empresa conseguiu encontrar a melhor rota de recolhimento de lixo, na qual o caminhão percorre uma distância igual a
Carregando comentários…