Una Heurística es un conjunto de técnicas o métodos utilizados para resolver problemas. En lugar de buscar una solución completamente lógica y óptima, la Heurística se enfoca en encontrar una solución rápida e intuitiva de manera creativa. Se basa en la experiencia y el pensamiento divergente para abordar problemas de manera más efectiva
En el Problema del Vendedor Viajero, la Heurística de Christófides (1976) permite resolver con una aproximación al óptimo el costo mínimo de recorrer todos los nodos desde y hacia un nodo inicial.
En este ejemplo A, de debe pasar por todos los nodos, y devolverse al nodo A al costo mínimo.
Grafo Ejemplo Heurística Christófides
El primer paso que tenemos que hacer es encontrar el Árbol Mínimo de Envergadura Máxima. Se denomina Árbol Mínimo de Envergadura Máxima, al árbol que conecta todos los nodos de la red al menor costo posible.
Entonces vamos a resolver que de cada nodo sale cada rama al menor costo.
En el ejemplo, del nodo A la rama que sale con menor costo es esta que conecta hacia E y es 600. Del nodo B, el menor costo posible es 550 y conecta a O.
Y así vamos a completar el Árbol Mínimo de Envergadura Máxima.
Árbol Mínimo de Envergadura Máxima
Si ustedes se fijan, de cada nodo sale la rama con costo mínimo. Salen uno o dos brazos dependiendo de la situación.
Por ejemplo, desde el nodo A tenemos 650, 600, 1.340 y 300, sale la conexión hacia E que es 600. Y así con todos los nodos.
La idea obviamente es conectar todos los nodos, por eso, en este caso, entre los nodos K y G, este valor es más pequeño, sin embargo, sale esta rama hacia I, porque se necesita conectar todos los nodos y este último quedaría fuera.
El segundo paso en esta heurística corresponde conectar los nodos impares que salen del Árbol Minimo de Envergadura Máxima. En el grafo todo lo que está con rojo, hay nodos que son impares. Entonces tenemos que detectar ahora aquellos nodos que son impares. En este ejemplo, desde A sale una ruta, desde N sale una ruta, en M que salen 3 rutas, en O sale solamente 1, en B salen 3 rutas, en D salen 3 rutas, en el nodo P sale una sola ruta, y en el nodo K sale una ruta. Entonces tenemos identificados todos los nodos que son impares.
Ahora lo que tenemos que hacer es conectar los nodos impares para eliminar la imparidad en el problema. Al conectar los nodos impares, nos queda una nueva situación y ya podemos trazar un tur que nos permite conectar el nodo A, dar toda la vuelta por todos los nodos y regresar a A.
Solución Christófides (Ruta en verde)
Esta solución es cercana al óptimo. No es la solución óptima. La solución óptima se hace con modelos de programación lineal propias de la Investigación de Operaciones.
Tenemos que la ruta óptima sería: A, N, A, E, M, O, B, D, C, P, H, L, D, F, H, L, G, J, I, K, G, J, y termina en A. Tenemos que conectar los nodos J y A obviamente, para poder darle final al ciclo.
Finalmente, con la Heurística de Christófides, el problema queda resuelto de esta manera explicada en este artículo.
Teorema Propiedad fundamental del Árbol Mínimo de Envergadura Máxima
Supongamos que hemos descubierto un procedimiento para encontrar un Árbol Mínimo de Envergadura Máxima y que, durante su construcción, usando este procedimiento, debemos dividir el grafo G en K subárboles distintos, tales que se cumpla que cada uno de los árboles sea un subgrafo de G y que:
N1 U N2 U ... U Nk = N, con Ni ∩ Nj = 0 para i ≠ j.
Notar que un subgrafo puede consistir en un solo nodo de G.
Corolario: En un grafo no dirigido G, el arco más corto que sale de cualquier nodo, pertenece al Árbol Mínimo de Envergadura Máxima.
Algoritmo para obtener el Árbol Mínimo de Envergadura Máxima
Se basa en el corolario de la Propiedad Fundamental y consta de los siguientes tres pasos:
Paso 1: Escoger arbitrariamente un nodo i del grafo G(N,A). Encontrar el arco más corto que sale de i, e incluirlos en el Árbol Mínimo de Envergadura Máxima. Los empates se rompen en forma arbitraria.
Paso 2: Encontrar el arco más corto que sale del conjunto de nodos que ya han sido incluidos en el Árbol Mínimo de Envergadura Máxima e incorporarlo a su vez.
Paso 3: Si todos los nodos ya han sido conectados, parar. Si no, ir al Paso 2.
Heurística de Christofides para el PVV
Paso 1: Encontrar el Árbol Mínimo de Envergadura Máxima para el grafo G(N,A) en consideración y llamar T a este nuevo grafo.
Paso 2: Sea n0 el número de nodos impares existentes en T. Encontrar un pareamiento de costo mínimo para estos nodos y llamar M al subgrafo formado por los arcos contenidos en el pareamiento de costo mínimo. Crear un grafo G que sea igual a M U T (Éste va a ser un grafo “euleriano”, es decir, sin nodos de grado impar).
Paso 3: Trazar un Tour de Euler sobre el grafo G que empiece y termine en el nodo inicial (que es un dato del problema). El circuito constituye una solución aproximada al PVV.
Teorema: Si la matriz de distancias en un tour de vendedor viajero representa distancias euclidianas, entonces la solución optima al PVV no puede cortarse a si misma.
Paso 4: Comprobar si en la solución del Paso 3 existen arcos que crucen o nodos que sean visitados mas de una vez y mejorar dicha solución haciendo uso de la desigualdad triangular.