问题
所以,假设有人想象一个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个路径...甚至如果我让它在不到一秒的时间内运行(我认为不会这样),那么计算所有路径需要数年时间......
我想我可能需要采取另一种方法,但我不确定,我怎样才能做到这一点？