Entiendo lo que es Dijkstra's algorithm, pero no entiendo por qué funciona.¿Por qué funciona el algoritmo de Dijkstra?
Al seleccionar el siguiente vértice para examinar, ¿por qué el algoritmo de Dijkstra selecciona el que tiene el menor peso? ¿Por qué no simplemente seleccionar un vértice arbitrariamente, ya que el algoritmo visita todos los vértices de todos modos?
Se puede pensar en el algoritmo de Djikstra como un algoritmo de llenado de agua (es decir, una búsqueda en amplitud podado). En cada etapa, el objetivo es cubrir más de todo el gráfico con el camino de menor costo posible. Suponga que tiene vértices en el borde del área que ha rellenado, y hacer una lista de ellos en términos de distancia:
v0 <= v1 <= v2 <= v3 ...
vez podría haber una manera más barata para llegar al vértice v1? Si es así, la ruta debe pasar por v0, ya que ningún vértice no probado podría estar más cerca. Por lo tanto, examine el vértice v0 para ver a dónde puede llegar, verificando si cualquier ruta a través de v0 es más barata (a cualquier otro vértice a un paso).
Si elimina el problema de esta manera, tiene la garantía de que sus distancias son mínimas, ya que siempre verifica exactamente ese vértice que podría conducir al camino más corto. O encuentras el camino más corto, o lo descartas, y pasas al siguiente vértice. Por lo tanto, tiene la garantía de consumir un vértice por paso.
Y se detiene sin hacer más trabajo del necesario, porque se detiene cuando su vértice de destino ocupa la ranura "I'm smallest" v0.
Veamos un breve ejemplo. Supongamos que estamos tratando de obtener de 1 a 12 por multiplicación, y el costo entre nodos es el número que tiene que multiplicar por. (Vamos a restringir los vértices a los números del 1 a 12.)
Empezamos con 1, y podemos llegar a cualquier otro nodo multiplicando por ese valor. Así que el nodo 2 ha costado 2, 3 ha costado 3, ... 12 ha costado 12 si va en un solo paso.
Ahora, un camino a través 2 podría (sin necesidad de conocer la estructura) llegar a 12 más rápido si existía una relación libre de 2 a 12. No lo hay, pero si lo hubiera, sería más rápido. Entonces, verificamos 2. Y encontramos que podemos obtener 4 por costo 2, 6 por 3, y así sucesivamente.Tenemos así una tabla de costos, así:
3 4 5 6 7 8 9 10 11 12 // Vertex
3 4 5 5 7 6 9 7 11 8 // Best cost to get there so far.
bien, ahora tal vez podamos llegar a 12 de 3 gratis! Mejor control. Y nos encontramos con que 3*2==6 por lo que el costo de 6 es el costo de 3 más 2, y para 9 es más 3, y 12 es más 4.
4 5 6 7 8 9 10 11 12
4 5 5 7 6 6 7 11 7
Bastante bien. Ahora probamos 4, y vemos que podemos obtener 8 para un 2 adicional, y 12 para un 3 extra. Una vez más, el costo para llegar a 12 es, pues, no más de 4 + 3 = 7:
5 6 7 8 9 10 11 12
5 5 7 6 8 7 11 7
Ahora tratamos 5 y 6 --no mejoras hasta ahora. Esto nos deja con
7 8 9 10 11 12
7 6 8 7 11 7
Ahora, por primera vez, vemos que el costo de llegar a 8 es menos que el costo de llegar a 7, por lo que será mejor comprobar que no hay alguna forma gratuita de llegar al 12 desde 8. No hay, no hay forma de llegar allí con números enteros, así que lo tiramos.
7 9 10 11 12
7 8 7 11 7
Y ahora vemos que 12 es tan barato como cualquier camino de la izquierda, por lo que el coste para llegar a 12 debe ser 7. Si hubiésemos rastreado la ruta más barata hasta el momento (solo reemplazando la ruta cuando es estrictamente mejor), encontraríamos que 3*4 es la primera forma más económica de llegar a 12.
¡Lo entiendo ahora! Ok, ahora me doy cuenta de que esto es lo que todas las respuestas intentaban decirme, pero esta es la explicación más clara y la que causó la caída del centavo. ¡Gracias! – BeeBand
Por cierto, ¿no es el mejor costo para 12 de 3, que sea 7? (3 * 4 = 12, pero aún tiene el mejor costo indicado como 8 ...) – BeeBand
@Bee: Me alegro de que haya ayudado. Pero sí dije que el mejor costo es 7 para llegar a 12 (fue 8 en el camino, pero cambia a 7 cuando probamos 4). –
El algoritmo de Dijkstra selecciona el vértice con el menor costo de ruta hasta ahora, porque una ruta a través de cualquier otro vértice es al menos tan costosa como una ruta a través del vértice con el menor costo de ruta.
Visitar cualquier otro vértice, por lo tanto, si es más costoso (lo cual es bastante posible) necesitaría visitar no solo ese otro vértice, sino también el que menos costo tiene hasta ahora, por lo que tendría que visitar más vértices antes de encontrar el camino más corto. De hecho, terminarías con el Bellman-Ford algorithm si lo hicieras.
También debo agregar que el vértice no tiene un peso, es el borde que tiene un peso. La clave para un vértice dado es el costo de la ruta más corta encontrada hasta ahora para ese vértice desde el vértice fuente.
Todavía no lo entiendo. Cuando dices "una ruta a través de cualquier otro vértice es al menos tan costosa", ¿cómo estás definiendo la ruta, la ruta entre dos vértices u y v? O el camino entre 3 vértices
@BeeBand - dibuja y juega con él a mano. Te encontrarás con ese momento "Tada" más rápido. – Donnie
@Donnie - ok, buena idea. Estoy trabajando en este momento, pero puedo hacer que parezca que estoy trabajando. – BeeBand
Le gusta la estrategia codiciosa.Mi inglés no es bueno.Traduce por google.Si no entiende, lo siento mucho.
Algoritmo de Dijkstra, una G de S a todos los vértices de la longitud del camino más corto. Suponemos que a cada vértice de G en V se le ha dado una bandera L (V), o es un número, ya sea ∞. Supongamos que P es el conjunto de vértices de G, P contiene S, para satisfacer:
A) Si V es P, entonces L (V) desde VS a la longitud de la ruta más corta, y la existencia de tal V de S a la ruta más corta: ruta en los vértices en P en
B) Si V no pertenece a P, entonces L (V) de S a V cumple las siguientes restricciones sobre la longitud de la ruta más corta: V es la única ruta P no pertenece al vértice.
Podemos utilizar la inducción para demostrar algoritmo P Dijkstra en línea con la definición anterior de la colección:
1) Cuando el número de elementos de P = 1, P corresponde a la primera etapa en el algoritmo, P = (S), está claramente satisfecho.
2) P Supongamos que es k, el número de elementos, P satisface la definición anterior, véase el algoritmo por debajo de la tercera etapa
3) P en y la primera para averiguar no está marcado con el vértice mínimo U, marcado como L (U), se puede probar de S a U de U fuera del camino más corto, además de que P no contiene los elementos que no pertenecen.
Porque si hay fuera de los otros vértices excepto U, entonces el camino más corto a S, P1, P2 ... Pn, Q1, Q2 ... Qn, U (P1, P2 ... Pn es P; Q1, Q2, ... Qn no pertenece a P), de la naturaleza de B) la longitud de camino más corta L (Q1) + RUTA (Q1, U)> L (U).
Que es mayor que S, P1, P2 ... Pn, U de la longitud del canal L (U), no es la ruta más corta. Por lo tanto, desde el S hasta la U de U fuera del camino más corto, además de que P no contiene los elementos, no pertenece a U desde S hasta la longitud del camino más corto desde donde se da L (U).
U se agrega a P en la forma P ', claramente P' para cumplir con la naturaleza de A).
Take V no pertenece a P ', obviamente no pertenece a VP, luego de S a V excepto el camino más corto y cumple todos los vértices fuera de V en P' en el camino hay dos posibilidades, i) contiene U, ii) no contiene U.
En i) S, P1, P2 ... Pn, U, V = L (U) + W (U, V)
ii) S, P1 , P2 ... Pn, V = L (V)
Obviamente, los dos se dan en la V más pequeña de S para cumplir con el acceso mínimo y la adición externa a todos los vértices son de longitud VP '.
El tercer paso para el algoritmo dado en P 'con k +1 elementos y cumple con A), B).
Por la proposición de inducción puede permitir.
Aquí está the source.
Gracias por la respuesta, lo siento, pero no entiendo lo que quiere decir con "Algoritmo de Dijkstra, una G de S a todos los vértices de la longitud de ruta más corta". Leí más, pero aún no llenó ese espacio en blanco. ¿Algo se perdió en la traducción allí tal vez? – BeeBand
La razón por la cual el algoritmo de Dijsktra funciona de la manera que lo hace es en parte porque explota el hecho de que el camino más corto entre el nodo u y w que incluye el punto v también contiene la ruta más corta desde u a v y desde v a w. Si existiera algo más corto entre tú y v, entonces no sería el camino más corto.
Para entender realmente por qué funciona el algoritmo de Dijkstra, consulte los conceptos básicos de dynamic programming, suena difícil pero es muy fácil de entender los principios.
gracias, ahora entiendo completamente lo que me está diciendo aquí. La ruta más corta desde u hasta w vía v debe garantizar que también incluya la ruta más corta desde u hasta v. Realmente no sé por qué estaba teniendo ese problema antes :-) – BeeBand
No hay problema - es una de esas áreas de superposición significativa entre la comunidad CS y OR. Simplemente enseñar el "qué" no da necesariamente la idea para saber el "cómo" y el "por qué". – Grembo
Comprueba la ruta con el peso más bajo primero porque es muy probable (sin información adicional) reducir el número de rutas marcadas. Por ejemplo:
a->b->c cost is 20 a->b->d cost is 10 a->b->d->e cost is 12
Si la meta es llegar desde A a E, que no necesita ni siquiera comprobar el coste de:
a->b->c->e
Porque sabemos que es al menos 20 por lo que sabemos que es no es óptimo porque ya hay otra ruta con un costo de 12. Puede maximizar este efecto comprobando primero los pesos más bajos. Esto es similar (¿lo mismo?) A cómo funciona minimax en el ajedrez y otros juegos para reducir el factor de ramificación del árbol de juego.
El algoritmo de Dijsktra es un algoritmo codicioso que sigue la resolución de problemas heurísticos de hacer la elección localmente óptima en cada etapa con la esperanza de encontrar un óptimo global.
@APC - Gracias por el enlace. Según esa entrada de la wiki, elegir el vértice más pequeño hace que Dijkstra sea "codicioso". Supongo que ahora necesito buscar los beneficios de un algoritmo codicioso. – BeeBand
@BeeBand, el término "codicioso" simplemente significa que es la mejor opción en el momento actual. La codicia tiende a ser bastante intuitiva y simple de implementar, pero no siempre es óptima (en este caso, sí lo es). –
Prueba el libro de Cormen para obtener una mejor explicación sobre "por qué" el algoritmo codicioso es adecuado ... –