LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS

algoritmo Edmonds o Chu-Liu / Edmonds' algoritmo es un algoritmo para encontrar una que abarca arborescencia de peso mínimo (a veces llamado una ramificación óptima ). Es el análogo dirigidodel problema del árbol de expansión mínimo . El algoritmo fue propuesto independientemente primero por Yoeng-Jin Chu y Tseng-Hong Liu (1965) y luego por Jack Edmonds (1967).

Algoritmo [ editar ]

Descripción [ editar ]

El algoritmo toma como entrada una gráfica dirigida. $${\ displaystyle D = \ langle V, E \ rangle} dónde $${\ displaystyle V} es el conjunto de nodos y $${\ displaystyle E} Es el conjunto de aristas dirigidas, un vértice distinguido. $${\ displaystyle r \ en V}Llamado la raíz , y un peso de valor real.$${\ displaystyle w (e)} para cada borde $${\ displaystyle e \ en E}. Devuelve una arborescencia abarcadora. $${\ displaystyle A} enraizado en $${\ displaystyle r} de peso mínimo, donde el peso de una arborescencia se define como la suma de sus pesos de borde, $${\ displaystyle w (A) = \ sum _ {e \ en A} {w (e)}}.

El algoritmo tiene una descripción recursiva. Dejar$${\ displaystyle f (D, r, w)} denota la función que devuelve una arborescencia abarcadora arraigada en $${\ displaystyle r}de peso mínimo. Primero eliminamos cualquier borde de$${\ displaystyle E} cuyo destino es $${\ displaystyle r}. También podemos reemplazar cualquier conjunto de bordes paralelos (bordes entre el mismo par de vértices en la misma dirección) por un solo borde con un peso igual al mínimo de los pesos de estos bordes paralelos.

Ahora, para cada nodo $${\ displaystyle v} aparte de la raíz, encuentre el borde entrante a $${\ displaystyle v}De menor peso (con los lazos rotos arbitrariamente). Denota la fuente de esta arista por$${\ displaystyle \ pi (v)}. Si el conjunto de aristas.$${\ displaystyle P = \ {(\ pi (v), v) \ mid v \ en V \ setminus \ {r \} \}} No contiene ciclos, entonces $${\ displaystyle f (D, r, w) = P}.

De otra manera, $${\ displaystyle P}contiene al menos un ciclo. Selecciona arbitrariamente uno de estos ciclos y llámalo.$${\ displaystyle C}. Ahora definimos un nuevo grafo dirigido ponderado.$${\ displaystyle D ^ {\ prime} = \ langle V ^ {\ prime}, E ^ {\ prime} \ rangle} en que el ciclo $${\ displaystyle C} se "contrae" en un nodo de la siguiente manera:

Los nodos de $${\ displaystyle V ^ {\ prime}} son los nodos de $${\ displaystyle V} no en $${\ displaystyle C}más un nuevo nodo denotado$${\ displaystyle v_ {C}}.

• Si $${\ displaystyle (u, v)} es una ventaja en $${\ displaystyle E} con $${\ displaystyle u \ notin C} y $${\ displaystyle v \ en C} (un borde que entra en el ciclo), luego incluir en $${\ displaystyle E ^ {\ prime}} una nueva ventaja $${\ displaystyle e = (u, v_ {C})}, y definir $${\ displaystyle w ^ {\ prime} (e) = w (u, v) -w (\ pi (v), v)}.
• Si $${\ displaystyle (u, v)} es una ventaja en $${\ displaystyle E} con $${\ displaystyle u \ en C} y $${\ displaystyle v \ notin C} (un borde que se aleja del ciclo), luego incluir en $${\ displaystyle E ^ {\ prime}} una nueva ventaja $${\ displaystyle e = (v_ {C}, v)}, y definir $${\ displaystyle w ^ {\ prime} (e) = w (u, v)}.
• Si $${\ displaystyle (u, v)} es una ventaja en $${\ displaystyle E} con $${\ displaystyle u \ notin C} y $${\ displaystyle v \ notin C} (un borde no relacionado con el ciclo), luego incluir en $${\ displaystyle E ^ {\ prime}}una nueva ventaja $${\ displaystyle e = (u, v)}, y definir $${\ displaystyle w ^ {\ prime} (e) = w (u, v)}.

Para cada borde en $${\ displaystyle E ^ {\ prime}}, recordamos en qué borde $${\ displaystyle E} corresponde a

Ahora encuentra un mínimo arborescencia que abarca $${\ displaystyle A ^ {\ prime}} de $${\ displaystyle D ^ {\ prime}} usando una llamada a $${\ displaystyle f (D ^ {\ prime}, r, w ^ {\ prime})}. Ya que$${\ displaystyle A ^ {\ prime}}es una arborescencia en expansión, cada vértice tiene exactamente un borde entrante. Dejar$${\ displaystyle (u, v_ {C})} ser la única ventaja entrante para $${\ displaystyle v_ {C}} en $${\ displaystyle A ^ {\ prime}}. Este borde corresponde a un borde.$${\ displaystyle (u, v) \ en E} con $${\ displaystyle v \ en C}. Quitar el borde$${\ displaystyle (\ pi (v), v)} desde $${\ displaystyle C}, rompiendo el ciclo. Marca cada borde restante en$${\ displaystyle C}. Para cada borde en$${\ displaystyle A ^ {\ prime}}, marca su borde correspondiente en $${\ displaystyle E}. Ahora definimos$${\ displaystyle f (D, r, w)} para ser el conjunto de bordes marcados, que forman una arborescencia de expansión mínima.

Observa eso $${\ displaystyle f (D, r, w)} se define en términos de $${\ displaystyle f (D ^ {\ prime}, r, w ^ {\ prime})}, con $${\ displaystyle D ^ {\ prime}} teniendo estrictamente menos vértices que $${\ displaystyle D}. Hallazgo$${\ displaystyle f (D, r, w)} para un gráfico de un solo vértice es trivial (es solo $${\ displaystyle D} sí), por lo que se garantiza que el algoritmo recursivo terminará.

Tiempo de ejecución [ editar ]

El tiempo de ejecución de este algoritmo es $${\ displaystyle O (EV)}. Una implementación más rápida del algoritmo debido a Robert Tarjan se ejecuta en el tiempo$${\ displaystyle O (E \ log V)}para gráficos escasos y$${\ displaystyle O (V ^ {2})}Para gráficos densos. Esto es tan rápido como el algoritmo de Prim para un árbol de expansión mínimo no dirigido. En 1986, Gabow, Galil, Spencer, Compton y Tarjan produjeron una implementación más rápida, con tiempo de ejecución$${\ displaystyle O (E + V \ log V)}.

De Wikipedia, la enciclopedia libre

Saltar a navegaciónSaltar a búsqueda

Un EMST de 25 puntos aleatorios en el plano.

El árbol de expansión mínimo de Euclides o EMST es un árbol de expansión mínimo de un conjunto de n puntos en el plano (o más generalmente en ℝ ^d ), donde el peso del borde entre cada par de puntos es la distancia euclidianaentre esos dos puntos. En términos más simples, un EMST conecta un conjunto de puntos utilizando líneas de manera que la longitud total de todas las líneas se minimice y se pueda acceder a cualquier punto desde cualquier otro siguiendo las líneas.

En el plano, se puede encontrar un EMST para un conjunto dado de puntos en Θ ( n log n ) tiempo utilizando el espacio O ( n ) en el modelo de cálculo de árbol de decisión algebraico . Se conocen algoritmos de complejidad aleatorios más rápidos O ( n  log log  n ) en modelos de computación más potentes que modelan con mayor precisión las capacidades de las computadoras reales. ^[1]

En dimensiones más altas ( d ≥ 3), encontrar un algoritmo óptimo sigue siendo un problema abierto .

Límite inferior [ editar ]

Se puede establecer un límite inferior asintótico de Ω ( n log n ) para la complejidad temporal del problema EMST en modelos de cálculo restringidos, como el árbol de decisión algebraica y los modelos de árbol de cálculo algebraico , en los que el algoritmo solo tiene acceso a los puntos de entrada a través de ciertas primitivas restringidas que realizan cálculos algebraicos simples en sus coordenadas: en estos modelos, el problema de par de puntos más cercano requiere time ( n  log  n ) tiempo, pero el par más cercano es necesariamente un borde de la EMST, por lo que la EMST también lo requiere mucho tiempo. ^[2]Sin embargo, si los puntos de entrada tienen coordenadas enteras y operaciones a nivel de bits y se permiten las operaciones de indexación de tablasutilizando esas coordenadas, entonces son posibles algoritmos más rápidos. ^[1]

Algoritmos para calcular las EMST en dos dimensiones [ editar ]

El algoritmo más simple para encontrar un EMST en dos dimensiones, dados n puntos, es construir el gráfico completo en n vértices, que tiene n ( n -1) / 2 bordes, calcular cada peso de borde al encontrar la distancia entre cada par de puntos, y luego ejecute un algoritmo de árbol de expansión mínimo estándar (como la versión del algoritmo de Prim o el algoritmo de Kruskal ) en él. Dado que este gráfico tiene edges ( n ² ) aristas para n puntos distintos, la construcción ya requiere Ω ( n ² ) tiempo. Esta solución también requiere Ω (n ² ) espacio para almacenar todos los bordes.

Un mejor enfoque para encontrar la EMST en un plano es observar que es un subgrafo de cada triangulación de Delaunay de los n puntos, un conjunto de bordes muy reducido:

1. Calcule la triangulación de Delaunay en tiempo O ( n log n ) y espacio O ( n ). Debido a que la triangulación de Delaunay es un gráfico plano , y no hay más de tres veces más bordes que vértices en cualquier gráfico plano, esto genera solo bordes O ( n ).
2. Etiqueta cada borde con su longitud.
3. Ejecute un algoritmo de árbol de expansión mínimo en este gráfico para encontrar un árbol de expansión mínimo. Puesto que hay O ( n ) los bordes, esto requiere O ( n log n tiempo) utilizando cualquiera de los mínimos estándar que abarca algoritmos de árboles tales como el algoritmo de Borůvka , el algoritmo de Prim , o el algoritmo de Kruskal .

El resultado final es un algoritmo que toma O ( n log n ) tiempo y O ( n ) espacio.

Si las coordenadas de entrada son enteros y se pueden usar como índices de matriz , son posibles algoritmos más rápidos: la triangulación de Delaunay se puede construir mediante un algoritmo aleatorio en O ( n  log log  n) tiempo previsto. ^[1] Además, dado que la triangulación de Delaunay es un gráfico plano , su árbol de expansión mínimo se puede encontrar en tiempo lineal mediante una variante del algoritmo de Borůvka que elimina todo menos el borde más barato entre cada par de componentes después de cada etapa del algoritmo. ^[3] Por lo tanto, el tiempo total esperado para este algoritmo es O ( n  log log  n ). ^[1]

Dimensiones superiores [ editar ]

El problema también puede generalizarse a n puntos en el espacio d -dimensional ℝ ^d . En dimensiones superiores, la conectividad determinado por la triangulación de Delaunay (que, del mismo modo, divide el casco convexo en d -dimensional simplices ) contiene el árbol de expansión mínimo; sin embargo, la triangulación podría contener el gráfico completo. ^[4] Por lo tanto, encontrar el árbol de expansión mínimo euclidiano como un árbol de expansión de la gráfica completa o como un árbol de expansión de la triangulación de Delaunay toma tiempo O ( dn ² ). Para tres dimensiones es posible encontrar el árbol de expansión mínimo en el tiempo O (( n log n ) ^4/3 ), y en cualquier dimensión mayor que tres es posible resolverlo en un tiempo que sea más rápido que el límite de tiempo cuadrático para el gráfico completo y los algoritmos de triangulación de Delaunay. ^[4] Para conjuntos de puntos uniformemente aleatorios, es posible calcular los árboles de expansión mínima tan rápido como la clasificación. ^[5] Usando una descomposición de pares bien separados , es posible producir una aproximación (1 + ε) en tiempo O ( n log n ). ^[6]

Subtítulo de la triangulación de Delaunay [ editar ]

Todos los bordes de un EMST son bordes de un gráfico de vecindad relativo , ^{[7] [8] [9]} que a su vez son bordes de un gráfico de Gabriel , que son bordes en una triangulación de puntos de Delaunay , ^[10] [11] como se puede probar a través de la declaración contrapositivaequivalente : cada borde que no esté en una triangulación de Delaunay tampoco está en ninguna EMST. La prueba se basa en dos propiedades de árboles de expansión mínima y triangulaciones de Delaunay:

1. (la propiedad del ciclo de árboles de expansión mínima): para cualquier ciclo C en el gráfico, si el peso de un borde e de C es mayor que el peso de otros bordes de C, este borde no puede pertenecer a un MST .
2. (una propiedad de las triangulaciones de Delaunay): si hay un círculo con dos de los puntos de entrada en su límite que no contiene otros puntos de entrada, la línea entre esos dos puntos es un borde de cada triangulación de Delaunay.

Considere un borde e entre dos puntos de entrada p y q que no es un borde de una triangulación de Delaunay. La propiedad 2 implica que el círculo C con e como su diámetro debe contener algún otro punto r dentro. Pero entonces r está más cerca de p y q de lo que están uno con el otro, por lo que el borde de p a q es el borde más largo en el ciclo de puntos p → q → r → p , y por propiedad 1 e no está en cualquier EMST.

Tamaño esperado [ editar ]

El tamaño esperado de la EMST para grandes cantidades de puntos ha sido determinado por J. Michael Steele . ^[12] Si$${\ displaystyle f} es la densidad de la función de probabilidad para los puntos de selección, luego para grandes $${\ displaystyle n} y $${\ displaystyle d \ neq 1}El tamaño de la EMST es de aproximadamente

$${\ displaystyle c (d) n ^ {\ frac {d-1} {d}} \ int _ {\ mathbb {R} ^ {d}} f (x) ^ {\ frac {d-1} {d }} dx}

dónde $${\ displaystyle c (d)} Es una constante que depende solo de la dimensión. $${\ displaystyle d}. El valor exacto de las constantes se desconoce, pero puede estimarse a partir de evidencia empírica.

Aplicaciones [ editar ]

Una aplicación obvia de los árboles de expansión mínima de Euclides es encontrar la red más barata de cables o tuberías para conectar un conjunto de lugares, asumiendo que los enlaces cuestan una cantidad fija por unidad de longitud. Sin embargo, mientras estos proporcionan un límite inferior absoluto en la cantidad de conexión necesaria, la mayoría de estas redes prefieren un gráfico conectado a k a un árbol, de modo que la falla de un enlace individual no dividirá la red en partes.

Otra aplicación de EMST es un algoritmo de aproximación de factor constante para resolver aproximadamente el problema del vendedor ambulante euclidiano , la versión del problema del vendedor ambulante en un conjunto de puntos en el plano con bordes marcados por su longitud. Esta variación realista del problema se puede resolver en un factor de 2 mediante el cálculo de la EMST, haciendo un recorrido a lo largo de su límite que describe todo el árbol, y luego eliminando todas las apariciones de cada vértice de este recorrido.

Realización planar [ editar ]

El problema de realización para los árboles de expansión mínima de Euclides se explica de la siguiente manera: Dado un árbol T  = ( V ,  E ), encuentre una ubicación D ( u ) para cada vértice u  ∈  V, de modo que T sea ​​un árbol de expansión mínimo de D ( u ) : u ∈ V, o determinar que no existen tales ubicaciones. La prueba de la existencia de una realización en el plano es NP-dura .

De Wikipedia, la enciclopedia libre

  (Redirigido desde el problema de la ruta más corta euclidiana )

Saltar a navegaciónSaltar a búsqueda

Ejemplo de una ruta más corta en un espacio euclidiano tridimensional

El problema de la ruta más corta de Euclides es un problema en la geometría computacional : dado un conjunto de obstáculos poliédricosen un espacio euclidiano , y dos puntos, encuentran la ruta más corta entre los puntos que no se interseca con ninguno de los obstáculos.

En dos dimensiones, el problema se puede resolver en tiempo polinomialen un modelo de cálculo que permite la suma y comparación de números reales, a pesar de las dificultades teóricas que involucran la precisión numérica necesaria para realizar tales cálculos. Estos algoritmos se basan en dos principios diferentes, ya sea que ejecutan un algoritmo de ruta más corta como el algoritmo de Dijkstra en un gráfico de visibilidad derivado de los obstáculos o (en un enfoque llamado método Dijkstra continuo) propagando un frente de onda desde uno de los puntos hasta que se encuentre con el otro.

En tres (y mayores) dimensiones, el problema es NP-difícil en el caso general, ^[1] pero existen algoritmos de aproximación eficientes que se ejecutan en tiempo polinomial en base a la idea de encontrar una muestra adecuada de puntos en los bordes del obstáculo y realizar una Cálculo del gráfico de visibilidad utilizando estos puntos de muestra.

Hay muchos resultados en el cálculo de las rutas más cortas que permanecen en una superficie poliédrica. Dados dos puntos syt, por ejemplo, en la superficie de un poliedro convexo , el problema es calcular una ruta más corta que nunca abandona la superficie y conecta s con t. Esta es una generalización del problema de 2 dimensiones, pero es mucho más fácil que el problema de 3 dimensiones.

Además, hay variaciones de este problema, donde los obstáculos se ponderan , es decir, uno puede atravesar un obstáculo, pero conlleva un costo adicional para atravesar un obstáculo. El problema estándar es el caso especial donde los obstáculos tienen un peso infinito. Esto se denomina como el problema de la región ponderada en la literatura.