java - 计算占用网格中的最大覆盖路径

Question

我正在实现一个基 native 器人，它使用 SLAM 算法生成其环境的占用网格。它非常简单，没有概率方面的因素，只是一个表示 Empty、Occupied、Unexplored、Unreachable 等的枚举。

我想知道是否有一个众所周知的算法来找到访问所有网格单元一次所需的最短路径(这是一个真空吸尘器!)。这是旅行商问题吗？

我已经研究了几个基于图的解决方案，例如寻找哈密顿循环，但我想知道是否有任何东西可以直接有效地处理网格。

网格大约为 250x250 个单元格。

谢谢!

Answer 1

只是想 id 将我的解决方案添加到这个悬而未决的问题 - 我尝试过的大多数算法在计算上都太复杂了。我选择了使用反向波前算法 非常有效地计算出的最大覆盖路径的近似值。

使用此算法，我能够在大约 5 秒内构建 250x250 网格单元阵列的最大覆盖路径，这在我的场景中当然可以接受。