En mi anterior post intentamos definir lo que eran los problemas y cuál era el camino a seguir para solucionarlos. Hoy vamos a plantear un problema típico y muy sencillo, pero con una resolución compleja: el problema del viajante de comercio. El enunciado es el siguiente:

Suetorp es un vendedor de una remesa de droides astromecánicos de la serie R3. Quiere hacer una ruta por el planeta Tatooine recorriendo su principales ciudades, y parte de la capital, Bestine.

Rutas de comercio en Tatooine

Las líneas en rojo marcan las rutas seguras para viajar en este planeta. Nuestro intrépido comerciante debe pasar por todas las ciudades y debe plantearse cuál es el recorrido más barato, es decir, el que gaste menos combustible sin pasar dos veces por el mismo lugar. ¿Cuál es la ruta que debe elegir el comerciante para minimizar el coste?

El problema aparentemente es sencillo, pero el número de combinaciones que tenemos que sopesar es bastante amplio.

Evidentemente nos encontramos ante un grafo con pesos. Estos pesos tendrán el valor de la distancia que tenemos que recorrer para llegar a la ciudad de destino.

¿Qué es un grafo con pesos?

Un grafo es una representación de la información compuesta por nodos, los cuales guardan una información sobre el elemento, y arcos, que unen a los nodos y aportan información sobre la relación que existe entre ellos. Esta información puede ser numérica, y en ese caso es llamada peso.

Grafo con las ciudades que tiene que visitar el mercader

Gracias a este grafo podemos representar el mapa y analizaremos cuál es el camino óptimo.

Muy bien, ¿y cómo encontramos el camino más corto?

Es muy difícil alcanzar la solución óptima probando todas las opciones porque nos encontramos con una infinidad de casos, por lo que tendremos que utilizaremos una serie de algoritmos que nos permitan alcanzar la resolución del problema. Éstos son llamados algoritmos de búsqueda. Durante las siguientes semanas intentaremos resolver el problema aplicando diferentes métodos y analizaremos cómo son de eficientes.

Antes de nada intentemos pensar como haría cualquier ser humano para resolver un problema. Pongamos un ejemplo:

Ahora mismo estáis sentados delante del ordenador pensar como saldríais de la habitación (la verdad que en esas situaciones los humanos poseen sensores periféricos que son bastante útiles), imaginaros en que lugar estamos, eres un punto rojo en una habitación, hay muchos obstáculos analizamos el camino y rápido encontramos la salida.

¿Como lo haría una máquina? De la misma forma.

1. Si conocemos la habitación lo primero sería coger referencias intentar saber donde estamos (sensores como brújulas electrónicas, ultrasonidos, infrarrojos, hasta sensores de visión artificial, nos pueden dar pistas), en definitiva, poner un punto rojo en la habitación, es decir, caracterizar el estado de origen.
2. Después buscar. Existen infinitas formas de salir de una habitación, pero algunas son más rápidas que otras (dar vueltas alrededor de la habitación hasta llegar a la puerta no es muy útil) y  algunas son muy buenas. Las mejores soluciones son las óptimas.
3. Llevamos a cabo la solución durante este proceso iremos pasando por muchos lugares, esto cambia por completo la situación, nos podemos encontrar obstáculos no previstos, que el objetivo ha cambiado de lugar o que no estamos realmente donde pensábamos. Hasta llegar a la puerta pasamos por múltiples estados y esto puede alterar la resolución de nuestros problemas, hasta el punto de que se convierta en un problema sin solución.
4. Cuando la máquina llega a la puerta detecta que ha cumplido el objetivo llega a su estado final, y ya puede intentar resolver otros problemas.

Si generalizamos podemos ver que resolver cualquier problema se puede hacer en los siguientes pasos.

1. Caracterizar el estado inicial.
2. Encontrar la solución óptima partiendo de ese estado.
3. Cambiar de estado y revisar la solución.
4. Detectar que se ha alcanzado el estado final.

La complejidad de esto reside en como conseguir cumplir cada uno de los objetivos, dependiendo de la situación. Pero eso lo dejaremos para más adelante.