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

Z时代
2024-01-10
分类：问答

因此，假设有人想象一个二维值的整数数组，它表示一个网格映射，如下所示： +-----+------+-----+-----+-----+ | 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的算法并从那里开始工作。在上述情况下，使用5x5网格，效果很好。我遍历每个数组索引，并使用值和相邻值来生成一个节点，该节点的所有相邻节点均具有加权边。这将建立一个图，然后可以将Dijkstra的算法应用于该图。

但是，实际上，我将使用最大阵列！那是2.5亿！

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

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

回答：

不要构造显式图（指针很昂贵）-使用成对的坐标来表示队列中的节点，并修改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) {};