algoritmo - Javascript: ¿Búsqueda de ruta en una matriz 2D de (50000*50000)?

El problema

Entonces, digamos que uno imagina una matriz bidimensional de valores enteros que representa un mapa en cuadrícula, como este: +-----+------+-----+-----+-----+ | 10 | 2 | 2 | 4 | 656 | +-----+------+-----+-----+-----+ | 234 | 165 | 724 | 759 | 230 | +-----+------+-----+-----+-----+ | 843 | 734 | 999 | 143 | 213 | +-----+------+-----+-----+-----+ | 242 | 2135 | 131 | 24 | 374 | +-----+------+-----+-----+-----+ | 159 | 464 | 155 | 124 | 151 | +-----+------+-----+-----+-----+

Los índices bidimensionales representan las coordenadas de una celda en el mapa, y los valores en el arreglo representan la dificultad relativa de atravesar el terreno de esa celda; por ejemplo, 999 podrían ser zarzas densas, mientras que 2,3,4 podría ser un camino ligeramente inclinado... o algo así.

Ahora queremos encontrar el camino más fácil desde [x,y] en la cuadrícula hasta [q,r] en la cuadrícula (donde la suma de los pasos sea lo más baja posible, en otras palabras)

El dominio del problema

Esto necesita ejecutarse en un navegador moderno, donde se muestra un mapa bastante espartano, y dibujaremos una línea desde [x,y] hasta [q,r] a través de todos los vértices intermedios, después de que el usuario haya ingresado [q,r]. Convenientemente, [X,Y] siempre es el mismo (digamos [0,0] para simplificar)

¡Así que usa el algoritmo de Dijkstra o A*!

Así que mi primer instinto fue modelar el arreglo como un grafo, aplicar el algoritmo de Dijkstra y trabajar a partir de ahí. Y en el caso anterior, con una cuadrícula de 5x5, eso funciona bien. Recorro cada índice del arreglo y uso el valor, y los valores adyacentes, para generar un nodo con aristas ponderadas hacia todos sus vecinos. Esto construye un grafo al que luego puedo aplicar el algoritmo de Dijkstra.

Sin embargo, en la práctica, ¡trabajaré con matrices de hasta 50,000 x 50,000 de tamaño! ¡Eso son 250 millones!

Así que, obviamente, construir un grafo sobre la marcha para ejecutar el algoritmo de Dijkstra no es aplicable. Mi siguiente idea fue precomputar los caminos (el conjunto de datos es fijo), almacenarlos en el servidor y hacer un callback cuando obtenemos el destino [q,r]... pero esto son 250,000,000 caminos... incluso si lograra que se ejecute en menos de un segundo (lo cual no creo que sea posible), tomaría años computar todos los caminos...

Creo que podría necesitar tomar otro enfoque, pero no estoy seguro, ¿cómo puedo hacer que esto funcione?

Respuesta #1

No construyas un gráfico explícito (los punteros son costosos): usa pares de coordenadas para representar nodos en la cola y modifica tu implementación de Dijkstra para operar directamente sobre tu representación en arreglo 2D.

Usa un arreglo similar al arreglo de costos para almacenar las distancias (inicialmente tentativas) calculadas por el algoritmo.

Dijkstra calculará los costos a todos los nodos en una sola ejecución, así que si tu punto de partida está fijo, ejecutarlo una vez debería ser suficiente; no hay necesidad de ejecutarlo millones de veces.

P.D.: Creé un Jsfiddle ejecutando Dijkstra en imágenes: https://goo.gl/5GWwMF

Calcula las distancias a todos los puntos desde un clic del ratón, donde los píxeles más oscuros se interpretan como más costosos...

Se vuelve más lento con imágenes más grandes, pero hasta ahora no ha logrado bloquearse, aunque creo que para tus datos se quedará sin memoria en el navegador.

La implementación de Dijkstra utiliza la siguiente interfaz para acceder al grafo: creo que esto debería ser bastante sencillo de proporcionar sobre tu estructura de datos sin generar explícitamente una estructura de grafo "tradicional" con nodos y aristas explícitas en la memoria:

/**
 * The interface the Dijkstra implementation below uses
 * to access the graph and to store the calculated final
 * and intermediate distance data.
 *
 * @Interface
 */
Graph = function() {};

/**
 * Returns the current distance for the given node.
 * @param {Object} node
 * @return {number}
 */
Graph.currentDistance = function(node) {};

/**
 * Stores the current distance for the given node.
 * @param {Object} node
 * @param {number} distance
 */
Graph.setCurrentDistance = function(node, distance) {};

/**
 * Returns an array of connected nodes for the given node, 
 * including the distances.
 *
 * @param {Object}
 * @return {Array<{cost:number, node:Object}>}
 */
Graph.connections = function(node) {};

P.D.S.: Se añadió código para mostrar el camino más corto en todos los clics después del primer clic. También se corrigió un error que permitía el movimiento diagonal: https://goo.gl/wXGwiv

Entonces, en conclusión, aunque esto probablemente no se escale a 50k x 50k en el navegador, creo que esto muestra que ejecutar Dijkstra directamente sobre los arreglos vale la pena intentarlo en el lado del servidor, y que un arreglo idéntico en tamaño al arreglo de datos es todo lo que se necesita para almacenar todos los caminos más cortos desde un solo punto.