2

所以,我想做一个能够穿越未知迷宫的机器人。提供给它的唯一信息是迷宫的单色位图图像,机器人必须从中识别起点和终点,它必须将其携带的球装在其中的盒子,并规划它的路径迷宫。它必须从迷宫的那个 bmp 图像中完成所有这些工作。这是指向迷宫的示例位图图像的链接。

由于完成所有这些处理,我将使用 arduino。目前,我已将此 BMP 读入 2D 字符数组,链接到字符数组,从中制作连接图/图,以便可以在其上应用路径规划算法(Dijkstra 或广度优先搜索)。

然而问题如下,这个位图的大小是 96x56 像素。这意味着连接图/图的大小将是 [5376][5376],非常大。要声明这么大的数组将需要以 MB 为单位的内存,而 arduino 的 SRAM 只有 96KB。

我应该怎么办?请建议。我只是电气工程一年级的学生,所以对所有这些东西都不太了解。我想到的一件事是删除相同的行(请参阅二维数组)。但是后来我想,它本身将需要大量的处理能力,因为我必须逐个元素地将每一行与其他行进行比较。这里的问题基本上是内存和处理限制。

我将不胜感激!

4

1 回答 1

0

您实际上不必将整个图形显式存储在内存中。或者,每次算法访问一个状态时,您可以查询位图以查看哪些邻居没有被占用,并相应地生成有效的转换/成本。这将需要更多的处理能力,但会将运动模型保持在处理器的内存限制范围内。

但是,对于 BFS 或 Dijkstra 算法,您还必须存储访问状态的队列,该队列可能会呈指数增长。您可能需要考虑使用 A* 而不是 Dijkstra 算法,因为 A* 将探索比 Dijkstra 算法更少的状态来找到最佳解决方案。

于 2018-01-11T15:22:55.700 回答