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
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
Gabarito comentado
