Vamos a calcular la solución del Problema del Viajante, en un grafo ponderado, calculando TODOS los ciclos de Hamilton y eligiendo el menor. La manera de introducir los pesos de las aristas es de forma ordenada (j,k), 1 ≤ j ≤ v-1, j < k ≤v, siendo v el número de vértices.

La  función  w(j,k), nos da el peso que une los vértices j < k de la lista del grafo. Extendemos el peso para valores k < j, de manera simétrica, con la función peso:

w[j_, k_, grafo_] := grafo[[(j - 1) (2v - j)/2 + k - j]]

peso[j_, k_, grafo_] := If[j<k, w[j, k, grafo], w[k, j, grafo]]

Fijamos el vértice 1 y calculamos las permutaciones de los v-1 restantes:

permutaciones[v_] := Permutations[Table[k, {k, 2, v}]]

Finalmente definimos la función que calcula el peso del ciclo mínimo, y un ciclo solución:

problemadelviajante[grafo_] := Block[{v, lon, ciclos = {}, ciclos2, per, con, fac, min, solu ... a en el ciclo ", Append[Join[{1}, per[[primersolu[[2]]]] ], 1] ]] ]

Consideramos el triángulo de manera que w(1,2)=1, w(1,3)=2 y w(2,3)=3:

problemadelviajante[{1, 2, 3}]

El camino mínimo mide 6 y se alcanza en el ciclo  {1, 2, 3, 1}

Tomamos ahora los grafos completos con v=3,4,...,10 puntos, con sucesión de pesos dada por {1,2,...,v(v-1)/2}. Observamos cómo los tiempos van creciendo factorialmente, y para v=10 se necesitan 4 minutos:

Do[Print[Timing[problemadelviajante[Table[j, {j, k (k - 1)/2}]]]], {k, 3, 10}]

El camino mínimo mide 6 y se alcanza en el ciclo  {1, 2, 3, 1}

{0.001749 Second, Null}

El camino mínimo mide 14 y se alcanza en el ciclo  {1, 2, 3, 4, 1}

{0.003528 Second, Null}

El camino mínimo mide 27 y se alcanza en el ciclo  {1, 3, 2, 4, 5, 1}

{0.010107 Second, Null}

El camino mínimo mide 46 y se alcanza en el ciclo  {1, 4, 2, 5, 3, 6, 1}

{0.050834 Second, Null}

El camino mínimo mide 73 y se alcanza en el ciclo  {1, 4, 5, 2, 6, 3, 7, 1}

{0.366396 Second, Null}

El camino mínimo mide 108 y se alcanza en el ciclo  {1, 5, 2, 6, 3, 7, 4, 8, 1}

{2.78638 Second, Null}

El camino mínimo mide 154 y se alcanza en el ciclo  {1, 5, 6, 2, 7, 3, 8, 4, 9, 1}

{24.7495 Second, Null}

El camino mínimo mide 210 y se alcanza en el ciclo  {1, 6, 2, 7, 3, 8, 4, 9, 5, 10, 1}

{246.895 Second, Null}

Este ejemplo corresponde a las distancias entre 1=Londres, 2= México DF, 3=Nueva York, 4=París, 5=Pekín y 6=Tokio:

problemadelviajante[{56, 35, 2, 51, 60, 21, 57, 78, 70, 36, 68, 68, 51, 61, 13}]

El camino mínimo mide 192 y se alcanza en el ciclo  {1, 3, 2, 6, 5, 4, 1}

problemadelviajante[{2, 19, 1, 9, 14, 10, 4, 7, 3, 6}]

El camino mínimo mide 17 y se alcanza en el ciclo  {1, 2, 5, 3, 4, 1}

problemadelviajante[{20, 12, 22, 17, 41, 11, 21, 19, 25, 28, 33, 9, 27, 16, 43}]

El camino mínimo mide 94 y se alcanza en el ciclo  {1, 3, 6, 4, 2, 5, 1}

Created by Mathematica  (May 1, 2006) Valid XHTML 1.1!