Page 157 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 157
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
Figura 7.4. Un ejemplo de la reducción de una matriz
La matriz corresponde a una gráfica con cinco vértices. Todo recorrido incluye exactamente una
arista <i, j> con i = k, 1 ≤k ≤ 5 y exactamente una arista <i, j> con j = k, 1 ≤ k ≤ 5, substrayendo una
constante t de todos los elementos en una hilera o una columna de la matriz de costos se reduce
el tamaño de cada recorrido exactamente t unidades. Un recorrido de costo mínimo se mantiene
después de esta operación de sustracción. Si t se escoge para hacer mínima la entrada en la hilera
i (columna j), restando i de todas las entradas en la fila i (columna j), presentará un cero en la fila i
(columna j). Repitiendo este procedimiento tanto como sea necesario, la matriz de costos puede ser
reducida. El monto total substraído de todas las columnas e hileras es el límite inferior y puede ser
utilizado como el valor c de la raíz del árbol de espacio de estado. Substrayendo 10, 2, 2, 3, 4, de
las hileras 1, 2, 3, 4, 5. Posteriormente, sustrayendo 1 y 3 en las columnas 1 y 3 respectivamente
de la matriz del inciso b) de la figura 7.4, se tiene la matriz reducida del inciso c) de la misma figura.
El monto total substraído es 25. Por lo tanto, todo recorrido del origen a origen tiene una longitud al
menos de 25 unidades.
Con todos los nodos del agente viajero del árbol de estados se puede asociar una matriz de costos.
Sea A la matriz de costos del nodo R. Sea S el hijo de R tal que la arista del árbol (R, S) corresponde
a la arista <i, j> en el recorrido. Si S no es una hoja entonces la matriz de costo para S puede ser
obtenida de la siguiente forma:
1. Al escoger el trayecto <i, j>, cambiar todo valor en la hilera i y columna j de
A por ∞. Esto previene el uso de algunas aristas salientes del vértice i o vértices
entrantes de j.
2. Colocar A(j,1) en ∞. Esto previene el uso de aristas <j, 1>.
3. Reducir todas las hileras y columnas en la matriz resultante excepto para las
151
