algorithm - 哪种数据结构最适合存储占用网格中探索节点的顺序？

Question

我有多个机器人，它们通过某种算法探索占用网格。我正在尝试保存已探索节点的顺序。但是我不确定，可以使用哪种数据结构来有效地保存它们。

我首先想到的是一棵树，但是顺序是可以重复的，比如1,2,5,1。所以，我觉得，用树的形式存储这样的顺序可能太复杂了。然后，我想到了一个数组，但就大型网格的内存而言，它可能过于昂贵。

我现在有点迷茫。什么数据结构会更好(假设网格有 10,000 个节点)。但关键是在这种情况下探索节点的顺序将大于 10,000，因为会有重叠。

谢谢!

Answer 1

树在这里没有什么意义，需要保留插入顺序并需要允许重复。基本上，据我了解，我们希望以尽可能紧凑的形式存储机器人行进的路径。

一种紧凑的、连续的序列最终在这里最有意义(例如数组)。它比任何链接结构(包括树)都便宜，因为没有要存储的链接。

我们几乎无法进一步压缩内存使用量。

但是，展开的列表在这里可能会有所帮助。由于它不是一个巨大的连续 block ，而是一系列较小的 block (例如:每个 4 KB)链接在一起，因此如果您想减少内存使用，您可以开始将列表前面的 block 卸载到磁盘。链接开销是微不足道的，因为我们只存储每 N 个元素的链接，其中 N 可能是一个很大的数字。