Algoritmo de expancion minima
Páginas: 3 (550 palabras)
Publicado: 17 de junio de 2011
Algoritmo de expansión mínima
El algoritmo de expansión mínima enlaza los nodos de una red en forma directa o indirecta, con la mínima longitud de las ramas enlazantes. Una aplicacióncaracterística es en la construcción de carreteras pavimentadas que unen varias poblaciones. El camino entre dos poblaciones adicionales. El diseño más económico del sistema de caminos indica que se minimice ladistancia total de caminos pavimentados resultado que se obtiene implementando el algoritmo de árbol de expansión mínima.
Los dos pasos del procedimiento son los siguientes. Sea N = {1,2,…,n} elconjunto de nodos de la red, y se definen.
Ck = Conjunto de nodos que se han conectado.
^Ck = Conjunto de nodos que todavía se deben conectar en forma permanente.
Paso 1. El conjunto C0 = 0 y ^C0 =N.
Paso 2. Comenzar con cualquier nodo en el conjunto ^C no conectado (o “inconexo”), e igualar C1 = {i}, con lo que ^C1 = N – {1}. Igualar K = 2.
Paso general K. Seleccionar un nodo j* en elconjunto no conectado Ck-1. Enlazar a j* en forma permanente a j* en forma permanente con Ck-1 y sacarlo de ^Ck-1 esto es.
Ck = Ck-1 + {j*}, ^Ck = ^Ck-1 – {j*}
Si el conjunto ^Ck, de nodos no conectadoses vacio, detenerse. En cualquier otro caso, igualar k=k+1 y repetir el paso.
EJEMPLO:
Midwest TV Cable Company está en el proceso de proporcionar servicio de cable a cinco nuevas áreashabitacionales. En la figura 6.4 representa los enlaces disponibles en TV entre las cinco áreas. Las millas de cable se muestra en cada arco. Determine la red de cable mas económica. El algoritmo comienza en elnodo 1 (cualquier nodo podría ser), con lo que se obtiene.
C1 = {1}, ^C1 = {2, 3, 4, 5, 6}
Las iteraciones del algoritmo se resumen en la figura 6.5. Los arcos con línea delgada son todos los enlacesposibles entre C y ^C. Las ramas gruesas representan los enlaces permanentes entre los nodos del conjunto conectado (o “conexo”) C, y la rama con la línea interrumpida representa el nuevo enlace...
El algoritmo de expansión mínima enlaza los nodos de una red en forma directa o indirecta, con la mínima longitud de las ramas enlazantes. Una aplicacióncaracterística es en la construcción de carreteras pavimentadas que unen varias poblaciones. El camino entre dos poblaciones adicionales. El diseño más económico del sistema de caminos indica que se minimice ladistancia total de caminos pavimentados resultado que se obtiene implementando el algoritmo de árbol de expansión mínima.
Los dos pasos del procedimiento son los siguientes. Sea N = {1,2,…,n} elconjunto de nodos de la red, y se definen.
Ck = Conjunto de nodos que se han conectado.
^Ck = Conjunto de nodos que todavía se deben conectar en forma permanente.
Paso 1. El conjunto C0 = 0 y ^C0 =N.
Paso 2. Comenzar con cualquier nodo en el conjunto ^C no conectado (o “inconexo”), e igualar C1 = {i}, con lo que ^C1 = N – {1}. Igualar K = 2.
Paso general K. Seleccionar un nodo j* en elconjunto no conectado Ck-1. Enlazar a j* en forma permanente a j* en forma permanente con Ck-1 y sacarlo de ^Ck-1 esto es.
Ck = Ck-1 + {j*}, ^Ck = ^Ck-1 – {j*}
Si el conjunto ^Ck, de nodos no conectadoses vacio, detenerse. En cualquier otro caso, igualar k=k+1 y repetir el paso.
EJEMPLO:
Midwest TV Cable Company está en el proceso de proporcionar servicio de cable a cinco nuevas áreashabitacionales. En la figura 6.4 representa los enlaces disponibles en TV entre las cinco áreas. Las millas de cable se muestra en cada arco. Determine la red de cable mas económica. El algoritmo comienza en elnodo 1 (cualquier nodo podría ser), con lo que se obtiene.
C1 = {1}, ^C1 = {2, 3, 4, 5, 6}
Las iteraciones del algoritmo se resumen en la figura 6.5. Los arcos con línea delgada son todos los enlacesposibles entre C y ^C. Las ramas gruesas representan los enlaces permanentes entre los nodos del conjunto conectado (o “conexo”) C, y la rama con la línea interrumpida representa el nuevo enlace...
Leer documento completo
Regístrate para leer el documento completo.