graph-theory - introductory - graph theory harary

Teoría de gráficos: ¿Cómo encontrar nodos accesibles desde un nodo determinado dentro de un costo determinado? (6)

He estado buscando "accesibilidad" o "accesibilidad" pero estas parecen ser palabras clave equivocadas.

Sí, tiene usted razón. Estas son las palabras clave equivocadas.

Primero, permítame redefinir el problema de manera más precisa. Dado un gráfico G (V, E) , un nodo s y una constante c , queremos encontrar el conjunto R = {(n, d) | la distancia entre s y n es d <= c} .

Este problema es una versión generalizada del problema de accesibilidad en el que c es infinito y es mucho más difícil si se consideran gráficos grandes.

Ahora, como parte de la precomputación, para encontrar el conjunto R , tendrá que determinar la longitud del camino más corto entre sy todos los demás nodos. Este es el problema de la ruta más corta de todos los pares (APSP) disfrazado.

Por lo tanto, el primer paso, la precomputación, es buscar en las bibliotecas de investigación un algoritmo APSP realmente rápido que se adapte al tipo de gráficos que está tratando. El algoritmo y su implementación determinan el tiempo de ejecución de la precomputación.

El segundo paso es encontrar una manera de almacenar lo más posible a partir de los resultados del algoritmo y de la manera más eficiente posible porque las estructuras de datos y los algoritmos que elija aquí determinarán el tiempo de ejecución de la consulta. Teniendo en cuenta un billón de vértices, el número de rutas más cortas calculadas por el algoritmo sería alrededor de 10 ^ 18 (de, a, distancia) tripletes. Si el tamaño de cada valor es de 4 bytes, necesitará alrededor de 7 exabytes si almacenamos todos estos datos en una tabla hash distribuida (que requiere almacenamiento adicional). En este caso, podemos lograr un tiempo de consulta de como máximo unos pocos milisegundos.

De lo contrario, si no puede almacenar todos estos datos, tendrá que comprimir los datos y / o descartarlos. Ese es un problema diferente ahora. Es posible que desee dividir el gráfico en muchos subgrafos de pequeño diámetro (el diámetro debe determinarse experimentalmente) y luego almacenar la información de la ruta más corta solo para los nodos en los centros de los subgrafos y en el momento de la consulta, tendrá que volver a ejecutar una muy eficiente Implementación de SSSP (ruta más corta de una sola fuente). Hay muchas otras técnicas de optimización que pueden abarcar fácilmente un libro. Hagas lo que hagas, lograr un tiempo de consulta de <200 ms es muy difícil.

Los resultados de la consulta de caché en DRAM y discos locales es una gran idea. Esto puede ayudar mucho si un gran porcentaje de las consultas son iguales.

En cuanto al número de usuarios, dado que el gráfico es estático, puede paralelizar todas las consultas. Puede aprovechar las CPU y GPU altamente paralelas. > 10000 consultas en paralelo no es trivial, pero puede aprovechar las consultas que están cerca en el gráfico y posiblemente fusionar varias consultas ligeramente diferentes en una y luego filtrar los resultados.

Finalmente, el código que escribe para procesar las consultas puede optimizarse. Una comprensión profunda de las optimizaciones del compilador y la arquitectura de la computadora puede ayudar a reducir sustancialmente el tiempo de consulta.

Estoy considerando el siguiente problema (descripción muy aproximada):

Supongamos que tenemos un gráfico en el que a los bordes se les asignan algunos costos no negativos, un nodo de inicio s y una constante de costo C Descubrir:

Un conjunto de nodos N , accesible desde s donde el costo de la ruta más corta desde el nodo de inicio s a cualquier nodo en N no es mayor que C
Para cada e en el conjunto de lo anterior - el costo de la ruta más corta.

Básicamente Dijkstra con la restricción de costos.

Mi pregunta principal es: ¿cuál es la terminología correcta en la teoría de grafos para este problema?

He estado buscando "accesibilidad" o "reachability" pero estas parecen ser las palabras clave equivocadas.

En última instancia, estoy buscando un algoritmo que pueda responder eficientemente muchas de estas consultas en un gráfico (no modificable) pero bastante grande (potencialmente ~ 100 millones de bordes) en paralelo. Me gustaría consultar la literatura, pero necesito sugerencias sobre las palabras clave adecuadas.

Actualización: Mi problema práctico es el siguiente.

Supongamos que nos dan una red de carreteras de tamaño continental (modelada como un gráfico dirigido, con algunas propiedades en los bordes y nodos como si fuera una vía peatonal o una carretera). Costo de borde es el tiempo de viaje.

Me gustaría responder a las preguntas de los usuarios como: a partir de una posición dada (nodo del gráfico), ¿a qué nodos se puede acceder en 1 hora?

También me gustaría responder estas consultas muy rápido (<200-300ms, si es posible) para muchos usuarios (> 10000, si es posible) en paralelo.

Creo que debería haber al menos dos optimizaciones posibles:

Algunas precomputaciones de tamaño razonable, por ejemplo matrices de distancia precalculadas para nodos "centrales" seleccionados.
Si las búsquedas se realizan en paralelo, pueden beneficiarse de los "resultados temporales" de cada uno.

Tengo algunas ideas por mi cuenta, pero primero me gustaría revisar la literatura para evitar reinventar la rueda.

Cuando estaba trabajando con esto, solíamos llamar a Dijkstra con un valor de corte, donde el valor de corte es el costo máximo en el que estamos interesados.

Por ejemplo, como se utiliza aquí algoritmos arcgis .

Esos algoritmos funcionarán. El primero será rápido para entornos blandos, donde el costo de ir de un lugar a otro es bastante alto. El segundo es menos susceptible.

Dejemos que G sea un gráfico dirigido, v un nodo, desde donde comenzamos, el costo de C se dejó.

//in case, there is no cycle of cost 0, but in metrical environment there won''t be one GLOBAL SET result = {}; def AchievableNodes(G,v,C): for each w: e = (v,w) in Edges: if c(e) < C: result.addIfNotInResult(w) AchievableNodes(G, w, C-c(e)) AchievableNodes(G, root, C) print(result) GLOBAL ARRAY result[|V|] - initialized with 0s. def AchievableNodes(G, v, C): for each w: e = (v,w) in Edges: if c(e) < C: if result[w] > result[v] + c(e): result[w] = result[v] + c(e) AchievableNodes(G, w, C-c(e)) AchievableNodes(G, v, C) print(result)

En realidad, recomiendo encarecidamente almacenar el resultado en algún lugar. Entonces puedes mejorarlo asintóticamente hasta tiempo constante.

La terminología correcta del problema con el que está tratando se encuentra en la familia de "algoritmos de ruta más corta". Los problemas de accesibilidad (es decir, Warshal) tratan con la pregunta "¿hay un camino entre los nodos A y B?" y tiene una respuesta binaria, no necesita pesos en este caso, solo busca bordes. Pero en su caso, debe tener en cuenta el tiempo que lleva viajar del nodo A al nodo B en cada caso.

Ahora, no hay un ajuste "exacto" para estos problemas porque se puede usar un pequeño cambio en Dijktra''s, Floyd''s, BFS o DFS para resolver este problema, pero tiene una complejidad adicional debido al tamaño del gráfico que es importante entender. Cómo construir tu solución. El algoritmo que utilice dependerá de su combinación específica de restricciones de tiempo y hardware disponible que tenga.

Hay 2 soluciones algorítmicas para su problema (supongo que ya tiene todos los bordes almacenados en algún lugar y que puede consultar esta base de datos de alguna manera):

En un mundo ideal (imaginario), ejecutaría un algoritmo de Floyd, guardaría la matriz resultante en algo así como Redis y ya está, puede atender sus solicitudes en menos de 10 ms, si la cantidad de clientes aumenta, puede agregar más servidores redis como es necesario ya que no es probable que la gráfica cambie muy a menudo (porque en su problema específico tiene información sobre la carretera). El problema con esto es la complejidad del espacio de la solución, lo mejor de todo es que todo está precomputado, lo que significa que el tiempo de respuesta a las solicitudes es mínimo. Para poder implementar alguna variación de esto, necesita mucho espacio, incluso un clúster redis con una base de datos almacenada en el disco (sí disco, no memoria) y todos los servidores con SSD deberían ser suficientes, esta opción se adapta bien cuando el número Los clientes concurrentes crecen y la respuesta en el tiempo es bastante rápida. Pero el tiempo o no puede usar esta solución depende de la cantidad de nodos en su gráfica: aunque necesita calcular previamente las distancias usando cada borde, solo necesita espacio para almacenar una matriz de NxN siendo N la cantidad de nodos en su gráfica. si esta matriz encaja en redis, entonces puede usar este algoritmo y calcular de antemano todas las "distancias" (en su caso, esta es la suma de los costos, también conocida como "tiempos de viaje") entre todos los nodos. Más adelante, cuando reciba una solicitud, necesita consultar la matriz resultante para obtener todos los nodos con un tiempo de viaje menor que un valor dado, hay una optimización adicional al almacenar esta matriz en redis que puede permitirle obtener los números de nodo bastante rápido utilizando conjuntos ordenados.
Luego tienes la segunda solución que es modificar Dijktra, BFS o DFS para eliminar la búsqueda según el costo y eso es todo. En este escenario, ya ha descartado a Floyd debido a la gran complejidad del espacio, lo que significa que su gráfica es bastante grande tanto en nodos como en bordes. En este caso, la solución es casi la misma usando una variación de cualquiera de los algoritmos, lo que hace que la diferencia sea cómo se almacena el gráfico. Los 3 algoritmos pueden modificarse para responder de manera eficiente en el momento que desee, pero para admitir a más de 10 mil clientes, la base de datos que utiliza para almacenar el gráfico marca la diferencia. Y aquí tienes otras 2 opciones:
- Uso de la base de datos SQL / NoSQL estándar: esta base de datos debe fragmentarse de alguna manera, ya que debería servir a sus servidores de código (en plural, debido al problema C10K) que ejecutan las búsquedas en el gráfico. Le sugeriría que continúe su investigación en esta área dependiendo del tamaño de los datos del gráfico en sí, pero si logra poner todos los datos en un clúster de Cassandra o en una tecnología similar, se puede optimizar para los tiempos de respuesta que desee. Escalas realmente bien.
- Hace uso del hecho de que el gráfico es en realidad un "mapa" y encuentra una forma de ejecutar consultas de distancia en los datos: Esto potencialmente requiere que cambie la forma en que almacena el gráfico para agregar algo como latitud y longitud. Entonces, en lugar de ejecutar el algoritmo contra el gráfico completo, que es absurdo, optimiza todo el proceso utilizando el hecho de que, dada una cierta cantidad de minutos desde un nodo dado, puede traducir eso a una distancia D en millas (aproximadamente, puede agregar algo como 10-20 millas para estar en el lado seguro) y ejecuta una consulta en la base de datos para obtener todos los nodos hasta esa distancia D y luego ejecuta el algoritmo de su elección contra ese pequeño gráfico. Es importante tener en cuenta que el gráfico que extrae de la base de datos utilizando este método ya le brinda una aproximación de la solución si el tiempo de viaje real en los bordes es algo proporcional a la distancia recorrida (esto no siempre es cierto, por eso es que una aproximación). Para implementar esto a pequeña escala, usaría PostgreSQL + PostGIS, que le permite ejecutar dichas consultas, pero tendrá que hacer una investigación aquí para tratar de encontrar la solución que mejor se adapte a sus necesidades.

¡Espero eso ayude!

Las distancias del camino más corto en un gráfico ponderado le dan a la estructura la estructura de un espacio métrico. En la terminología del espacio métrico, usted está tratando de encontrar la bola cerrada de radio c centrada en s. Tal vez haya alguna investigación sobre el tratamiento de gráficos como espacios métricos discretos computacionalmente manejables. La noción de excentricidad también puede ponerse en juego, donde la excentricidad de un nodo es la distancia máxima desde ese punto a cualquier otro punto. Parece que estás tratando de encontrar el subgrafo máximo con la propiedad de que la excentricidad de s en el subgrafo está delimitada por c.

El algoritmo de Dijkstra puede modificarse claramente para dar lo que buscas. Si en algún punto el algoritmo de Dijkstra quisiera que incluyera un vértice en el conjunto de nodos visitados (los nodos para los que se conoce la distancia final) pero con una distancia resultante que excede de c, deseche ese nodo en lugar de agregarlo a la lista de Nodos visitados. Esto, en efecto, podará el árbol de nodos accesibles desde s. Debe ser razonablemente eficiente.

Ya que está buscando optimizaciones de valores precalculados y resultados temporales, sugeriría buscar algo como el algoritmo Floyd-Warshall, que se utiliza para encontrar la ruta más corta de todos los pares. Una vez que se calcula esto una vez, se puede comenzar desde cualquier otro nodo rápidamente desde los primeros resultados, por lo que le daría todos los resultados temporales que necesita.

Desafortunadamente, el algoritmo es O (V ^ 3) con respecto a la complejidad del tiempo y O (V ^ 2) en la complejidad del espacio, por lo que es bastante caro. Dado que su problema de ejemplo parece ser bastante grande, con respecto a la cantidad de nodos, probablemente no querrá ejecutar ese algoritmo en todo el conjunto de datos, a menos que tenga una gran cantidad de memoria que desee usar al almacenar los datos previamente calculados. resultado de esto.

Dependiendo de los tipos de búsquedas que haga la gente, podría dividir la red de carreteras en secciones más pequeñas y luego ejecutar el algoritmo Floyd-Warshall en el conjunto de datos más pequeño para que no tenga que almacenar todo el resultado todo el tiempo. Esto solo funcionaría si las personas están buscando distancias pequeñas, como en su ejemplo de lugares a 1 hora de distancia. Si la gente estuviera buscando algo dentro de las 1000 millas, dividirlo en pedazos no ayudaría, y calcularlo no se podría hacer en tiempo real dentro de las restricciones de tiempo que proporcionó. Tan eficiente como pueda hacer esto, las búsquedas de todo en un radio masivo como ese van a tomar un tiempo significativo para computar (probablemente mucho más que su restricción de tiempo).

De manera realista, la mejor solución dependerá de cómo la usan las personas y de cuán dispersas están las búsquedas.

Incluso si la gente está buscando cosas a más de 100 millas de distancia, es probable que las autopistas sean la ruta más eficiente, al menos para la mayoría del viaje, así que probablemente podría intentar una optimización para largas distancias ignorando carreteras más pequeñas, excepto cerca del inicio y final del viaje, lo que reduciría significativamente el número de nodos para largas distancias, haciendo que el tiempo de cálculo y la memoria consumida por el Floyd-Warshall sean mucho más razonables. Desafortunadamente, eso no lo ayudará porque todavía necesitará encontrar todos los nodos menos que la distancia dada.

Si le preocupa la velocidad de cálculo y la tensión en su servidor, es posible que deba restringir la cantidad de distancias que va a aceptar.