En el post anterior enunciamos el problema del viajante de comercio. Comentamos que las dimensiones del problema eran demasiado grandes como para abordarlas sin realizar ningún tipo de poda o intentando evitar caminos que nos lleven a situaciones ya ocurridas. Aunque a esta conclusión llegamos mediante la intuición, y no estimamos cuánto tiempo tardaríamos en buscar todas las combinaciones.

Si intentamos evaluar la complejidad del problema, nos damos cuenta de que si nuestro querido comerciante de androides quiere recorrer 18 ciudades y queremos valorar todas las opciones, deberemos calcular todas las combinaciones de 18 elementos, que son 18! posibilidades, es decir, 6.402.373.705.728.000. Si para calcular cada una de las posibilidades empleamos 1µs, necesitaríamos un poco más de 203 años para terminar de comprobar cada una de las posibilidades. Naturalmente eso es mucho tiempo y en ese tiempo se pueden crear ciudades, abandonar otras, o que la Estrella de la Muerte pase por ahí y se cargue el planeta.

Una vez que ha quedado claro el espacio de configuraciones, que vamos a denotar como Ω, vamos a formular una función matemática denominada función de energía, que cuantificará el coste de cada una de sus configuraciones. En este problema la funcion de energía es evidente, ya que equivale a la distancia que recorremos en cada uno de los ciclos completos. Si llamamos cada una de la permutaciones ∏(1)∏(2)∏(3)…∏(N), entonces el coste de un ciclo es:

Donde d(x, y) es la distancia que existe entre las ciudades de x e y.

Teniendo definidas la dimensión del problema y la función de energía, nuestro problema va a consistir en hacer que la configuración mínima sea la menor posible; de esta manera recorreremos todas la ciudades de la manera más óptima.

Por ahora lo dejamos aquí, ya que en próximos posts aplicaremos la distribución de Gibbs para conseguir un nuevo parámetro de control que nos facilite la solución del problema: la temperatura. También simularemos los procesos de templado que se utilizan para endurecer el metal, que nos servirán en nuestro problema para intentar descubrir cuál es la configuración óptima. Tomen aliento, esto acaba de empezar.