Download Nodos - Universia

AnAnálisis de redes de
transporte
Tr
Muchas veces se utiliza en aplicaciones
que nada tienen que ver con el transporte
Resumen
Antecedentes y definiciones
El camino más corto
Árbol de expansión mínima
Introducción a los problemas del viajante
de comercio y del cartero chino
Recordatorio continuo
del capítulo 3
Añadimos calles discontinuas, como
máximo 1/3 de la longitud de un bloque
en distancia media de desplazamiento
¿Y si se cambia a una red dirigida, esto
es, alternando calles de un solo sentido?
Con las redes de transporte, se discretiza
la geografía
Red ilustrativa
A
B
C
D
E
Red con terminología
B
A
Nodos B y D
C
D
Arco dirigido
E
Arco no dirigido
Ejemplos de nodos y arcos
Nodos
Intersecciones
de calles
Poblaciones
Ciudades
Empalmes eléctricos
Fases principales del proyecto
Arcos
Segmentos de calles
Carreteras secundarias
Tiempo de desplazamiento
en aviones
Componentes de
circuito
Tareas del proyecto
Los arcos pueden tener “longitudes”
4
B
A
2
1
1
5
C
D
3
6
17
E
Longitudes de arco
Los nodos pueden tener “peso”
100 A
B 200
50 C
D 100
Pesos del nodo
E
50
¿Ejemplos de pesos de nodo?
Número de habitantes
% de cierta población
por zona
% de uso de
electricidad por zona
Podemos viajar por CAMINOS
B
A
Camino: A
C
D
E
C
D
E
Un camino especial es un CICLO
A
B
C
D
E
Ciclo : C
D
E
C
Algunos ejemplos de redes
Metro de
Boston
Red de
autopistas principales de Seattle
Red del ferry
de Seattle
Redes de telecomunicación
Terminología de redes
N = conj. de nodos
A = conj. de arcos
G(N,A)
Arco incidente
Nodos adyacentes
Arcos adyacentes
Camino
Grados de un nodo
Grado de salida
Grado de entrada
Ciclo o circuito
Nodos conectados
Grafo no dirigido
conectado
Grafo dirigido
fuertemente conectado
Subgrafo
Terminología de redes (cont.)
El árbol de una red
no dirigida
es un subgrafo
conectado sin ciclos
El árbol de expansión
de G(N,A) contiene
todos los n
nodos de N
Longitud de un camino S
Un árbol con t
nodos contiene (t-1)
aristas
L(S) =
∑ l(i, j)
(i, j )∈S
d(x,y), d(i,j)
Ahora pasemos a algunos
problemas de decisión de redes
Diseño o despliegue de
una red
Problemas de ruta
El problema del camino más corto
El problema del viajante de comercio
El problema del cartero chino
El problema del camino más corto
Halle el camino más corto entre
dos nodos, comenzando en el
nodo O y terminando en el D.
– O: Origen (nodo)
– D: Destino (nodo)
Algoritmo de etiquetado de nodos:
Dijkstra
Camino más corto entre nodos
k=1, comienzo en el nodo de origen
Al final de la iteración k, el conjunto de k
NODOS CERRADOS consiste en los k
nodos más cercanos al origen.
Cada NODO ABIERTO adyacente a uno o
más nodos cerrados tiene nuestra mejor
solución en curso de la distancia mínima
a dicho nodo.
Algoritmo de Dijkstra (cont.)
Cada mejor solución representa un camino factible,
quizá optimo
Siguiente paso: cierre el más cercano de las
MEJORES SOLUCIONES.
Ejecute un bucle para actualizar las mejores soluciones.
Repita reemplazando k con k+1.
O
(1,0)
5
3
3
2
8
4
2
5
4
6
1
10
D
(k,d)=(iteración k, min. distancia a nodo O)
Red de complejidad computacional
con n nodos
Cada iteración: hasta n comprobaciones
Hasta n iteraciones
Implica complejidad O(n2)
Para todo el grafo: complejidad O(n3)
El problema del árbol de
expansión mínima (MST)
Considere un grafo no dirigido
¿Por qué es un problema importante?
Problema: encontrar un árbol de expansión
de distancia mínima de G(N, A).
Si |N|=n, entonces cada árbol de
expansión contiene (n-1) enlaces.
Es posible que el MST no sea único
MST
Algoritmo: comience en un nodo arbitrario
Siga conectando al subárbol creciente
el nodo libre más cercano.
Prueba por contradicción
T1
Prueba por contradicción
T1
T2
MST = T1 + T2 + (un enlace de conexión)
Prueba por contradicción
6
7
9
5
11
T1
T2
MST = T1 + T2 + (un enlace de conexión)
Corolario
En una red no dirigida G, el enlace de
distancia más corta que salga de
cualquier nodo es parte del MST.
Otro algoritmo MST
Clasifique los arcos por longitud y súmelos
a la solución incumbente del árbol (un
grupo de subárboles), asegurándose de
no crear ciclos.
Se trata de un buen algoritmo manual
pero resulta más difícil de automatizar
en la computadora.
Complejidad computacional
del MST
Tomemos una G completamente conectada
Iteración nº1: (n-1) comparaciones para
hallar el mínimo. Etiquete cada nodo
con la distancia al nodo inicial.
Complejidad computacional
del MST
Iteración nº2:
– Hallar las distancias a partir de los nodos
recién añadidos a cada nodo que no está en
el árbol y cambiar las etiquetas si procede.
Requiere (n-2) comparaciones.
– Hallar el mínimo de etiquetas. Requiere
(n-2) comparaciones adicionales.
Complejidad computacional
del MST
Iteración nºj:
– Hallar las distancias a partir de los nodos
recién añadidos a cada nodo que no está en
el árbol y cambiar las etiquetas si procede.
Requiere (n-j) comparaciones.
– Hallar el mínimo de etiquetas. Requiere
(n-j) comparaciones adicionales.
nº cálculos = (n − 1) + 2
n
(
∑ n − j) =
j=2
2(n − 1) + 2(n − 2) + ... + 2 − (n − 1) =
n(n − 1)
2
− (n − 1)
2
2
⇒ O(n )
Problema del viajante de comercio
Hallar el ciclo más corto
empezando y terminando en el nodo
O y visitando cada nodo especificado
A, B, C, etc. al menos una vez.
14
4
B
A
2
1
5
1
5
C
D
2
1
7
H
I
3
6
E
1
2
3
17
G
F
7
6
J
Ejemplo del viajante de comercio:
Haga el mejor ciclo uniendo los nodos azules
El problema del cartero chino
Hallar el ciclo o el camino de
distancia mínima que pasa por cada
enlace al menos una vez.
Un problema famoso
Los siete puentes de Konigsberg
N = Orilla norte
Isla A
Isla B
S = Orilla sur
Reducido a una red
Los siete puentes de Konigsberg como una red
N
A
B
S
El cartero chino: fácil
Un problema del cartero chino sencillo
El cartero chino: emparejamiento
D
E
8
5
5
6
6
5
A
C
8
5
B
D
Emparejamiento nº 2
E
8
5
5
6
6
5
A
C
8
5
B
D
Emparejamiento nº 3
E
8
5
5
6
6
5
A
C
8
5
B
Cada uno de estos problemas se ha
refinado y ampliado a lo largo de los
años
Cada uno se puede implementar vía ordenador en entornos operativos complejos
Correos, FEDX, caminoneros, incluso
mensajeros en bici utilizan estas técnicas