O
problema do carteiro é dos mais simples de resolver porque o caminho óptimo se
obtém sempre da mesma maneira.
Devem ser definidas fronteiras de forma a
contornarem os constrangimentos.
Uma fronteira ao contornar um constrangimento
herda os pontos do raio que em teoria pertenceriam a fronteiras mais
interiores.
Um constrangimento total é o que obriga a um
percurso pelo raio até à origem e neste caso a fronteira deve passar a conter também o ponto da origem.
As fronteiras devem ser classificadas por ordem
de exterioridade sendo a fronteira mais externa a 1 e o ponto de origem a
enésima fronteira, chamamos a estas fronteiras, tenham elas a forma que tiverem
círculos do carteiro.
O conjunto das fronteiras definidos deve
passar por todos os pontos que se pretendam alcançar.
Cada fronteira definida só pode conter os seus
próprios pontos ou o ponto de origem e mais nenhum ponto de outra fronteira.
Solução
do carteiro
O carteiro começa por ir até ao primeiro círculo do carteiro, pelo raio do carteiro mais curto possível, e que atravesse o
menor número de círculos do carteiro, desde o enésimo, a origem, até ao primeiro, o círculo do carteiro número 1.
Depois percorre o círculo do carteiro num dos sentidos possíveis,
o que é indiferente, ou o horário ou o anti-horário.
Quando a próxima casa, for uma das casas já visitadas, então percorre a perpendicular a este círculo, o raio, até ao primeiro ponto do novo círculo mais interior, e percorre este círculo no
sentido contrário ao sentido utilizado para percorrer o círculo anterior, até
que a próxima casa seja uma das casas já visitados, e repete o processo até
chegar à origem e ter todas as casas já visitadas.
O pior cenário, é o caso dos constrangimentos
serem tantos que todos os movimentos se façam pelos raios e não pelos círculos,
e neste caso e só neste caso, o número de passagens pela casa de origem será
igual ao dobro do número de pontos da fronteira exterior, sem contar com o ponto de origem, a percorrer.
No melhor cenário a casa de origem só será
ponto de partida e de chegada e não estará contido por nenhum círculo do carteiro.
A demonstração passa por serem verdadeiras as seguintes afirmações:
- A curva mais compacta que existe num plano é o circulo;
- A distância mais curta entre dois círculos é a diferença entre os seus raios;
Se já estiver estabelecido um percurso para o
carteiro, ao adicionar-se uma casa ao percurso, a solução mais viável para
refazer o percurso do carteiro é adicionar essa casa a um dos círculos do carteiro previamente definidos e reordenar os pontos desse círculo.
Sem comentários:
Enviar um comentário