Javascript：在（50000 * 50000网格）2d数组中寻路？

小编典典

Javascript：在（50000 * 50000网格）2d数组中寻路？

algorithm

问题

因此，假设有人想象一个二维值的整数数组，它表示一个网格映射，如下所示： +-----+------+-----+-----+-----+ | 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， r]。方便地，[X，Y]始终相同（为简单起见，假设为[0,0]）

因此，请使用Dijkstra的算法或A *！

因此，我的第一个直觉是将数组建模为图形，应用Dijkstra的算法并从那里开始工作。在上述情况下，使用5x5网格，效果很好。我遍历每个数组索引，并使用值和相邻值来生成一个节点，该节点的所有相邻节点均具有加权边。这将建立一个图，然后可以将Dijkstra的算法应用于该图。

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

因此，显然无法即时构建图形来运行Dijkstra的算法。我的下一个想法是预先计算路径（数据集是固定的），将它们存储在服务器上，并在到达目标[q，r]时执行回调…但这是250,000,000条路径…甚至如果我让它在不到一秒钟的时间内运行（我认为不会），那么计算所有路径将需要数年时间…

我认为我可能需要采取另一种方法，但是我不确定如何使这项工作有效？

阅读 432

2020-07-28

共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值得在服务器端尝试，并且大小与数据数组相同的数组值得从单个点存储所有最短路径所需的全部操作。

2020-07-28