Page 159 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 159
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
Figura 7.5. Posibles trayectos
Para localizar la cota inferior se debe realizar la reducción de la matriz. La suma de todas las diferen-
cias será la cota inferior c(.). Retomando el primer ejemplo del agente viajero, se tiene:
Restando por hileras:
A la h se resta 10. Por lo tanto, r = 10
1
A la h se resta 2. Por lo tanto, r = 12
2
A la h se resta 2. Por lo tanto, r = 14
3
A la h se resta 3. Por lo tanto, r = 17
4
A la h se resta 4. Por lo tanto, r = 21.
5
La matriz resultante es:
153
