algorithm - 防止二维网格旅行者重复的最小数据结构

如果这是某个线程的重复，我很抱歉，但我真的不确定如何描述这个问题。

我想知道防止 2D 网格旅行者重复自身的最小数据结构是什么（即旅行到它之前已经旅行过的某个点）。旅行者每次只能水平或垂直移动1步。对于我的特殊情况（如下），二维网格实际上是一个左下角三角形，其中一个坐标永远不会超过另一个。

例如，对于 1D 案例，这可以通过记录上次行进的方向来简单地完成。如果方向改变，它就会重演。

对于 2D 情况，它变得复杂。最简单的方法是创建一个记录之前经过的点的列表，但我想知道是否有更有效的方法来做到这一点？

我正在为4-sum实现或多或少的“4-finger”算法，其中中间的 2 个手指沿两个方向（即i、j、k和l）移动：

  i=>    <=j=>     <=k=>       <=l
1 2 3 ... 71 72 ... 123 124 ... 201 202 203

手指行进的方向由某种算法决定（或建议），但可能导致永远循环。因此，如果中间的2根手指开始重复历史位置，我不得不强制不要采取一些建议。

在这些天中，我找到了2个解决方案。它们都不是这个问题的理想解决方案，但它们至少有点可用：

正如下面提到的@Sorin，一种解决方案是保存一个表示所有单元格状态的位数组。对于此处的三角网格示例，我们甚至可以压缩数组以将内存成本减少一半（尽管需要时间来计算自由度为 2k^2的位位置。标准数组仅使用线性时间）。k
另一种解决方案是直接避免向后旅行。设置算法，j并且k只向一个方向移动（这可能是贪婪的）。

但是由于 2D-grid traveler 有一个很好的属性，它每次都沿着轴 1 移动，我想知道这种运动是否有更“专业”的表示。

谢谢你的帮助！

标签： algorithmsearchdata-structures

如果您正在寻找最佳查找复杂性，那么哈希集是最好的选择。您需要 O(N) 内存，但所有查找和插入都是 O(1)。

如果您经常访问大多数单元格，那么您甚至可以跳过哈希部分并存储一个位数组。那就是为每个单元存储一位，然后检查相应的位是 0 还是 1。这在内存中要紧凑得多（至少 32 倍，一位与一位 int，但可能更多，因为您也跳过了在内部存储一些指针到数据结构，64 位）。

如果这仍然占用太多空间，您可以使用布隆过滤器（链接），但这会给您一些误报（告诉您您访问过一个单元格，但实际上您没有访问过）。如果这是您可以忍受的空间，那么节省的空间是相当巨大的。

BSP 或 Kd 树等其他结构也可以工作。一旦达到所有内容都空闲或被占用的点（忽略上三角形中未使用的单元格），您可以将所有信息存储在单个节点中。这很难推荐，因为它很复杂，而且在许多情况下它也可能使用 O(N) 内存，但常数更大。此外，所有检查都是 O(logN)。