algorithm - 最近的 block ，每种颜色一个，但在不同的行上

Question

假设我有一个房间，里面有 3 种不同颜色的方 block ，分别标记为 A、B 和 C:

我的目标是找到离 Lolo 最近的三个方 block ，这样我就有一个 A、一个 B 和一个 C。此外，每个方 block 和 Lolo 自己必须在不同的行上:

例如，不能使用第 1 行上的 block ，因为 Lolo 在该行上:

如果我们选择 Lolo 上方的 A block ，则不能使用第 0 行的其他 block :

对于这个例子，正确的答案是这些 block :

我可以很容易地找到离洛洛最近的三个街区；但是，我很难应用额外的约束(每个字母之一，不在同一行)。这感觉像是旅行商问题的变体。

找出这些 block 的有效方法是什么？ (即使是正确方向的一点也将不胜感激!)谢谢!

Answer 1

贪心解法:

下面所有的 block 选择都应该遵循行约束。

1. 选择最近的尚未选择的 block (假设这是 A)。
2. 选择最近的非 A block (假设这是 B)。
3. 选择最近的非 A、非 B(因此是 C) block 。
4. 记录这个距离。
5. 如果与 B 在同一行中有更近的 C，则选择那个 C 以及下一个最接近的 B 并记录距离。
   • 对于超过 3 种颜色，您只想在不同的行中选择下一个最接近的 B。
6. 如果最近的未拾取 block 比 bestDistanceSoFar/3 更远，则停止，否则从 1 开始重复。
7. 返回最佳距离。

为此，我建议为每种颜色准备一个排序列表。

我相信这是最优的，但为什么会这样需要一些思考。

预处理:

如前所述，您可以移除与 Lolo 在同一行中的所有方 block ，但也可以移除比同一行中的另一个相同类型的方 block 距离 Lolo 更远的所有方 block ，在这种情况下不是很多，但仍然如此。

补充说明:

鉴于你只有 3 种颜色，蛮力的运行时间将为 O(n³)，这比 O(n!) 或 O(2< TSP 的 sup>n)。

暴力破解的明显优化是分离所有颜色，这将导致运行时间为 O(n₁n₂n₃ ) 其中 n_i 是具有第 i 种颜色的 block 的数量。