我面临一个难题：
想象一下，我有一个整个国家的 Map ，由巨大的细胞矩阵代表 . 每个单元代表1平方米的领土 . 每个Cell表示为介于0和1之间的 double 值，表示遍历该单元的成本 .
Map 显然不适合记忆 .
我试图用一种方法来计算机器人的最佳路径，从起点到终点 . 我的第一个想法就是制作一个类似TCP的移动窗口，移动机器人周围的真实 Map 的小 Map ，并在那里执行A *算法，但是我遇到了一些有巨大墙壁的 Map 的问题，不好寻路等...
我正在搜索关于A *类算法的文献，我无法想象出这个问题的一个很好的解决方案的近似值 .
我想知道是否有人遇到类似的问题或者可以帮助解决可能的解决方案！
提前致谢 ：）
3 回答
由于我不知道确切的数据，这里有一些可能有用的信息：
最短路径的部分路径本身是最短路径 . 即您可以将矩阵拆分为子矩阵并找到（所有）最短路径 . 请注意，您不必存储所有结果：例如，可以通过不保存完整路径而只保存信息来节省内存：路径从
A到B. 中间节点可以稍后再次计算或存储在文件中以供稍后使用 . 您甚至可以为某些区域预先计算一些最短路径 .另一种方法是您可以以某种方式压缩矩阵 . 即如果你的大区域只包含一个相同的数字，那么最好只存储那个数字和那个区域的尺寸 .
另一种方法（与预先计算一些最短路径相关）是生成 Map 的不同级别的细节 . 考虑到美国的 Map ，这可能看起来如下：最粗略的细节包含纽约，洛杉矶，芝加哥，达拉斯，费城，休斯顿和菲尼克斯等城市 . 等级越精细，它们包含的城市越多，但另一方面 - 整个 Map 的较小区域由它们显示 .
你的问题是否有任何特殊结构，例如，三角不等式是否保持/你能保证最短路径不来回慢进吗？您想多次执行查询吗？ （如果是这样，您可以进行预处理，以便在多个查询中分摊 . ）您是否需要确切的最小解决方案，或者epsilon因子中的某些内容是否正常？
一种想法是你可以粗化矩阵 - 形成100米乘100米的正方形，并确定通过100×100平方的最短路径距离 . 现在这将适合内存（大约1千兆字节），你可以运行Dijkstra，然后通过100 \ 100平方展开每一步 .
另外，您是否尝试过运行Dijkstra算法的前后版本？即，从源头扩展并同时搜索水槽，并在有交叉点时停止 .
顺便说一句，为什么你需要如此精细的粒度级别？
以下是一些可行的想法
您可以将路径建模为分段线性曲线 . 如果您有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
您的问题有点类似于在化学系统中找到反应路径的问题 . 也许你可以在戴维斯威尔士的“能源景观”一书中找到一些灵感 .
但我也有一些问题：
您是否有必要找到最佳路径，或者您只是在寻找一条好路径？
你有多少电脑电量和时间手？
机器人可以急转弯，还是需要额外的物理建模来改善成本函数？