Javascript:在(50000 * 50000 网格)二维数组中寻路？

Question

问题

因此，假设一个二维整数值数组代表一个网格 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 索引表示 map 上单元格的坐标，数组中的值表示穿越该单元格地形的相对难度 - 例如 999 可能是粗荆棘，而 2,3,4 可能是一个略微倾斜的路径......或者什么的。

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

问题域

这需要在现代浏览器中运行，其中呈现了一个相当简陋的 map ，我们将在用户输入后通过所有中间顶点绘制一条从 [x,y] 到 [q,r] 的线[q,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 实现以直接对二维数组表示进行操作。

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

Dijkstra 将在单次运行中计算所有节点的成本，因此如果您的起点是固定的，运行一次就足够了——没有必要运行数百万次。

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

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

图像越大，速度越慢，但到目前为止还没有崩溃，但我认为对于您的数据，它会耗尽浏览器中的内存。

Dijkstra 实现使用以下接口(interface)来访问图形——我认为这应该直接在您的数据结构之上提供，而无需在内存中显式生成具有显式节点和边缘的“传统”图形数据结构:

/**
 * 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.P.S.:添加了代码以在第一次点击后显示所有点击的最短路径。还修复了允许对 Angular 线移动的错误:https://goo.gl/wXGwiv

总而言之，虽然这可能无法在浏览器中扩展到 50k x 50x，但我认为这表明 Dijkstra 直接在数组上操作值得在服务器端尝试，并且数组大小与数据数组是存储从单个点开始的所有最短路径所需的全部。