算法 - 如何有效地配对块

Question

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

块-1,

1 2 3
1 3 2
3 1 2

块-2，

4 3 2
4 2 3
2 4 3

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

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

5 5 5
5 5 5
5 5 5

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

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

有什么线索吗？

Answer 1

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

找到连接对

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

(a) 建立表面模型

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

块 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) 散列块

现在你通过它们的表面表示对块进行哈希处理

(c) 寻找连接对

对于每个块，您然后通过取表面表示中的最大值并从中减去矩阵中的条目来计算连接表面模型，

对于 block-1 这将产生

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

可以使用散列 table 找到具有此表面表示的块（请注意，块 2 的表面表示将匹配）。

注意：当您允许旋转时，您将必须对哈希 table 执行 4 次查询，并进行所有可能的旋转。

寻找最佳配对

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

编辑

我认为第二步（找到最佳配对）可以更有效地完成，通过贪婪地连接匹配块对（首先连接对导致最高块）。

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

所以算法可以按如下方式工作：

(根据其表面表示对每个块进行哈希处理。排序具有相同表面表示的块根据降序它们的偏移量（块的高度减去表面表示）
按偏移量降序处理块，对于每个块：搜索为了连接具有最高偏移量的块 cBlock，将两者连接起来块，从散列 table 中删除 cBlock 并进行处理管道.

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

内可行

算法 - 如何有效地配对块

Algorithm - How to pair blocks efficiently

algorithm

multidimensional-array

data-structures

2d

cube