在不完全适合内存的矩阵中寻找路径的最佳算法
我面临着一个难题：
假设我有一张整个国家的地图，由一个巨大的单元矩阵表示。每个单元格代表 1 平方米的领土。每个单元格都表示为 0 到 1 之间的双精度值，表示遍历单元格的成本。
该地图显然无法容纳在内存中。
我试图用一种方法来计算机器人从起点到终点位置的最佳路径。我的第一个想法是制作一个类似 TCP 的移动窗口，在移动机器人周围有一个真实地图的小地图，并在里面执行 A* 算法，但是我遇到了一些带有巨大墙壁的地图的问题，不好寻路等...
我正在搜索有关 A* 类算法的文献，但我无法想象出该问题的良好解决方案的近似值。
我想知道是否有人遇到过类似的问题或可以帮助提供可能的解决方案！
提前致谢 ：）
I'm facing a hard problem:
Imagine I have a map of an entire country, represented by a huge matrix of Cells. Each cell represents a 1 square meter of territory. Each Cell is represented as a double value between 0 and 1 that represents the cost of traversing the cell.
The map obviously is not fittable in memory.
I am trying to wrap my mind arround a way to calculate the optimal path for a robot, from a start point to a end position. The first idea I had was to make a TCP-like moving window, with a minimap of the real map arround the moving robot, and executing the A* algorithm inside there, but I'm facing some problems with maps with huge walls, bad pathfinding, etc...
I am searching the literature about A*-like algorithms and I could not visualize an approximation of what would be a good solution for this problem.
I'm wondering if someone has faced a similar problem or can help with a idea of a possible solution!
Thanks in advance :)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
由于我不知道确切的数据，因此这里有一些可能有用的信息：
最短路径的部分路径本身就是最短路径。即，您可以将矩阵拆分为子矩阵，并在其中找到（所有）最短路径。请注意，您不必存储所有结果：例如，您可以通过不保存完整路径而仅保存信息来节省内存：路径从
A到B。中间节点可能稍后再次计算或存储在文件中以备后用。您甚至可以预先计算某些区域的一些最短路径。另一种方法是您可以以某种方式压缩矩阵。即，如果您有仅由一个相同数字组成的大区域，则最好仅存储该数字和该区域的尺寸。
另一种方法（与预先计算一些最短路径有关）是生成地图的不同细节级别。考虑到美国地图，这可能看起来如下：最粗略的细节级别仅包含纽约、洛杉矶、芝加哥、达拉斯、费城、休斯顿和菲尼克斯等城市。关卡越精细，它们包含的城市就越多，但另一方面，它们显示的整个地图的区域就越小。
Since I do not know exact data, here's some information that could be useful:
A partial path of a shortest path is itself a shortest path. I.e. you might split up your matrix into submatrices and find (all) shortest paths in there. Note that you do not have to store all results: You e.g. can save memory by not saving a complete path but just the information: Path goes from
AtoB. The intermediate nodes might be computed later again or stored in a file for later. You might even be able to precompute some shortest paths for certain areas.Another approach is that you might be able to compress your matrix in some way. I.e. if you have large areas consisting only of one and the same number, it might be good to store just that number and the dimensions of that area.
Another approach (in connection to precompute some shortest paths) is to generate different levels of detail of your map. Considering a map of the USA, this might look the following: The coarsest level of detail contains just the cities New York, Los Angeles, Chicago, Dallas, Philadelphia, Houston und Phoenix. The finer the levels get, the more cities they contain, but - on the other hand - the smaller area of your whole map is shown by them.
你的问题是否有任何特殊的结构，例如，三角形不等式是否成立/你能保证最短路径不会来回移动吗？您想多次执行查询吗？ （如果是这样，您可以进行预处理，以分摊多个查询。）您是否需要精确的最小解决方案，或者 epsilon 因子内的某些内容可以吗？
一种想法是，您可以粗化矩阵 - 形成 100 米 x 100 米的正方形，并确定通过 100 × 100 正方形的最短路径距离。现在这将适合内存（大约 1 GB），您可以运行 Dijkstra，然后将每个步骤扩展到 100 × 100 平方。
另外，您是否尝试过运行 Dijkstra 算法的前向-后向版本？即从源头开始扩展，同时寻找汇点，有交集时停止。
顺便说一句，为什么需要如此精细的粒度？
Does your problem have any special structure, e.g., does the triangle inequality hold/can you guarantee that the shortest path doesn't jog back and forth? Do you want to perform the query many times? (If so you can do pre-processing that will amortize over multiple queries.) Do you need the exact minimum solution, or will something within an epsilon factor be OK?
One thought was that you can coarsen the matrix - form 100 meter by 100 meter squares, and determine the shortest path distances through the 100 \times 100 squares. Now this will fit in memory (about 1 Gigabyte), you can run Dijkstra, and then expand each step through the 100 \times 100 square.
Also, have you tried running a forward-backward version of Dijkstra's algorithm? I.e., expand from the source and search forthe sink at the same time, and stop when there's an intersection.
Incidentally, why do you need such a fine level of granularity?
以下是一些可能有效的想法
您可以将路径建模为分段线性曲线。如果您有 31 条线段，那么您的曲线可以由 60 个数字完整描述。每条可能的曲线都有一个成本，因此成本是以下形式的函数
cost(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
你的问题有点类似于在化学系统中寻找反应路径的问题。也许你可以在戴维斯·威尔士的《能源景观》一书中找到一些灵感。
但我也有一些疑问：
Here are some ideas that may work
You can model your path as a piecewise linear curve. If you have 31 line segments then your curve is fully described by 60 numbers. Each of the possible curves have a cost, so the cost is a function on the following form
cost(x1, x2, x3 ..... x60)
Now your problem is to find the global optimum of a function of 60 variables. You can use standard methods to do this. One idea is to use genetic algorithms. Another idea is to use a monte carlo method such as parallel tempering
http://en.wikipedia.org/wiki/Parallel_tempering
Whenever you have a promising path then you can use it as a starting point to find a local minimum of the cost function. Maybe you can use some interpolation to make your cost function is differentiable. Then you can use Newtons method (or rather BFGS) to find local mimima of the cost function.
http://en.wikipedia.org/wiki/Local_minimum
http://en.wikipedia.org/wiki/BFGS
Your problem is somewhat similar to the problem of finding reaction paths in chemical systems. Maybe you can find some inspiration in the book "Energy Landscapes" by Davis Wales.
But I also have some questions: