Existe um bom aplicativo móvel que resolve o problema do caixeiro-viajante, dada uma lista de cidades?

Computar o caminho mais curto de um nó de uma rede para outro nó de uma rede é um problema relativamente simples. Este não é o problema do caixeiro-viajante.

No problema do caixeiro-viajante, você tem que desenhar um caminho que passa por vários nós intermediários. Entretanto, é possível atravessar os nós intermediários em qualquer ordem. Qual ordem fornece o caminho mais curto não é óbvio.

Considerar um bloco de papel que ele marcou em 1/4″ quadrados. Suponha que cada quadrado seja de fato um quadrado perfeito. Pegue todas as intersecções das linhas como seus "nós", e as linhas entre elas como seus "links" . Suponha que você precisa traçar um caminho que cruze cada nó da página e volte ao nó inicial. É óbvio que há um grande número de maneiras de fazer isso, e que todos os caminhos têm exatamente o mesmo comprimento total para o caminho percorrido.

Ponha que você altere o problema em uma pequena quantidade, de modo que alguns dos links ainda sejam 1/4″ de comprimento, e alguns sejam 1% mais longos. Agora está claro que com uma pequena mudança no problema algumas soluções, especificamente as soluções que evitam os links ligeiramente mais longos, são melhores do que algumas outras soluções.

Faça outra pequena mudança no problema, de modo que os links que tinham sido 1% mais longos sejam agora 1% mais curtos. Como você alterou o problema em apenas uma pequena quantidade, o valor de qualquer solução não é muito diferente. No entanto, se você precisava encontrar a melhor solução, é claro que a natureza da solução ótima pode ter mudado radicalmente, pelo menos no sentido de que você está tomando um caminho completamente diferente através da rede.

Uma característica dos problemas NP-duros é que uma mudança muito pequena no problema pode resultar em uma mudança muito grande na forma da solução ótima. Outra característica é que normalmente existem soluções diferentes que são muito próximas em termos de quão "óptimas" são, mas muito diferentes em termos da forma da solução.