Muestreo eficiente de las rutas

14

Deje un grafo, y dejar que y sea dos vértices de . Podemos degustar una manera eficiente más corto - ruta uniformemente y de forma independiente al azar del conjunto de todos los caminos más cortos entre y ? Por simplicidad, podemos suponer que es simple, no dirigido y no ponderado.s t G s t s t GGstGststG

Incluso en muchos gráficos restringidos, el número de caminos más cortos entre y puede ser exponencial en el tamaño de . Por lo tanto, naturalmente nos gustaría evitar calcular en realidad todas las rutas - cortas. No sé sobre el caso general, pero me parece que podemos lograr esto para algunas clases especiales de gráficos.t G s tstGst

Esto se siente como algo que alguien debe haber considerado antes. ¿Existe alguna investigación sobre esto, o de hecho es simple de hacer incluso para gráficos generales?

Juho
fuente
Buena pregunta Juho. Al considerar una respuesta, ¿qué entiende exactamente al "muestrear una ruta st uniformemente al azar"? Si es suficiente para que syt se tomen al azar, la pregunta es trivial, así que supongo que quiere decir que todos los nodos en el camino más corto aparecen con una frecuencia (es decir, probabilidad) que sigue una distribución uniforme. ¿O hay alguna otra definición? En particular, para los gráficos bipartitos, su pregunta parece ser muy fácil, ¿no?
Carlos Linares López
1
@ CarlosLinaresLópez Considere decir el gráfico de diamantes , y digamos que s está en el lado derecho del "borde vertical", t está en el lado izquierdo. Ahora hay 2 caminos más cortos entre s y t . El algoritmo debe devolver con igual probabilidad cualquiera de estos dos caminos. Así que s y t no son "recogidos al azar", sino que se dan como entrada. ¿Eso lo deja claro? En este sentido, no estoy seguro de si el problema es realmente fácil para los gráficos bipartitos.
Juho
1
@ CarlosLinaresLópez En otras palabras, se nos da un gráfico G y dos vértices s,tV(G) . Deje S ser el conjunto de todos los caminos más cortos entre s y t . Salida de un elemento de S uniformemente al azar.
Juho

Respuestas:

6

No estoy 100% seguro de que esta respuesta sea correcta, pero aquí va:

Creo que puede reducir esto a cualquier ruta uniformemente aleatoria, desde , en un DAG con una sola fuente y un solo sumidero.st

Dado un gráfico G

  1. Hacer una nueva dígrafo vacío, .H
  2. Primero: ejecute la parte BFS de la ruta más corta de Dijkstra, comenzando desde , marque todos los nodos con su distancia más corta desde s .ss
  3. Sea la distancia mínima de s - v ; que conocemos por el paso BFS del algoritmo de ruta más corta de Dijkstra.d(s,v)sv
  4. Luego realice el siguiente paso del algoritmo de ruta más corta de Dijkstra, obtenga la ruta más corta y guárdela en (yendo hacia atrás de t a s ).pts
  5. Ahora comience el siguiente ciclo; expansión en comentarios y abajo:
    • q0={t}
    • Mientras q0
      • q1=
      • Para uq0
        • Por lo tanto, queremos encontrar todos los nodos siguientes posibles para este subtrayecto más corto desde tu
        • Para todo tal que d ( s , v ) < d ( s , u )edge(u,v)Gd(s,v)<d(s,u)
          • es un nodo vecino, con menos d ( s , ) (será 1 menos)vd(s,)1
          • Por lo tanto, es una posible ruta secundaria en una ruta más corta.tuv
          • Poner vH,di-edge(tu,v)H
          • Ahora tenemos que verificar los vecinos menores de el próximo turno.v
          • Poner vq1
      • Establezca a q 1 : q0 0q1
        • q0 0q1

Esencialmente, Estoy recogiendo todos los nodos posibles que se pueden utilizar en el camino más corto, y colocándolos en .H

Más sobre cómo funciona esto:

El algoritmo de ruta más corta de Dijkstra funciona ejecutando primero un BFS y marcando todos los nodos con sus rutas más cortas desde s - v . El siguiente paso es retroceder desde t - s , y seguir los nodos menos vecinos hacia atrás.vsols-vts

La cuestión es que aquí puede elegir cualquiera de los nodos menos vecinos. Lo que hago aquí es recopilar todos los nodos menos vecinos en cada paso, lo que significa que tengo en cuenta todas las rutas más cortas.

Ahora piensas rápidamente, pero oye, ¿por qué enumerarlos es exponencial, pero mi manera no?

La respuesta es que, como uso un conjunto para evitar agregar los mismos nodos dos veces, evito volver a calcular esto para cada ruta posible.

Ahora tenemos un DAG que podemos recorrer de cualquier manera desde , y obtenemos un camino inverso más corto desde s - t . El gráfico debe tener t como única fuente y s como el único sumidero.tsstts


Si lo anterior es correcto, entonces creo que podemos llevar esto un paso más allá y resolver el problema de la siguiente manera.

Dele a cada nodo en el DAG un peso de nodo; el peso del nodo será el número de rutas desde ese nodo a . Llamemos a esto w ( v ) .sw(v)

Puede calcular rápidamente éstos, véase algoritmo que encuentra el número de caminos simples de s a t en G .

Una vez que tenemos el peso del nodo, podemos elegir uniformemente una ruta de la siguiente manera:

  • Diseño del DAG como una estructura de nivel (para visualización)
  • En cada nivel, elija un orden arbitrario entre los nodos, es decir. una noción de "izquierda a derecha".
  • Recorriendo el DAG: en cada paso , i [ 1 , | p | ] (donde || significa tamaño de, en este caso, la longitud de la ruta más corta): ii[1,|p|]||
    • Vamos ser el nodo actual (a partir de t )uit
    • Sume todos los pesos de los hijos de , y usando un RNG, elija un nodo hijo, v i , de manera uniforme entre los hijos ponderados.uivi
    • Establezca , y vaya al siguiente pasoui+1=vi
Ensalada Realz
fuente
La estructura de nivel y la noción de izquierda a derecha fueron parte de mi intento inicial de generar simplemente y elegir un camino de esa manera, pero no lo descubrí, así que puedes ignorarlos con seguridad. r[0,w(t))
Realz
1
¡Esta respuesta se ve genial! ¡Amo las ideas! Traté de escribirlo de una manera ligeramente diferente (en mi respuesta), como prueba de mi comprensión. En cualquier caso, ¡solo quería compartir mi agradecimiento por esta encantadora respuesta!
DW
5

Aquí hay una solución basada en las ideas de la respuesta de Realz Slaw. Básicamente es una reexposición de sus ideas que podría ser más clara o más fácil de seguir. El plan es que procederemos en dos pasos:

  1. En primer lugar, vamos a construir un gráfico con la siguiente propiedad: cualquier camino de s a t en S es una ruta más corta de s a t en G , y cada camino más corto desde s a t en G también está presente en S . Por lo tanto, S contiene exactamente las rutas más cortas en G : todas las rutas más cortas y nada más. Como sucede, S será un DAG.SstSstGstGSSGS

  2. A continuación, vamos a probar de manera uniforme al azar de todos los caminos de a t en S .stS

Este enfoque generaliza a un gráfico dirigido arbitrario , siempre que todos los bordes tengan un peso positivo, por lo que explicaré mi algoritmo en esos términos. Deje w ( u , v ) denotar el peso en el borde u v . (Esto generaliza el enunciado del problema que dio. Si tiene un gráfico no ponderado, suponga que cada borde tiene peso 1. Si tiene un gráfico no dirigido, trate cada borde no dirigido ( u , v ) como los dos bordes dirigidos u v y v u .)Gw(u,v)uv(u,v)uvvu


Paso 1: extracto de . S Ejecute un algoritmo de rutas más cortas de una sola fuente (por ejemplo, el algoritmo de Dijkstra) en , comenzando desde la fuente s . Para cada vértice v en G , supongamos que d ( s , v ) denota la distancia de s a v .GsvGd(s,v)sv

Ahora defina el gráfico siguiente manera. Consiste en cada arista u v tal que (1) u v es una arista en G , y (2) d ( s , v ) = d ( s , u ) + w ( u , v ) .SuvuvGd(s,v)=d(s,u)+w(u,v)

El gráfico tiene algunas propiedades convenientes:S

  • Cada ruta más corta de a t en G existe como una ruta en S : una ruta más corta s = v 0 , v 1 , v 2 , , v k = t en G tiene la propiedad de que d ( s , v i + 1 ) = d ( s , v i ) + w ( v i , v istGSs=v0,v1,v2,,vk=tG, por lo que el borde v i v i + 1 está presente enS.d(s,vi+1)=d(s,vi)+w(vi,vi+1)vivi+1S

  • Cada camino en de s a t es un camino más corto en G . En particular, considere cualquier ruta en S de s a t , digamos s = v 0 , v 1 , v 2 , ... , v k = t . Su longitud viene dada por la suma de los pesos de sus bordes, a saber, k i = 1 w ( v i - 1 , v i )SstGSsts=v0,v1,v2,,vk=ti=1kw(vi1,vi), pero por la definición de , esta suma es k i = 1 ( d ( s , v i ) - d ( s , v i - 1 ) , que se telescopía a d ( s , t ) - d ( s , s ) = d ( s , t ) . por lo tanto, este camino es una ruta más corta desde s a t en GSi=1k(d(s,vi)d(s,vi1)d(s,t)d(s,s)=d(s,t)stG.

  • Finalmente, la ausencia de bordes de peso cero en implica que S es un dag.GS

Paso 2: muestra una ruta aleatoria. Ahora podemos tirar a la basura los pesos en los bordes en , y muestra un camino al azar de s a t en S .SstS

Para ayudar con esto, haremos una precomputación para calcular para cada vértice v en S , donde n ( v ) cuenta el número de rutas distintas de v a t . Esta precomputación se puede hacer en tiempo lineal escaneando los vértices de S en orden topológico, utilizando la siguiente relación de recurrencia:n(v)vSn(v)vtS

n(v)=wsucc(v)n(w)

donde denota los sucesores de v , es decir, succ ( v ) = { w : v w  es una ventaja en  S } , y donde tenemos el caso base n ( t ) = 1 .succ(v)vsucc(v)={w:vw is an edge in S}n(t)=1

A continuación, usamos la anotación para muestrear una ruta aleatoria. Primero visitamos el nodo s . Luego, elegimos aleatoriamente uno de los sucesores de s , con el sucesor w ponderado por n ( w ) . En otras palabras:n()sswn(w)

choosesuccessor(v):
    n = 0
    for each w in succ(w):
        n = n + n(w)
    r = a random integer between 0 and n-1
    n = 0
    for each w in succ(w):
        n = n + n(w)
        if r < n:
            return w

Para elegir una ruta aleatoria, repetidamente repetimos este proceso: es decir, , y v i + 1 = ( v i ) . La ruta resultante es la ruta deseada, y se muestreará de manera uniforme al azar de todas las rutas más cortas de s a t .v0=svi+1= choosesuccessor(vi)st

Esperemos que esto le ayude a comprender la solución de Realz Slaw más fácilmente. ¡Todo el crédito a Realz Slaw por la solución hermosa y limpia de este problema!


El único caso que esto no maneja es el caso en que algunos bordes tienen peso 0 o peso negativo. Sin embargo, el problema no está bien definido en ese caso, ya que puede tener infinitas rutas más cortas.

DW
fuente
Me alegra que te hayas tomado el tiempo para obtener mi respuesta completa No estaba seguro de que sea correcto. Ahora estoy reivindicado: D.
Realz Slaw