我现在面临一个难题矩阵路径寻找最优算法：在不适合完全到内存
想象我有地图是整个国家的，由细胞的一个巨大的矩阵表示。每个单元代表1平方米的领土。每个单元表示为介于0和1之间的double值，表示遍历单元的成本。
地图显然不适合在内存中。
我试图围绕一种方式来计算机器人从起点到终点的最佳路径。我的第一个想法是制作一个类似TCP的移动窗口，在移动机器人周围绘制真实地图的小地图，并在其中执行A *算法，但是我遇到了墙壁很大的地图存在的一些问题，寻路等...
我正在搜索关于类似A *算法的文献，并且我无法想象这个问题的解决方案的近似值。
我想知道是否有人遇到了类似的问题，或者可以帮助提出可能的解决方案！
感谢提前:)
因为我不知道确切的数据，这里的一些信息，可能是有用的：
的最短路径的部分路径本身就是一个最短路径。即你可能会将你的矩阵分成子矩阵并找到（全部）最短路径。请注意，您不必储存全部结果：您可以通过不保存完整路径来节省内存，但只是信息：路径从A到B。中间节点可能稍后再计算或存储在文件中供以后使用。您甚至可以预先计算某些区域的最短路径。
另一种方法是你可能能够以某种方式压缩你的矩阵。即如果您的大面积区域只包含同一个号码，则只需存储该号码和该区域的尺寸即可。
另一种方法（预先计算一些最短路径）是为了生成不同级别的地图细节。考虑到美国的地图，这可能看起来如下：最粗糙的细节包含纽约，洛杉矶，芝加哥，达拉斯，费城，休斯顿和菲尼克斯等城市。级别越高，它们包含的城市越多，但是 - 另一方面，整个地图的较小区域由它们显示。
您的问题是否有任何特殊结构，例如，三角不等式是否成立/您能保证最短路径不会来回跳动吗？你想多次执行查询吗？ （如果是这样，你可以做预处理，将分摊在多个查询。）你需要确切的最低限度的解决方案，或将在一个epsilon因素内的东西是好的？
一个想法是，你可以粗化矩阵 - 形成100米乘100平方米，并确定通过100乘100平方的最短路径距离。现在这将适合内存（大约1千兆字节），您可以运行Dijkstra，然后展开100 \ times 100 square的每一步。
另外，你有没有试过运行Dijkstra算法的向前 - 向后版本？即，从源头扩展并同时搜索接收器，并在有交叉点时停止。
顺便说一下，为什么你需要这样精细的粒度级别？
这个问题没有任何特殊的结构，它只是每个节点上有权重的矩阵的特例。查询应该只执行一次，确切的解决方案会很好，但它应该是计算上合理的，所以一个足够好的解决方案是可以的。这个想法与phimuemue表达的一样，但应该使用低存储器算法。问题是什么？ – CatOsMandros 2010-11-01 21:32:37
这里有一些想法，可能工作
您可以将路径建模为分段线性曲线。如果你有31条线段，那么你的曲线完全由60个数字来描述。每一个可能的曲线中有一个成本，所以成本以下表格上的功能
成本（X1，X2，X3 ..... X60）
现在你的问题是要找到全局最优解60个变量的函数。您可以使用标准方法来执行此操作。一个想法是使用遗传算法。另一个想法是使用蒙特卡洛方法，如并行回火
http://en.wikipedia.org/wiki/Parallel_tempering
只要你有一个有希望的路径，那么你可以使用它作为一个出发点，找到成本函数的局部最小值。也许你可以使用一些插值来使你的成本函数是可微的。然后，您可以使用牛顿法（或者BFGS）来查找成本函数的局部mimima。
http://en.wikipedia.org/wiki/Local_minimum
http://en.wikipedia.org/wiki/BFGS
你的问题有点类似于在寻找化学反应系统路径的问题。也许你可以在戴维斯威尔士的“能源景观”一书中找到一些启发。
但我也有一些问题：
>您是否有必要找到最佳路径，或者您只是在寻找一条好路径？确切的解决方案会很好，但它应该是计算上合理的，所以一个足够好的解决方案是好的 – CatOsMandros 2010-11-07 09:51:42
你有多少计算机的功率和时间？有限的，但时间不是限制，所以它没关系... – CatOsMandros 2010-11-07 09:52:17
机器人可以做出急转弯，还是你需要额外的物理模型来提高成本函数？我不必关心那个:)。 – CatOsMandros 2010-11-07 09:54:50
具有不同层次的细节将是一个不错的主意。如果我理解正确，一个9x9的矩阵可以分成3x3的矩阵，其中每个单元本身就是一个3x3矩阵，其值由启发函数决定。和A *一样，启发函数不应该高估成本，也不会找到最佳路径。让我感到困惑的是，当我计算每个子矩阵内的路径时，我应该如何定位开始点和结束点？ – CatOsMandros 2010-11-01 17:16:52