Problema del Viajante de Comercio

Dado un grafo con valores asignados a las aristas, este problema trata de encontrar un camino de coste mínimo que recorra cada nodo exactamente una vez y que termine en el nodo inicial. Utilizando el símil del viajante de comercio, se trata de recorrer todas las ciudades de una zona exactamente una vez empezando y terminando en la misma ciudad.

Se trata por lo tanto de un problema de optimización. No existe solución mediante un esquema voraz, por lo tanto tendremos que usar el esquema de ramificación y poda.

El procedimiento es el siguiente:

• El algoritmo parte de un nodo inicial.
• Se recorre el árbol de búsqueda, siguiendo el orden de los nodos de menor coste estimado y explorando sus ramificaciones.
• A la hora de explorar las ramificaciones, se comprueba que los nodos no están incluidos aún en la ruta.
• Además, se comprueba si se ha alcanzado una solución, y si ésta es mejor que la solución óptima actual, se actualiza.
• La estimación optimista se realiza sumando el coste de la ruta de los vértices ya asignados y el coste mínimo de cualquier trayecto que complete la ruta.
• En este caso no se puede calcular una estimación pesimista para realizar podas, pues el problema podría no tener solución.

Ejemplos de aplicaciones prácticas

• Planificación de rutas.
• Scheduling: Asignación de tareas a procesadores.
• Diseño de circuitos electrónicos.