free hosting   image hosting   hosting reseller   online album   e-shop   famous people

Método de Monte Carlo. Problema del viajero

Uno de los problemas difíciles de resolver es el problema del viajero: Dado un número N de ciudades a recorrer, ¿cual es el camino con el menor costo dada la tabla que se ve a continuación?:

Este fue un camino seleccionado, su costo es

(1-2) + (2-8) + (8-3) + (3-7) + (7-6) + (6-10) + (10-5) + (5-4) + (4-9) =
3 + 4 + 3 + 4 + 9 + 8 + 5 + 3 + 3 = 42

Este problema tiene N! posibles soluciones (un número muy grande) que aumenta enormemente por cada ciudad adicionada. La solución utilizando Método Monte Carlo es:

1. Genere una ruta inicial y evalúela

(1-2) + (2-8) + (8-3) + (3-7) + (7-6) + (6-10) + (10-5) + (5-4) + (4-9) =
3 + 4 + 3 + 4 + 9 + 8 + 5 + 3 + 3 = 42

2. Haga un cambio aleatorio a esa ruta y vuelva a ensayarla, si es mejor entonces esa nueva ruta se selecciona, si no entonces se deja la ruta anterior. En el ejemplo se intercambia las ciudades 3 y 4 y esta es la nueva ruta.

3. Determinar si es suficientemente buena la selección en caso contrario vuelva al paso 2.