Problema do viaxeiro

 

O problema do vendedor viaxeiro describe un vendedor que debe viaxar entre N cidades. O obxectivo é atopar a ruta que minimice o custo total da viaxe, xa sexa en termos de distancia, tempo, ou custo económico, visitando cada cidade exactamente unha vez e regresando ao punto de inicio. Cada cidade está conectada con outras próximas por avións, estradas ou ferrocarrís.

Cada un deses enlaces entre as cidades ten un ou máis pesos (ou o custo) adxuntos. O custo describe o "difícil" que é atravesar esta aresta no grafo, e pode estar dado, por exemplo, polo custo dun billete de transporte, ou quizais pola lonxitude da aresta ou o tempo necesario para completar a travesía. O viaxeiro quere manter no menor posíbel tanto os gastos de desprazamento como a distancia a percorrer.^[6]

O problema do vendedor viaxeiro é un exemplo clásico dentro dunha ampla clase de problemas de optimización combinatoria "duros" que foron obxecto de estudo por matemáticos e informáticos durante anos. É particularmente relevante debido á súa aplicabilidade en aplicacións en ciencia e enxeñaría, e diversos campos como a loxística, onde se pode usar para optimizar rutas de entrega. Por exemplo, na fabricación dunha placa de circuíto, é importante determinar a mellor orde na que un láser perforará miles de buratos para minimizar o tempo total de produción e, por tanto, reducir os custos para o fabricante.^[7]

 

En xeral, o problema do vendedor viaxeiro é difícil de resolver. Se hai unha forma de dividir este problema en problemas de compoñentes máis pequenos, os compoñentes serán polo menos tan complexos como o orixinal. Isto é o que os científicos informáticos chaman problemas NP-hard (problema NP-difícil ou NP-complexo).^[8][9]

Moitas persoas estudaron este problema. A solución máis sinxela (e máis cara) é simplemente probar todas as posibilidades. O problema con isto é que para N cidades tes (N-1) posibilidades factoriais. Isto significa que para só 10 cidades hai máis de 180 mil combinacións para probar (xa que a cidade de inicio está definida, pode haber permutacións nas nove restantes). Só contamos a metade xa que cada ruta ten unha ruta igual ao revés coa mesma lonxitude ou custo. 9! / 2 = 181.440

• Pódense atopar solucións exactas ao problema, utilizando algoritmos de ramificación e poda.^[10] Isto é posible actualmente para até 85.900 cidades.^[11]
• Os enfoques heurísticos usan un conxunto de regras orientadoras para a selección do seguinte nodo. Pero dado que as heurísticas dan como resultado aproximacións, non sempre darán a solución óptima, aínda que as heurísticas admisibles de alta calidade poden atopar unha solución útil nunha fracción do tempo necesario para unha solución total por forza bruta do problema. Un exemplo de heurística para un nodo sería unha suma de cantos nodos non visitados están "próximos" a un nodo conectado. Isto podería animar ao vendedor a visitar un grupo de nodos próximos agrupados antes de pasar a outro natural do grafo. Véxanse o algoritmo de Monte Carlo e o algoritmo de Las Vegas.

• Problema das pontes de Königsberg
• Teoría de grafos

• TSPLIB Arquivado 25 de marzo de 2017 en Wayback Machine. Arquivado

Este artigo sobre matemáticas é, polo de agora, só un bosquexo. Traballa nel para axudar a contribuír a que a Galipedia mellore e medre.  Existen igualmente outros artigos relacionados con este tema nos que tamén podes contribuír.