El problema del viajante

Un viajante tiene que visitar una serie de pueblos. En cada pueblo, deja una batería cargada, y se lleva otra, descargada. Esa es pues su labor.

Las baterías son de ácido-plomo, lo que se traduce en que pesan. Mucho. Cada una. Y todas juntas pesan una barbaridad.

Para ahorrar costes, decide buscar la ruta más corta entre los pueblos. Coge su flamante GPS y... mal asunto: el GPS sólo le calcula la ruta óptima entre dos pueblos, pero no la ruta más corta entre todos ellos.

¡Que se compre otro GPS! Dirán algunos. Pero el problema no es el GPS. El problema es que hay demasiadas rutas posibles, y no sabemos buscar cuál es la mejor. Igual sabemos encontrar una que sea bastante buena. Si son pocos pueblos, quizá podamos encontrar la mejor. Si los pueblos forman una distribución que no deje lugar a dudas (por ejemplo: a todos se llega sólo por una carretera que los comunica) la solución puede ser trivial.

Pero en el caso general, cuando hay digamos N pueblos, el número de posibles rutas para visitar los pueblos, supuesto que no queremos visitar el mismo dos veces, es de 1/2(n-1)!, si n>2.

Para que nos hagamos una idea, para n=6, (n-1)! = 120, osea que ya hay 60 posibles rutas.
n=7, (n-1)! = 720, lo cual nos deja 360 rutas.

A medida que va aumentando el número de pueblos a visitar, el número de rutas crece una barbaridad. Por mucho ordenador que tengamos, siempre podemos encontrar un número "relativamente pequeño" de pueblos por el que pasar, que supongan tantas rutas que el ordenador no sea capaz de calcular la mejor.

Este problema del viajante (hoy en día sería el comercial de la empresa) representa una clase de problemas que entre nosotros llamaremos NP-Chungos. Osea, verdaderamente abigarrados y difíciles de resolver, con unas aproximaciones la mar de complicadas.

Aunque claro, siempre nos quedará xkcd ;-).

Ojo, que esto que digo no contradice el hecho de que un aparatito de GPS (con su cartografía y su programa) sea capaz de encontrar la ruta óptima entre DOS puntos. Que obviamente los hay, y funcionan.




P.D: Para n=1000, osea, 1000 poblaciones, el numerajo nos queda algo como:

20119363003854688677185121696150199285968743210535731627189995521496
92561993145102960221042434847024002399943050985980293158334364974042
79450661914834972295498712252043536879959411813863594366259889752975
49763806043748773124852180070913904732324814552819694371894324366855
95905229128918239249885062383164449179778677162565926619792315377787
04557131208737174673776714323288305833898698334410145603689571926859
79412490406343391918727986587306804268976726211079329660096404543914
86542156964222016406157793055184884006786521080843738048379356741560
12739294660383584566224213118065706254390104000130841575513670913988
85239231793408508218251207684569914063240510654638062244817996435255
74824877099546711107834162860404106665930584057768079182734920233544
87801450475268808237923864210944839823122472580382676704099450692721
24399247997665955086167777830106972519986814037506891880765356388096
34245171763126000079442675736658058510519840879607554538940096965890
57097272628611932770730531446093980111919485738044253138431483573337
34878145561704121960408007689044494698225913162183580838108958445488
99559518770156373111449940025977222071410060936808729963214782908733
14151477785149512162076590808605232916018393453058630079391760375758
14211277013258524165211307198714346653084544898424129506272916358411
32290332633849793263411364035378906959290894448261040821741724129966
33021683830088499806415930394193075139732977565578276018046994090306
06927930015071784726361210317231589873029734128655189504201221621923
28286225072014109426262354675953104645115682466367487827569793602798
27114374887005706673481357711422931188693769115241932844488230963691
90745007038365522332012994974511111088295216995094300928326324253089
98511780969485089300204059448649591555105856149229508209605344421935
60927823062480399361454259648409686194321307419828691145561562512093
32467657198506871426596332493766860947034714071705926007900706167241
40075256998471450767415388222845495365762166391441349323013949321605
69541753108547501298694931777138598371411124378793382876172110103786
81528474941254398446408137692443169845497991314047806072549743585062
22582306301895146545604445434710142553200910771997285784029709363744
99047127371086791200531838702297870892580414615067679040920048498186
26211528042795185031213562170845450207684505296699191788896970548501
38767360000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000 posibles rutas. Por comentar...