Problema do carteiro

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:

1.   A curva mais compacta que existe num plano é o circulo;
2.   A distância mais curta entre dois círculos é a diferença entre os seus raios;

Acrescentar um novo ponto de passagem

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.

Ou seja o problema do carteiro é linear e não exponencial, porque pode ser reduzido à soma de funções lineares como o é a função do perímetro, funções do tipo 2πr, ou seja, em que os números de casas de cada círculo é proporcional ao raio desse círculo, sendo que se a casa a acrescentar for de uma fronteira mais exterior se tem de renumerar no máximo todos os pontos dessa fronteira, e apenas os pontos dessa fronteira.