Encontrar el camino con el peso máximo mínimo
https://stackoverflow.com/questions/873126
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Estoy tratando de llegar a un algoritmo para encontrar un camino a través de un grafo dirigido. No es un camino convencional y no puedo encontrar ninguna referencia a algo como esto ser hecho ya.
Quiero encontrar el camino que tiene el peso mínimo máximo.
es decir. Si hay dos caminos con pesos 10-> 1-> 10 y 2-> 2-> 2 a continuación, la segunda trayectoria se considera mejor que el primero debido a que el peso mínimo (2) es mayor que el peso mínimo de la primera (1 ).
Si alguien puede encontrar una forma de hacer esto, o simplemente me punto en la dirección de algún material de referencia que sería increíblemente útil:)
EDITAR :: Parece que me olvidé de mencionar que estoy tratando de conseguir desde un vértice específica a otro vértice específico. Muy punto importante que hay: /
Edit2 :: Como alguien ha señalado a continuación, debo destacar que pesos de las aristas son no negativos.
Solución
Utilice de Prim o algoritmo / wiki de Kruskal. Sólo modificarlos para que se detienen cuando se enteran de que los vértices de preguntar acerca están conectados.
EDIT: Usted pide máxima mínimo, pero su ejemplo se ve como desea la máxima mínimo. En caso de máximo y mínimo algoritmo de Kruskal no funcionará.
EDIT: El ejemplo está bien, mi error. Sólo algoritmo de Prim trabajará a continuación.
Otros consejos
esta respuesta y añadiendo, además de darle mi prueba de la corrección para el algoritmo:
Me gustaría utilizar alguna variante de de Dijkstra. Tomé el pseudo código abajo directamente de Wikipedia y sólo cambiaron 5 cosas pequeñas:
- Renamed
distawidth(de la línea 3 en) - iniciada cada
-infinityainfinity(línea 3) - inicializar la anchura de la fuente a
(s, a) = 300(línea 8) - Establecer el criterio final para
b(línea 14) - Modificado la función de actualización y el signo (línea 20 + 21)
1 function Dijkstra(Graph, source):
2 for each vertex v in Graph: // Initializations
3 width[v] := -infinity ; // Unknown width function from
4 // source to v
5 previous[v] := undefined ; // Previous node in optimal path
6 end for // from source
7
8 width[source] := infinity ; // Width from source to source
9 Q := the set of all nodes in Graph ; // All nodes in the graph are
10 // unoptimized – thus are in Q
11 while Q is not empty: // The main loop
12 u := vertex in Q with largest width in width[] ; // Source node in first case
13 remove u from Q ;
14 if width[u] = -infinity:
15 break ; // all remaining vertices are
16 end if // inaccessible from source
17
18 for each neighbor v of u: // where v has not yet been
19 // removed from Q.
20 alt := max(width[v], min(width[u], width_between(u, v))) ;
21 if alt > width[v]: // Relax (u,v,a)
22 width[v] := alt ;
23 previous[v] := u ;
24 decrease-key v in Q; // Reorder v in the Queue
25 end if
26 end for
27 end while
28 return width;
29 endfunction
Algunos (handwaving) explicación de por qué esto funciona: se inicia con la fuente. A partir de ahí, se tiene capacidad infinita de sí mismo. Ahora se comprueba que todos los vecinos de la fuente. Suponga que los bordes no todos tienen la misma capacidad (en su ejemplo, dicen (s, b)). Entonces, no hay mejor manera de llegar <=> continuación, a través de <=>, por lo que sabe la mejor capacidad de caso de <=>. Se continúa yendo a los mejores vecinos del conjunto conocido de vértices, hasta que llegue a todos los vértices.
prueba de la corrección del algoritmo:
En cualquier punto en el algoritmo, habrá 2 conjuntos de vértices A y B . Los vértices en A serán los vértices a que se ha encontrado el camino capacidad mínima máxima correcta. Y el conjunto B tiene vértices a los que no hemos encontrado la respuesta.
inductivo Hipótesis : en cualquier paso, todos los vértices en el conjunto A tienen los valores correctos de camino máximo de capacidad mínima a ellos. es decir., todas las iteraciones anteriores son correctas.
Corrección de caso base : Cuando el conjunto A tiene el vértice S solamente. Entonces, el valor de S es infinito, lo que es correcto.
En iteración actual, nos propusimos
val [W] = max (val [W], min (val [V], width_between (V-W)))
paso inductivo : Supongamos, W es el vértice en el conjunto B con la mayor val [W]. Y W se quita de la cola de la cola y W se ha establecido la respuesta val [W].
Ahora, necesitamos para mostrar que cada otra trayectoria de S-W tiene una anchura <= val [W]. Esto será siempre cierto porque todas las demás formas de llegar a W irán a través de algún otro vértice (llámese X) en el conjunto B.
Y para todos los otros vértices X en conjunto B, val [X] <= val [W]
Así cualquier otra ruta de acceso a W se verá limitado por val [X], que nunca es mayor que val [W].
Así, la estimación actual de val [W] es óptima y, por tanto algoritmo calcula los valores correctos para todos los vértices.
También puede utilizar la "búsqueda binaria sobre la respuesta" paradigma. Es decir, hacer una búsqueda binaria en los pesos, las pruebas de cada peso w si se puede encontrar un camino en el gráfico utilizando sólo los bordes de peso mayor que O(|E|*log(max W)).
El O(|E|log |V|) grande para el que se puede (que se encuentra a través de la búsqueda binaria) da la respuesta. Tenga en cuenta que sólo se necesita comprobar si existe un camino, por lo que sólo un O (| E |) en anchura / profundidad-primera búsqueda, no una ruta más corta. Así que es <=> en total, comparable a la de Dijkstra / Kruskal / Prim de <=> (y no puedo ver inmediatamente una prueba de esos, también).
Esto se puede solucionar utilizando un algoritmo BFS estilo, sin embargo es necesario dos variaciones:
- En lugar de marcar cada nodo como "visitado", lo marca con el peso mínimo a lo largo del camino que tomó para llegar a él.
Por ejemplo, si I y J son vecinos, I tiene un valor w1, y el peso del borde entre ellos es w2, entonces J = min (w1, w2).
- Si se llega a un nodo marcado con el valor W1, es posible que necesite observación y procesarlo de nuevo, si la asignación de un nuevo valor de W2 (y w2> W1). Esto es necesario para asegurarse de obtener el máximo de todos los mínimos.
Por ejemplo, si I y J son vecinos, I tiene un valor w1, J tiene valor w2, y el peso del borde entre ellos es w3, entonces si min (w2, w3)> w1 debe remarcar J y el proceso de todos lo que es vecinos de nuevo.
No estoy seguro de que Prim funcionará aquí. Tome este contraejemplo:
V = {1, 2, 3, 4}
E = {(1, 2), (2, 3), (1, 4), (4, 2)}
weight function w:
w((1,2)) = .1,
w((2,3)) = .3
w((1,4)) = .2
w((4,2)) = .25
Si se aplica Prim para encontrar el camino maxmin de 1 a 3, a partir del 1 seleccionará el 1 --> 2 --> 3 ruta, mientras que la distancia maxmin se alcanza por el camino que pasa por 4.
Ok, respondiendo a mi propia pregunta aquí sólo para tratar de conseguir un poco de retroalimentación que tenía en la solución tentativa trabajé a cabo antes de publicar aquí:
Cada nodo almacena un "fragmento camino", esto es todo el camino a sí misma hasta el momento.
0) conjunto de vértices actual a partir del vértice
1) Generar todos los fragmentos de trayectoria de este vértice y añadirlos a una cola de prioridad
2) Tomar el fragmento de la parte superior de la cola de prioridad, y establecer el vértice actual al vértice final de ese camino
3) Si el vértice actual es el vértice de destino, a continuación, devolver la ruta
4) Goto 1
No estoy seguro de que esto va a encontrar el mejor camino, sin embargo, creo que la condición de salida en el paso tres es un poco ambicioso. No puedo pensar en una mejor condición de salida, sin embargo, ya que este algoritmo no vértices cercanos (un vértice se puede hacer referencia en tantos fragmentos de trayectoria, ya que le gusta) no se puede simplemente esperar hasta que todos los vértices están cerradas (como Dijkstra para ejemplo)
Puede seguir utilizando de Dijkstra!
En lugar de utilizar +, utilice el operador min ().
Además, tendrá que orientar el montón / priority_queue de manera que las cosas más grandes son en la parte superior.
Algo como esto debería funcionar: (i probablemente he perdido algunos detalles de implementación)
let pq = priority queue of <node, minimum edge>, sorted by min. edge descending
push (start, infinity) on queue
mark start as visited
while !queue.empty:
current = pq.top()
pq.pop()
for all neighbors of current.node:
if neighbor has not been visited
pq.decrease_key(neighbor, min(current.weight, edge.weight))
Se garantiza que cada vez que se llega a un nodo ha seguido un camino óptimo (ya que se encuentran todas las posibilidades en orden decreciente, y nunca se puede mejorar su ruta mediante la adición de un borde)
Los límites de tiempo son los mismos que de Dijkstra -. O (Vlog (E))
EDIT: ah, espera, esto es básicamente lo que usted envió. LOL.
