Javascript:在(50000*50000网格)2d阵列中寻路？

Question

问题

所以,假设有人想象一个2-d整数值数组,它代表一个gridded-map,如下所示: +-----+------+-----+-----+-----+ | 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 | +-----+------+-----+-----+-----+

2d索引表示地图上单元格的坐标,数组中的值表示遍历该单元格地形的相对难度 - 例如999可能是粗荆棘,而2,3,4可能是稍微倾斜的路径......或者其他东西.

现在我们想找到从网格上的[x,y]到网格上的[q,r]的最简单路径(其中步长的总和是最低的,换句话说)

问题域

这需要在现代浏览器中运行,其中渲染相当简洁的地图,并且在用户输入[q之后,我们将通过所有中间顶点绘制从[x,y]到[q,r]的线. R].方便的是,[X,Y]总是相同的(简单来说[0,0])

所以使用Dijkstra的算法或A*!

所以我的第一直觉是将数组建模为图形,应用Dijkstra的算法并从那里开始工作.在上面的例子中,使用5x5网格,工作正常.我遍历每个数组索引,并使用值和相邻值生成一个节点,该节点的所有邻居都有加权边.这构建了一个图表,然后我可以应用Dijkstra的算法.

但是,实际上,我将使用最大50,000 x 50,000的阵列!那是2.5亿!

因此,显然构建运行Dijkstra算法的图形是不适用的.我的下一个想法是预先计算路径(数据集是固定的),将它们存储在服务器上并在我们到达目的地[q,r]时进行回调...但这是250,000,000个路径...甚至如果我让它在不到一秒的时间内运行(我认为不会这样),那么计算所有路径需要数年时间......

我想我可能需要采取另一种方法,但我不确定,我怎样才能做到这一点？

Answer 1

不要构造显式图(指针很昂贵) - 使用坐标对来表示队列中的节点,并修改Dijkstra实现以直接对您的2d数组表示进行操作.

使用类似于costs数组的数组来存储算法计算的(最初暂定的)距离.

Dijkstra将计算单次运行中所有节点的成本,因此如果您的起点是固定的,那么运行一次就足够了 - 无需运行数百万次.

PS:在图像上创建了一个运行Dijkstra的Jsfiddle:https://goo.gl/5GWwMF

通过鼠标单击计算到所有点的距离,其中较暗的像素被解释为更昂贵...

对于较大的图像,它会变慢,但到目前为止还没有成功崩溃,但我认为对于您的数据,它将在浏览器中耗尽内存.

Dijkstra实现使用以下接口来访问图形 - 我认为这应该是直接提供在数据结构之上而不显式生成具有显式节点和内存边缘的"传统"图形数据结构:

/**
 * 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) {};

PPS:添加了代码,以便在第一次单击后显示所有点击的短路径.还修复了允许对角线移动的错误:https://goo.gl/wXGwiv

总而言之,虽然这可能不会在浏览器中扩展到50k x 50x,但我认为这表明直接在阵列上运行的Dijkstra值得在服务器端尝试,并且与数据阵列大小相同的数组是从一个点存储所有最短路径所需的一切.