在棋盘中构造阻挡集，从中禁止矩形

Question

假设我们有一个m * n单位正方形的棋盘。考虑其中形状a * b的矩形多联骨牌，其中a小于或等于m，b小于或等于n。如果任何这样的多边形（及其旋转）与S中的至少一个单位正方形相交，则板的单位正方形S的子集称为类型（a，b）的阻塞集。现在我想找到构造a的算法阻塞集具有最少的单位正方形。

我问过同样的问题，关于MSE中最小阻塞集大小的封闭公式，希望这次解决方案会更容易。

---

虽然现在已经有了一些答案，但我认为我有责任使这个问题更清楚。让我举一个具体的例子。假设我们的棋盘大小为6 * 6。在这个momemt让我们考虑案例a = 2，b = 3。例如，下图中的黄色块是其上的两个2 * 3矩形多面体。

现在想想下面的红色单位正方形的集合S.

很容易检查板上的任何2 * 3矩形多边形都必须与S相交，并且通过鸽笼原理，任何阻挡组必须包括至少6个单位方格，因此S也是最小的。当然，S并不是唯一的，因为人们可以找到另一个与它不相同的最小阻塞集。确切地说，我正在寻找的是一种算法，用于在板上构建一个最小的阻塞集，就像上面的红色集S一样，但是对于一般的四倍（m，n，a，b）。我希望这个解释有效。

Answer 1

标准的动态编程解决方案是保持一组“通过配置文件粘贴在此行之后的最低成本”。不幸的是，有max(a, b)^m这样的配置文件可能，所以它不能很好地扩展到大矩形。

然而，作为一种简化，我们可以尽可能地向上和向下滑动每个矩形。这确实减少了一些配置文件的数量。

话虽如此，这里运行Python代码来解决这个问题。但请注意，即使是发现blocking(11,10, 4,3)就像120这样简单的事情也需要一些时间才能运行。这是因为它必须跟踪多少数据，以及它创建了多少临时垃圾。

def blocking (m, n, a, b):
    # Small optimization.
    if (m < n):
        (m, n) = (n, m)
    # We start before with a row with nothing sticking up, of cost 0 to get here.
    last_solutions = {
        tuple([0 for i in range(m)]): 0
        }
    # Now advance one row, n times.
    for i in range(n):
        next_solutions = {}
        for (profile, cost) in last_solutions.items():
            carried_profile = tuple([i-1 for i in profile])
            for (new_profile, incremental_cost) in advance_row(carried_profile, a, b):
                if tuple(reversed(new_profile)) < new_profile:
                    # By symmetry we only need to look at one of these.  Look at the other!
                    pass
                elif new_profile in next_solutions:
                    next_solutions[new_profile] = min(next_solutions[new_profile], cost + incremental_cost)
                else:
                    next_solutions[new_profile] = cost + incremental_cost
        last_solutions = next_solutions
    return min(last_solutions.values())

def advance_row(profile, a, b, p=0):
    if len(profile) <= p:
        # We reached the end.  Yield it.
        yield (profile, 0)
    else:
        if 0 < profile[p]:
            # It is OK to put no block here.
            for (next_profile, cost) in advance_row(profile, a, b, p+1):
                yield (next_profile, cost)
        area = a * b
        if profile[p] < b:
            # We might place a block a x b here
            new_profile = add_in_rectangle(profile, a, b, p)
            for (next_profile, cost) in advance_row(new_profile, a, b, p+1):
                yield (next_profile, cost+area)
        if profile[b] < b:
            # We might place a block b x a here
            new_profile = add_in_rectangle(profile, b, a, p)
            for (next_profile, cost) in advance_row(new_profile, a, b, p+1):
                yield (next_profile, cost+area)

# Creates a copy of the profile with a block of length a, height b
# filled in starting at position p
def add_in_rectangle(profile, a, b, p):
    # Make a copy
    new_profile = [x for x in profile]
    for i in range(p, min(p + b, len(profile))):
        new_profile[i] = max(profile[i], a)
    return tuple(new_profile)

Answer 2

这是第二种可能更快的方法，但我不会花时间对其进行编码。但是因为它与我的其他解决方案无关，所以我会将它作为一个单独的答案。

将局部倾斜的轮廓集视为图的节点。从每一个中你可以构造一组边，这是添加一个矩形的结果，该矩形的底边覆盖了未完全填充的底行的最左边的空方格。（这将为每个节点提供a + b边。）

现在从节点构造一个A*搜索，该搜索与完全填充的节点无关。从任何节点，估计的成本是a*b的最小倍数，其大于空方块的数量。

如果通常情况下通过贪婪搜索可以产生最佳平铺，则此搜索将很快发现并给您答案。如果不是这样，它只需要回溯。

即使它确实回溯，你跟踪你去过哪些节点的事实将为你提供DP解决方案的好处，可能会更好地修剪你必须分析的可能性。