Apuntes algoritmo nodo resuelto

Prévia do material em texto

Apuntes “Algoritmo del Nodo resuelto” 
El algoritmo del nodo resuelto es recomendable usar para problemas de ruta más corta, donde la red contiene arcos no dirigidos. Esto no quiere decir que este algoritmo no se pueda usar en el caso de una red dirigida, pero en el caso de una red dirigida en realidad es recomendable usar Dijkstra. Vamos a empezar planteando la siguiente red del libro Hillier & Lieberman.
4
1
7
3
1
4
7
5
4
2
5
2
D
T
E
C
B
A
O
	
A partir de la red anterior se recomienda construir una tabla como la siguiente que facilitara los cálculos.
	
	
	
	
	
	
	
	O
	A
	B
	C
	D
	E
	T
	O-A-2
	A-B-2
	B-C-1
	C-B-1
	D-E-1
	E-D-1
	
	O-C-4
	A-D-7
	B-A-2
	C-E-4
	D-B-4
	E-B-3
	
	O-B-5
	
	B-E-3
	
	D-T-5
	E-C-4
	
	
	
	B-D-4
	
	D-A-7
	E-T-7
	
El primer pasó realizado en la construcción de la tabla anterior; es que debe existir una columna por cada nodo de la red. Luego se empieza a partir de la columna del nodo de origen “O” a ver a cuales otros nodos podemos trasladarnos a través de un solo arco y estos arcos se ordenan en forma creciente, según la distancia que estos posean. Los nodos “A”, “B”, “C”, “D” y “E” pueden considerarse como nodos de transbordo y en igual forma el procedimiento que se realiza para el nodo “O” también se realiza en estos; pero los arcos que permiten llegar al nodo de origen a partir de estos nodos de transbordo no deben estar presentes en la tabla. El nodo “T” representa el nodo de destino y para este no se consideran arcos en la tabla.
El procedimiento descrito en el párrafo anterior aplica siempre que se tenga un problema de ruta más corta, donde la red tenga solamente arcos no dirigidos y se desea aplicar el algoritmo del nodo resuelto. En el caso de una red con arcos dirigidos la tabla se construye de forma similar con unas diferencias solamente.
Ahora bien vamos a empezar a desarrollar los cálculos correspondientes. Se empieza siempre asignando un valor de cero encima del nodo de origen, que indica la distancia más corta a ese nodo. Luego para cada nodo que tenga que tenga un valor asignado asignado encima se calcula la suma de este valor más el valor del arco de su misma columna no resaltada que tenga el número más pequeño; observar que en esta etapa se observa la utilidad de ordenar los arcos en forma creciente. Por ejemplo, el nodo “O” es el único nodo que hemos asignado un valor, luego el arco O-A con valor de 2 se le suma a el valor asignado al nodo “O”. Es decir; se efectúa 0 + 2 = 2.
Por consiguiente, el arco O-A se debe resaltar de color rojo de preferencia y para los arcos de la tabla que finalicen en “A” se deben tachar, el cual indicaremos su tachadura resaltándolos de color amarillo. En la iteración 1 se muestra el proceso descrito en forma precisa.
 Iteración 1
	0
	2
	
	
	
	
	
	O
	A
	B
	C
	D
	E
	T
	O-A-2
	A-B-2
	B-C-1
	C-B-1
	D-E-1
	E-D-1
	
	O-C-4
	A-D-7
	B-A-2
	C-E-4
	D-B-4
	E-B-3
	
	O-B-5
	
	B-E-3
	
	D-T-5
	E-C-4
	
	
	
	B-D-4
	
	D-A-7
	E-T-7
	
Es importante tener presente las siguientes condiciones que detallaremos para efectuar los cálculos.
Primera condición: Evaluar si todos los arcos de un nodo están resaltados ya sea de color rojo o amarillo o una mezcla de ambos. Si se cumple la condición este nodo no debe considerarse más para los cálculos. En caso contrario, pueden considerarse si pasan la segunda condición.
Segunda condición: Si el nodo no cumple la primera condición, entonces este nodo solamente puede considerarse para los cálculos solamente si tiene un valor asignado.
Entonces, a partir de la tabla anterior vemos primero que ningún nodo tiene todos sus arcos resaltados de rojo o amarillo o una mezcla de ambos, por lo que todos los nodos al parecer pueden considerarse para los cálculos. Sin embargo, vemos que los nodos “O” y “A” son los únicos que tienen un valor asignado y entonces solamente estos se consideran para los cálculos.
Por consiguiente, para el nodo “O” no puede considerarse el arco O-A porque esta resaltado de rojo, pero el que le sigue si O-C y se tiene 0 + 4 = 4. Para el nodo “A” puede considerarse el arco A-B y se tiene 2 + 2 = 4. Aquí vemos, que las sumas efectuadas reproducen el mismo valor y por lo tanto se resalta de rojo el arco O-C y A-B y se tachan todos los arcos que finalicen en “C” y “B”. 
. 
Iteración 2
	0
	2
	4
	4
	
	
	
	O
	A
	B
	C
	D
	E
	T
	O-A-2
	A-B-2
	B-C-1
	C-B-1
	D-E-1
	E-D-1
	
	O-C-4
	A-D-7
	B-A-2
	C-E-4
	D-B-4
	E-B-3
	
	O-B-5
	
	B-E-3
	
	D-T-5
	E-C-4
	
	
	
	B-D-4
	
	D-A-7
	E-T-7
	
Entonces, a partir de la tabla anterior vemos que el nodo “O” tiene todos sus arcos resaltados y este no se considera más para los cálculos. Sin embargo, los demás nodos aparentemente pueden considerarse para los cálculos, pero se observa que de estos nodos solo los nodos “A”, “B” y “C” tienen un valor asignado y estos son los que se consideran para los cálculos.
Para el nodo “A” el único arco que puede considerarse es el A-D y se tiene 2 + 7 = 9. Para el nodo “B” se considera el arco B-E y se tiene 4 + 3 = 7. Para el nodo “C” se considera el arco C-E y se tiene 4 + 4 = 8. El valor más pequeño es el 7 y por lo tanto se resalta de rojo el arco B-E y se tachan todos los arcos de la tabla que finalicen en “E”. 
Iteración 3
	0
	2
	4
	4
	
	7
	
	O
	A
	B
	C
	D
	E
	T
	O-A-2
	A-B-2
	B-C-1
	C-B-1
	D-E-1
	E-D-1
	
	O-C-4
	A-D-7
	B-A-2
	C-E-4
	D-B-4
	E-B-3
	
	O-B-5
	
	B-E-3
	
	D-T-5
	E-C-4
	
	
	
	B-D-4
	
	D-A-7
	E-T-7
	
Entonces, a partir de la tabla anterior vemos que el nodo “O” y “C” tiene todos sus arcos resaltados y este no se considera más para los cálculos. Sin embargo, los demás nodos aparentemente pueden considerarse para los cálculos, pero se observa que de estos nodos solo los nodos “A”, “B” y “E” tienen un valor asignado y estos son los que se consideran para los cálculos.
Para el nodo “A” el único arco que puede considerarse es el A-D y se tiene 2 + 7 = 9. Para el nodo “B” el único arco que puede considerarse es el B-D y se tiene 4 + 4 = 8. Para el nodo “E” se puede considerar el arco E-D y se tiene 7 + 1 = 8. Existen dos resultados iguales y por lo tanto se resalta de rojo los arcos B-D y E-D y los arcos que finalicen en “D” se tachan de la tabla.
Iteración 4
	0
	2
	4
	4
	8
	7
	
	O
	A
	B
	C
	D
	E
	T
	O-A-2
	A-B-2
	B-C-1
	C-B-1
	D-E-1
	E-D-1
	
	O-C-4
	A-D-7
	B-A-2
	C-E-4
	D-B-4
	E-B-3
	
	O-B-5
	
	B-E-3
	
	D-T-5
	E-C-4
	
	
	
	B-D-4
	
	D-A-7
	E-T-7
	
Entonces, a partir de la tabla anterior vemos que el nodo “O”, “A”, “B” y “C” tiene todos sus arcos resaltados y este no se considera más para los cálculos. Sin embargo, los demás nodos aparentemente pueden considerarse para los cálculos y como estos tienen un valor asignado los nodos “D” y “E” se consideran para los cálculos.
Para el nodo “D” el único arco que puede considerarse es el D-T y se tiene 8 + 5 = 13. Para el nodo “E” el único arco que puede considerarse es el E-T y se tiene 7 + 7 = 14. El valor más pequeño es 13 y por lo tanto el arco D-T se resalta de rojo y los demás arcos que terminen en “T” se tachan de la tabla.
Iteración 5
	0
	2
	4
	4
	8
	7
	13
	O
	A
	B
	C
	D
	E
	T
	O-A-2
	A-B-2
	B-C-1
	C-B-1
	D-E-1
	E-D-1
	
	O-C-4
	A-D-7
	B-A-2
	C-E-4
	D-B-4
	E-B-3
	
	O-B-5
	
	B-E-3
	
	D-T-5
	E-C-4
	
	
	
	B-D-4
	
	D-A-7
	E-T-7
	
Entonces, a partir de la tabla anterior vemos que todos los nodos tienen sus arcos resaltados y además tienen valor asignado y se puede concluir que la solución encontrada es la óptima. Entonces, la ruta más corta desde el nodo “O” al nodo “T” tiene un valor de 13.