Page 158 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 158

INTRODUCCIÓN AL ANÁLISIS  DE ALGORITMOS


                             hileras y columnas que contienen solo ∞. Cada diferencia a cero se suma en la
                             variable r. La matriz resultante será B. Ya realizadas todas las substracciones del
                             paso anterior, entonces:

                              c (S) = c (R) + A<i, j> + r para nodos hoja c (.) = c( ).

                             Siendo S el número de nodo actual.

                             Siendo R el número de nodo padre.




                  Los dos primeros pasos son válidos y no existirá un recorrido en el subárbol S que contenga las
                  aristas del tipo <j, k> o <k, j> o <j, 1> (excepto para la arista <i, j>). En este momento r es el monto
                  total substraído del paso 3, entonces c(S) = c(R) + A<i, j> + r. Para los nodos hoja є(.) = c() es fácil
                  calcular, ya que cada rama hasta la hoja define un único recorrido. Para la función de la cota superior
                  u, se requiere usar u(R) = ∞ para todo nodo R.

                  Siendo S el número de nodo actual.

                  Siendo R el número de nodo padre.




                  Para ver el árbol de transición se tomará el siguiente ejemplo:









                  Tomando la notación de la transición:

                  I = y
                  s
                  donde

                  I indica en este caso transición.

                  s indica el nivel //nodo hijo.

                  y indica la columna.




                  De esta forma el árbol de trayectorias para el ejemplo quedaría como se muestra en la figura 7.5:










                                                              152
   153   154   155   156   157   158   159   160   161   162   163