Download Nodos - Universia
Document related concepts
Transcript
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