算法 - 如何有效地配对 block

Question

比方说，我们有两个 3X3 的立方体，单元格中的高度不同。每个单元格值代表该单元格的高度。例如，在下面的 block 1 中，cell (1,1) 的高度为 1，cell(1,2) 的高度为 2，依此类推。

block 1，

1 2 3
1 3 2
3 1 2

block 2，

4 3 2
4 2 3
2 4 3

给两个这样的 block 如何有效地检查两个 block 是否可以以没有单元格不匹配的方式连接并且两个 block 一起产生 cuboid .

例如，上面的 block-1 + block-2 可以连接起来，结果 block 将是一个完美的长方体，高度为 5。结果长方体将是，

5 5 5
5 5 5
5 5 5

问题的扩展:给定一组 (size >= 50K) 这样的 4X4 block 如何连接成对的 block 并产生合成长方体的最大高度和？您只能采用匹配 block 的全高来最大化总高度总和。不匹配的 block 将被忽略。每个单元格高度最多可达 20 个单位。

问题的进一步扩展: block 可以以这样一种方式给出，即可以旋转以与其他 block 配对以最大化所得长方体的高度总和。

有什么线索吗？

Answer 1

您可以分两步解决该问题 (1) 找到所有连接的 block 对(构建一个长方体)和 (2) 找到使总高度最大化的最佳配对。

寻找连接对

为此，我将 (a) 为每个 block 构建一个表面表示，(b) 通过表面表示对 block 进行哈希处理，以及 (c) 通过查找连接表面模型来搜索每个 block 的所有连接 block 。

(a) 构建表面模型

基本思想是用它的表面来表示每个 block 。为此，您只需从矩阵中的每个条目中减去矩阵中的最小条目

block-1 的表面表示将是

1 2 3   -1   0 1 2       
1 3 2   -->  0 2 1
3 1 2        2 0 2

block-2 的表面表示将是

4 3 2   -2    2 1 0
4 2 3   -->   2 0 1
2 4 3         0 2 1

(b) 散列 block

现在你通过它们的表面表示散列 block

(c) 寻找连接对

对于每个 block ，您然后计算连接表面模型，方法是取表面表示中的最大值并从中减去矩阵中的条目，

对于 block-1 这将产生

    0 1 2     2 1 0     
2 - 0 2 1  =  2 0 1   
    2 0 2     0 2 0

可以使用哈希表找到具有此表面表示的 block (请注意， block 2 的表面表示将匹配)。

注意:当您允许旋转时，您将不得不对哈希表执行 4 次查询，并进行所有可能的旋转。

寻找最佳配对

为了找到最佳配对(最大化连接 block 的总和)，我会使用 Hungarian Algorithm .为此，您必须构建一个矩阵，其中条目 (i, j) 包含当两个 block i 和 j 连接时 block 的高度，否则为 0。

编辑

我认为第二步(寻找最佳配对)可以更有效地完成，方法是贪婪地连接成对的匹配 block (首先连接导致最高 block 的对)。

直觉是:当您有两个 block a 和 b 并且它们都具有相同的表面模型时。然后它们要么都连接到另一个 block c，要么都不连接到 c。考虑到这一点，在“查找连接对”步骤之后，您将得到成对的 block 组 (X_i, Y_i)，其中 X< sub>i 连接到 Y_i 的每个 block 。如果 X_i 和 Y_i 这两个组的大小相等，那么我们可以以任何我们想要的方式连接，并且总能得到相同的长方体高度总和。如果其中一组 (wlog Y_i) 包含较少的元素，那么我们要避免连接到 X_i 中的最小块。因此，我们可以从最大的 block 开始贪婪地连接，并在这样做时避免连接到最小的 block 。

因此该算法可以按如下方式工作:

1. (根据其表面表示散列每个 block 。排序具有相同表面表示的 block 根据降序它们的偏移量( block 的高度减去表面表示)

2. 按偏移量降序处理 block ，对于每个 block :搜索为了连接具有最高偏移量的 block cBlock，将两者连接起来blocks，从哈希表中移除cBlock并进行处理管道。

总体而言，这应该在 O(n log n)

内可行