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

Question

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

我的目标是找到离 Lolo 最近的三个街区，这样我就有一个 A、一个 B 和一个 C。此外，每个街区和 Lolo 本人必须在不同的行上：

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

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

对于这个例子，正确的答案是这些块：

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

找出这些块的有效方法是什么？（即使是正确方向的一点也将不胜感激！）谢谢！

Answer 1

我认为你应该使用 DFS

您以以下方式构建 G：

1. 洛洛是根
2. 选择没有颜色的可用块已经访问，加到G上，权重是到Lolo的距离
3. 使同一行上的所有块不可用
4. 如果有更多可用块 转到 2
5. 如果没有可用块返回 Lolo，并选择不是 Lolo 直子的块

构建图表后，您可以运行深度为 3 的 DFS 并选择成本最低的路径。

这将为您提供最短距离。

还有其他限制吗？它需要运行多快？

Answer 2

贪心解决方案：

应该完成下面的所有块选择，以使其遵守行约束。

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

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

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

预处理：

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

附加说明：

假设你只有 3 种颜色，蛮力的运行时间将为 O(n ³ )，这比TSP的 O(n!) 或 O(2 ^{n ) 少很多。}

对蛮力的明显优化是分离所有颜色，这将导致 O(n ₁ n ₂ n ₃ ) 的运行时间，其中 n _i是具有第 i 个颜色的块的数量。