Algoritmo matricial de shumbel
Páginas: 3 (668 palabras)
Publicado: 9 de junio de 2010
ALGORITMO MATRICIAL DE SHUMBEL
Este algoritmo propuesto por Shumbel en Structure in Communication Net, Symposium of Information Networks en 1954, establece un procedimiento para hallar latrayectoria de valor máximo o valor mínimo, usando productos de matrices a partir de la matriz inicial de costos o adyacencia.
ALGORITMO DE SHUMBEL
Sea M la matriz de valores asociados a un grafo G, lacual se representa por [pic] donde los elementos [pic] se definen de dos formas:
a. Si se desea encontrar la matriz de valor mínimo, se establece:
[pic]
b. Si se desea encontrar latrayectoria de valor máximo, se define:
[pic]
La matriz de trayectorias de valor óptimo es [pic] en donde n es el número de nodos en el grafo.
Si en un momento dado se obtiene [pic]= [pic], siendo m< n – 1 la matriz [pic] es la matriz de trayectorias de valor optimo, o sea que la matriz de valor optimo se obtiene del calculo de las siguientes potencias: [pic], [pic], [pic], [pic],… donde lasoperaciones matriciales se definen de la siguiente forma:
a. Si se trata de hallar la trayectoria de valor mínimo:
El producto de las dos matrices dará origen a otra matriz C obtenida así:[pic]
Ósea que en la matriz C resultante cada uno de sus elementos es el mínimo de las parejas de sumas de los elementos de las filas de la primera matriz con los elementos de las columnas delas segunda matriz.
b. Si se trata de hallar la trayectoria de valor máximo:
Los elementos de la matriz producto son de la forma:
[pic]
Ósea que en la matriz C resultante cada uno desus elementos es el máximo de las parejas de sumas de los elementos de las filas de la primera matriz con los elementos de las columnas de las segunda matriz.
Ejemplo:
Determinar los valores delas trayectorias más cortas de todos los nodos del siguiente grafo.
[pic]
Paso 1: La matriz de valores asociados al grafo es:
A B C D E...
Este algoritmo propuesto por Shumbel en Structure in Communication Net, Symposium of Information Networks en 1954, establece un procedimiento para hallar latrayectoria de valor máximo o valor mínimo, usando productos de matrices a partir de la matriz inicial de costos o adyacencia.
ALGORITMO DE SHUMBEL
Sea M la matriz de valores asociados a un grafo G, lacual se representa por [pic] donde los elementos [pic] se definen de dos formas:
a. Si se desea encontrar la matriz de valor mínimo, se establece:
[pic]
b. Si se desea encontrar latrayectoria de valor máximo, se define:
[pic]
La matriz de trayectorias de valor óptimo es [pic] en donde n es el número de nodos en el grafo.
Si en un momento dado se obtiene [pic]= [pic], siendo m< n – 1 la matriz [pic] es la matriz de trayectorias de valor optimo, o sea que la matriz de valor optimo se obtiene del calculo de las siguientes potencias: [pic], [pic], [pic], [pic],… donde lasoperaciones matriciales se definen de la siguiente forma:
a. Si se trata de hallar la trayectoria de valor mínimo:
El producto de las dos matrices dará origen a otra matriz C obtenida así:[pic]
Ósea que en la matriz C resultante cada uno de sus elementos es el mínimo de las parejas de sumas de los elementos de las filas de la primera matriz con los elementos de las columnas delas segunda matriz.
b. Si se trata de hallar la trayectoria de valor máximo:
Los elementos de la matriz producto son de la forma:
[pic]
Ósea que en la matriz C resultante cada uno desus elementos es el máximo de las parejas de sumas de los elementos de las filas de la primera matriz con los elementos de las columnas de las segunda matriz.
Ejemplo:
Determinar los valores delas trayectorias más cortas de todos los nodos del siguiente grafo.
[pic]
Paso 1: La matriz de valores asociados al grafo es:
A B C D E...
Leer documento completo
Regístrate para leer el documento completo.