我面临一个难题：
想象一下，我有一张整个国家的地图，由一个巨大的单元矩阵表示。每个单元格代表 1 平方米的领土。每个 Cell 表示为一个double介于 0 和 1 之间的值，表示遍历该单元的成本。
该地图显然不适合内存。
我正试图围绕一种方法来计算机器人的最佳路径，从起点到终点。我的第一个想法是制作一个类似 TCP 的移动窗口，在移动机器人周围有一个真实地图的小地图，并在里面执行 A* 算法，但我遇到了一些问题，地图有巨大的墙壁，糟糕寻路之类的……
我正在搜索有关 A*-like 算法的文献，但我无法想象出对于这个问题来说什么是一个好的解决方案的近似值。
我想知道是否有人遇到过类似的问题，或者可以帮助提出可能的解决方案！
提前致谢 ：）
由于我不知道确切的数据，这里有一些可能有用的信息：
最短路径的部分路径本身就是最短路径。即，您可以将矩阵拆分为子矩阵并在其中找到（所有）最短路径。请注意，您不必存储所有结果：例如，您可以通过不保存完整路径而只保存信息来节省内存：路径从A到B。中间节点可能会在以后再次计算或存储在文件中以备后用。您甚至可以为某些区域预先计算一些最短路径。
另一种方法是您可能能够以某种方式压缩矩阵。即，如果您的大区域仅包含一个相同的数字，则最好仅存储该数字和该区域的尺寸。
另一种方法（与预先计算一些最短路径有关）是生成地图的不同细节级别。考虑美国的地图，这可能如下所示： 最粗略的细节级别仅包含纽约、洛杉矶、芝加哥、达拉斯、费城、休斯顿和凤凰城。关卡越精细，它们包含的城市就越多，但另一方面，它们显示的整个地图的区域就越小。
您的问题是否有任何特殊结构，例如，三角不等式是否成立/您能否保证最短路径不会来回移动？是否要多次执行查询？（如果是这样，您可以进行预处理以分摊多个查询。）您是否需要精确的最小解决方案，或者 epsilon 因子内的某些东西可以吗？
一种想法是您可以粗化矩阵 - 形成 100 米乘 100 米的正方形，并确定通过 100 × 100 正方形的最短路径距离。现在这将适合内存（大约 1 GB），您可以运行 Dijkstra，然后通过 100 × 100 平方扩展每个步骤。
另外，您是否尝试过运行 Dijkstra 算法的向前向后版本？即从源头扩展，同时寻找汇点，有交叉点时停止。
顺便说一句，为什么需要如此精细的粒度？
以下是一些可能有效的想法
您可以将路径建模为分段线性曲线。如果您有 31 个线段，那么您的曲线由 60 个数字完全描述。每条可能的曲线都有一个成本，因此成本是以下形式的函数
成本（x1，x2，x3 ..... x60）
现在你的问题是找到一个有 60 个变量的函数的全局最优值。您可以使用标准方法来执行此操作。一种想法是使用遗传算法。另一个想法是使用蒙特卡罗方法，例如平行回火
http://en.wikipedia.org/wiki/Parallel_tempering
每当您有一条有希望的路径时，您就可以将其作为起点来找到成本函数的局部最小值。也许你可以使用一些插值来使你的成本函数是可微的。然后你可以使用牛顿法（或者更确切地说是 BFGS）来找到成本函数的局部最小化。
http://en.wikipedia.org/wiki/Local_minimum
http://en.wikipedia.org/wiki/BFGS
您的问题有点类似于在化学系统中寻找反应路径的问题。也许你可以在戴维斯威尔士的《能源景观》一书中找到一些灵感。
但我也有一些问题：