Tabla 5: Un problema del vendedor viajero (TSP).
Tabla 5: Un problema del vendedor viajero (TSP).
La dificultad está una vez más en definir los niveles, estados y decisiones. Una forma natural es que el nivel t represente las ciudades t visitadas, y la decisión es donde ir a continuación. ¿Cuáles son los estados?. Supongamos que elegimos la ciudad en la que estamos como un estado. No se podría tomar la decisión de donde seguir a continuación ya que no sabemos lo que se ha realizado anteriormente. En consecuencia, el estado debe incluir información acerca de todas las ciudades visitadas, más la ciudad a donde queremos terminar. Luego, un estado estará representado por el par (i,S) donde S es el conjunto de t ciudades ya visitadas e i es la última ciudad visitada ( así i debe estar en S). Usando recursividad se tiene:
Los cálculos en el nivel 3 son:
Se recomienda realizar los cálculos. Un aspecto importante de
este problema es la NP-completitud. El espacio de búsqueda es tan
grande que llega a ser imposible encontrar una solución, aún
para problemas de tamaño pequeño. Por ejemplo suponga un
problema con 20 ciudades, el número de estados en el 10-ésimo
nivel es más de un millón. Para 30 ciudades, el número
de estados en el nivel 15 es más de un billón. Y para 100
ciudades, el número de estados en el nivel 50 es más de 5,000,000,000,000,000,000,000,000,000,000.
Este no es un problema fácil de resolver aún con una configuración
computacional ideal.
Siguiente:Recursividades no sumativasArriba:Tutorial Anterior:Reemplazo Equipamiento