Algoritmos de resolución


Fuerza Bruta


El único algoritmo óptimo pero inabordable computacionalmente a partir de un cierto número de nodos. Su funcionamiento es intuitivo: generar todas las rutas posibles a partir de los \(n-1\) nodos dados, verificar que las rutas son caminos Hamiltonianos y tomar el menor de los caminos generados. Para poner de manifiesto la inoptimalidad de este algoritmo un ejemplo: para \(23\) nodos se genera un total de \(25\cdot 10^{21}\) rutas posibles.

Algoritmo Voraz


Los algoritmo voraces son otra opción para resolver el TSP y otros problemas similares. En este algoritmo se considera un conjunto de candidatos y a medida que avanza, se tiene un conjunto de candidatos elegidos y otro de candidatos rechazados. Así  pues será necesaria una función que determine que candidato es el más prometedor. Para el problema que nos ocupa, estará directamente relacionado con la optimalidad del camino.

Una versión de este algoritmo sería la heurística de "vecinos próximos" en el que la función elige recurrentemente el nodo más próximo al actual. Esta forma de resolverlo vuelve muy asequible al algoritmo pero no nos asegura su optimalidad - Como ya demostró Karl Menger -.


Backtracking


Con este algoritmo el primer paso es generar un camino - cualquiera - inicial para comparar. Este primer camino tiene un coste \(X\). A continuación de manera recursiva se generan otros caminos calculando el coste de este nuevo continuamente. Si en algún momento nos topamos con que una ruta alcanza un coste mayor que el inicial el algoritmo deshace todo - o parte del camino realizado - y vuelve a elegir otra opción de ruta buscando alcanzar un camino de coste menor o igual que \(X\).

Es evidente que este algoritmo consume más tiempo y recursos que el método voraz pero ofrece soluciones más óptimas.

Ramificación y Acotación

Este algoritmo se basa en plantear el TSP como un problema de programación lineal entera. Una vez planteado, se resuelve el problema sin imponer que las variables sean enteras (Problema relajado): 

\( (PR) \left. \begin{matrix}\text{min} & \sum\limits_{i,j=1}^n d_{i,j}x_{i,j}&\\  \text{s. a} & \sum\limits_{j=1}^{n} x_{i,j} = 1 &, i = 1,...,n\\ &\sum\limits_{i=1}^{n} x_{i,j} = 1 &, j = 1,...,n \\ & u_i - u_j + nx_{i,j}\leq (n-1) &, 1< i \neq j\leq n\\ & x_{i,j},u_i,u_j \geq 0 \end{matrix} \right. \)

Si alguna de las variables de la solución \(x^*\), no cumple la condición de integridad. Se impone la condición de que la variable sea mayor que su parte entera (\( x^*_{i,j}\geq [ x^*_{i,j}]\)) y se vuelve a resolver el problema relajado. Además, por separado, se resolverá el problema relajado con la restricción de que la variable sea menor que parte entera  (\( x^*_{i,j}<[ x^*_{i,j}]\)  ) .

Este proceso se repite hasta que todas las variables sean enteras y se llegue a la mejor solución posible. 


Última modificación: domingo, 11 de febrero de 2018, 15:23