Sea un gráfico no ponderado no dirigido con vértices aristas. ¿Es posible preprocesar y producir una estructura de datos de tamaño para que pueda responder consultas de la forma "distancia entren m G m ⋅ p o l y l o g ( n ) u v y " en el tiempo O (n)?
El problema parece demasiado básico para no resolverse.
Respuestas:
Esta es una pregunta muy interesante. En un nivel alto, se pregunta si se puede preprocesar un gráfico de manera que las consultas de ruta más corta se vuelvan independientes de la densidad del gráfico, sin utilizar mucho espacio adicional, interesante, pero como usted dice, sin resolver.
Si está satisfecho con las distancias aproximadas, aquí hay una manera de obtener una aproximación de2 . Sea sol un gráfico ponderado no dirigido con norte nodos metro aristas. En el siguiente documento se muestra que para consultas de distancia aproximada, diseñar estructuras de datos para gráficos con metro bordes no es más difícil que los gráficos en los que cada nodo tiene un grado limitado por m / n :
R. Agarwal, PB Godfrey, S. Har-Peled, consultas de distancia aproximada y enrutamiento compacto en gráficos dispersos, INFOCOM 2011
Entonces, suponga que es un gráfico acotado de m / n grados. Muestra α = O ( m / n ) nodos uniformes al azar; llame a estos nodos emblemáticos. Durante la fase de preprocesamiento, almacene la distancia desde cada nodo de referencia a cada nodo en el gráfico; esto requiere O ( m ) de espacio. Para cada nodo u , almacene su nodo de referencia más cercano ℓ ( u ) . Además, almacene el gráfico dentro de la estructura de datos, digamos como una lista de adyacencia.sol m / n α = O ( m / n ) O(m) u ℓ(u)
Cuando se le pregunta por la distancia entre y v , crecen bolas alrededor de ambos nodos: la bola del nodo w se define como el conjunto de nodos que están estrictamente más cerca de w que a su nodo de referencia más cercano, digamos ℓ ( w ) . Se puede demostrar que el tamaño de cada bola es O ( n 2 / m ) , en expectativa. Sea Γ ( u ) = B ( u ) ∪ N ( B ( u ) ) , donde B (u v w w ℓ(w) O(n2/m) Γ(u)=B(u)∪N(B(u)) , en expectativa.B(u) es la bola del nodo y N ( B ( u ) ) es el conjunto de vecinos de nodos en B ( u ) . Se puede demostrar que el tamaño de Γ ( u ) es O ( n )u N(B(u)) B(u) Γ(u) O(n)
Respondiendo a la consulta: si , devuelve min x ∈ Γ ( u ) ∩ Γ ( v ) { d ( u , x ) + d ( v , x ) } ; de lo contrario, si , devuelve ; de lo contrario, devuelve -aproximación.Γ(u)∩Γ(v)≠∅ minx∈Γ(u)∩Γ(v){d(u,x)+d(v,x)} d ( u , ℓ ( u ) ) + d ( ℓ ( u ) , v ) d ( v , ℓ ( v ) ) + d ( ℓ ( v ) , u ) 2d(u,ℓ(u))≤d(v,ℓ(v)) d(u,ℓ(u))+d(ℓ(u),v) d(v,ℓ(v))+d(ℓ(v),u) . Es fácil demostrar que este es un2
En términos de tiempo de consulta, tenga en cuenta que las bolas en crecimiento requieren un tiempo para un gráfico acotado de grados; construir y dadas las bolas respectivas toma tiempo (ya que los vecinos se almacenan dentro de la estructura de datos); y comprobar si está vacío o no, también lleva tiempo .m / n Γ ( u ) Γ ( v ) O ( n ) Γ ( u ) ∩ Γ ( v ) O ( n )O(n) m/n Γ(u) Γ(v) O(n) Γ(u)∩Γ(v) O(n)
Los límites anteriores están en expectativa; Creo que es fácil desrandomizar la construcción. Desafortunadamente, esta técnica no parece permitir obtener una aproximación mejor que . Sin embargo, es una pregunta muy interesante ...2
fuente
Lo que necesita se llama "oráculo de distancia". Desafortunadamente, no estoy muy familiarizado con los oráculos a distancia, por lo que solo puedo remitirlo al documento seminal debido a Thorup y Zwick:
Mikkel Thorup y Uri Zwick. Distancia aproximada de oráculos. STOC '01, 2001.
Aquí hay un extracto del resumen:
Sea un gráfico ponderado no dirigido con | V | = N y | E | = m . Deje k ser un número entero. Mostramos que G = ( V , E ) puede preprocesarse en O ( k m n 1 / k ) tiempo esperado, construyendo una estructura de datos de tamaño O ( k n 1 + 1 / kG=(V,E) |V|=n |E|=m k G=(V,E) O(kmn1/k) , de modo que cualquier consulta de distancia posterior se pueda responder, aproximadamente, en tiempo O ( k ) . La distancia aproximada devuelta es de estiramiento como máximo 2 k - 1 , es decir, el cociente obtenido al dividir la distancia estimada por la distancia real se encuentra entre 1 y 2 k - 1 . [...] El requisito de espacio de nuestro algoritmo es [...] esencialmente óptimo.O(kn1+1/k) O(k) 2k−1 2k−1
Según sus resultados, lo que solicita es básicamente factible incluso para gráficos ponderados: elegir produce un oráculo de distancia de tamaño O ( n 2 ) obtenido en el tiempo esperado O ( m n ) , que puede responder a sus consultas de ruta más corta con 1 -estiramiento en O ( 1 ) tiempo!k=1 O(n2) O(mn) 1 O(1)
Distancia oráculos es un campo muy bien investigado, por lo que podrá cavar más, creo.
fuente