Ruta Mas Corta
Páginas: 3 (676 palabras)
Publicado: 17 de octubre de 2012
LA RUTA MAS CORTA
El problema de la ruta más corta incluye un juego de nodos conectados donde sólo un nodo es considerado como el origen y sólo un nodo es considerado como el nodo destino. Elobjetivo es determinar un camino de conexiones que minimizan la distancia total del origen al destino.
Se trata de encontrar la ruta de menor distancia, o costo, a entre el punto de partida o nodoinicial y el destino o nodo terminal.
DEFINICIÓN DEL PROBLEMA
* -Se tienen n nodos, partiendo del nodo inicial 1 y terminando en el nodo final n.
* -Arcos bi-direccionales conectan los nodos condistancias mayores que cero.
* -Se desea encontrar la ruta de mínima distancia que conecta el nodo 1 con el nodo n.
Por medio de la aplicación del algoritmo de este problema podemos conocer lamenor distancia entre un nodo origen y un nodo destino
PASOS A SEGUIR:
1. Elaborar un cuadro con todos los nodos y los ramales que salen de él.
2. Partiendo del origen, debemos encontrar elnodo más cercano a él.
3. Anular todos los ramales que entren al nodo más cercano elegido.
4. Comenzando en el origen se debe encontrar el nodo más cercano a él, por intermedio del(los)nodo(s) ya elegido(s) y volver al tercer paso hasta llegar al destino
EJEMPLO:
ARBOL DE EXPANSION MINIMA
un árbol de expansión minima es aquel que conecta todos los nodos dentro de una red, que esta enuna distancia minima y que no contiene un ciclo.
PASOS PARA ELABORAR UN ARBOL DE EXPANSION MINIMA:
* Seleccionar cualquier nodo de la red o indicado según el problema
* Colocar este nodo almas cercano que minimice la distancia y proseguir considerando todos los nodos que estén conectados, escogiendo de igual manera el que tenga la minima distancia, hasta incluir todos los nodos. Si losnodos son de igual valor se selecciona uno arbitrariamente, y esto quiere decir que puede haber mas de una solución optima
Método de la ruta crítica
El Método CPM (Critical Path Method), fue...
El problema de la ruta más corta incluye un juego de nodos conectados donde sólo un nodo es considerado como el origen y sólo un nodo es considerado como el nodo destino. Elobjetivo es determinar un camino de conexiones que minimizan la distancia total del origen al destino.
Se trata de encontrar la ruta de menor distancia, o costo, a entre el punto de partida o nodoinicial y el destino o nodo terminal.
DEFINICIÓN DEL PROBLEMA
* -Se tienen n nodos, partiendo del nodo inicial 1 y terminando en el nodo final n.
* -Arcos bi-direccionales conectan los nodos condistancias mayores que cero.
* -Se desea encontrar la ruta de mínima distancia que conecta el nodo 1 con el nodo n.
Por medio de la aplicación del algoritmo de este problema podemos conocer lamenor distancia entre un nodo origen y un nodo destino
PASOS A SEGUIR:
1. Elaborar un cuadro con todos los nodos y los ramales que salen de él.
2. Partiendo del origen, debemos encontrar elnodo más cercano a él.
3. Anular todos los ramales que entren al nodo más cercano elegido.
4. Comenzando en el origen se debe encontrar el nodo más cercano a él, por intermedio del(los)nodo(s) ya elegido(s) y volver al tercer paso hasta llegar al destino
EJEMPLO:
ARBOL DE EXPANSION MINIMA
un árbol de expansión minima es aquel que conecta todos los nodos dentro de una red, que esta enuna distancia minima y que no contiene un ciclo.
PASOS PARA ELABORAR UN ARBOL DE EXPANSION MINIMA:
* Seleccionar cualquier nodo de la red o indicado según el problema
* Colocar este nodo almas cercano que minimice la distancia y proseguir considerando todos los nodos que estén conectados, escogiendo de igual manera el que tenga la minima distancia, hasta incluir todos los nodos. Si losnodos son de igual valor se selecciona uno arbitrariamente, y esto quiere decir que puede haber mas de una solución optima
Método de la ruta crítica
El Método CPM (Critical Path Method), fue...
Leer documento completo
Regístrate para leer el documento completo.