Problema do viaxeiro

miniatura| Ruta óptima dun vendedor que visita as 15 cidades máis grandes de Alemaña. A ruta mostrada é a máis curta das 43.589.145.600 posibles.
O **problema do vendedor viaxeiro** ou **problema do viaxeiro** (ás veces chamado **TSP** *Traveling Salesman Problem* polas súas siglas en inglés) é un problema algorítmico clásico no campo da informática e da investigación operativa. Está centrado na optimización. Neste contexto, *unha mellor solución* adoita significar *unha solución que é máis barata, máis curta ou máis rápida*. TSP é un problema matemático que se expresa máis facilmente como un gráfico que describe as localizacións dun conxunto de vertices ou nodos.
[miniatura| [William Rowan Hamilton foi o primeiro en definir o problema de TSP.]]
O **problema do viaxeiro** foi definido no 1800 polo matemático irlandés W.R. Hamilton e polo matemático británico Thomas Kirkman. O *Icosian Game* de Hamilton foi un puzzle recreativo baseado en atopar un ciclo hamiltoniano (*Hamiltonian cycle* ou *Hamiltonian path*). A forma xeral do TSP parece que foi estudada por primeira vez polos matemáticos durante a década de 1930 en Viena e en Harvard, especialmente por Karl Menger. Menger define o problema, considera o obvio algoritmo de forza bruta e observa a non-optimalidade da heurística do algoritmo do veciño máis próximo:

## Enunciando o problema 
miniatura| Exposición do problema do viaxeiro: Un vendedor quere visitar todas as cidades, A, B, C e D. Cal é a mellor forma de facelo (billetes de avión máis baratos e tempo de viaxe mínimo)?
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.

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.

## Dificultade 
miniatura|Representación dun problema do  viaxeiro, mostrando unha rede de cidades e as rutas optimizadas entre elas.
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).

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. Isto é posible actualmente para até 85.900 cidades.
* 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.

## Notas 
## Véxase tamén 
* Problema das pontes de Königsberg
* Teoría de grafos

### Ligazóns externas 
* TSPLIB  Arquivado