28

这个问题出现在一个挑战中，但由于它现在已经关闭，所以应该可以询问它。

问题（不是这个问题本身，这只是背景信息）可以这样直观地描述，借用自己的形象：

盖方块

我选择以最佳方式解决它。这可能（对于决策变体）是一个 NP 完全问题（它肯定在 NP 中，而且它闻起来像一个精确覆盖，尽管我还没有证明可以将一般精确覆盖问题简化为它），但这很好，它只需要在实践中快速，不一定在最坏的情况下。在这个问题的上下文中，我对任何近似算法都不感兴趣，除非它们提供削减。

有一个明显的 ILP 模型：生成所有可能的方格（如果方格仅覆盖存在的网格单元格，则方格是可能的），x_i为每个方格引入一个二进制变量，指示我们是否使用它，然后

minimize sum x_i

subject to:
1) x_i is an integer
2) 0 ≤ x_i ≤ 1
3) for every cell c
       (sum[j | c ϵ square_j] x_j) = 1

约束 3 表示每个单元只被覆盖一次。约束 1 和 2 使 x_i 二进制。最小解给出了原始问题的最优解。

这个（即忽略约束 1）的线性松弛是半体面的，但它会做这样的事情（这是一个 6x6 网格，左上角缺失）：

分数解

这里选择了 13 个正方形的“一半”（客观值为 6.5），大小（这样你可以更容易地找到它们）

  • 1 的 4x4
  • 3 的 3 x 3
  • 6 个 2x2
  • 3 个 1x1

此实例的最佳解决方案的目标值为 8，例如：

整数解

线性放松是半体面的，但我并不完全满意。差距有时超过 10%，这有时会导致整数阶段非常缓慢。

这就是实际问题出现的地方，是否有额外的约束可以添加（懒惰地）作为削减，以改进分数解决方案？

我已经尝试了问题的替代公式来找到切割，例如，而不是选择正方形，如果我们选择“左上角”和“右下角”，然后将它们匹配以形成不重叠的正方形覆盖所有细胞？然后在每个“类似反斜杠的对角线”上，必须有匹配数量的左上角和右下角。但这无济于事，因为如果我们选择正方形，那么无论如何该条件总是正确的，在分数解决方案中也是如此。

我还尝试了一些关于重叠的推理，例如，如果两个正方形明显重叠，它们的总和不能大于 1，并且可以通过添加完全包含在重叠区域中的所有正方形来改进。但该约束不如所有单元格仅被覆盖一次的约束强大。

我尝试过对总面积进行推理（例如，总覆盖面积必须等于单元格的数量），但这已经通过每个单元格必须被覆盖一次的约束来保证，并根据总面积来说明只允许更多的自由。

我也尝试过用平方数（每个平方的面积是，嗯，一个平方）和平方数的差异做一些事情，但这也没有任何有用的结果。

4

5 回答 5

6

我使用了分支和价格方法来解决类似的问题（ITA 的草莓地；向下滚动）。这是我的代码，它（缺少注释）可能只是作为我知道我在说什么的零知识证明。它比商业求解器（我不会命名）快几个数量级。

关键是分支策略。而不是直接在x_i变量上分支，这可能是您的求解器正在做的事情，而是在更高级别的决策上分支。我在 Strawberry Fields 中使用的是决定两个单元格是否会被同一个正方形覆盖。如果您针对分数解决方案最关注的对，那么解决方案的结构似乎设置得相当快。

不幸的是，我无法为您提供如何将其编程到现有整数程序求解器中的建议。对于 Strawberry Fields，我使用自定义所有内容，主要是因为我想要，但部分是因为我正在动态生成列，使用累积网格行和网格列总和来快速评估矩形。

于 2015-06-25T12:22:45.917 回答
3

目标函数值的约束

每当目标函数值是非整数时——例如，因为你在分数解中有奇数个 0.5 权重的平方——你可以“直接在目标函数上”添加一个切割来强制它到下一个更高的积分值：例如，在您的示例分数解决方案中，有 13 个正方形，每个正方形的权重为 0.5，总目标函数值为 6.5，您可以添加所有 x_i 的总和 >= 7 的约束。

更一般的削减

这导致了一个更通用的规则，只要您有一个分数解决方案，其中某些单元子集 C 被具有非整数总权重 w 的某些正方形子集 S“完全覆盖”，该规则就会起作用。通过“完全覆盖”，我的意思是 S 中的每个正方形都具有非零权重，并且共同为 C 中的每个单元格提供总权重 1，并且不与 C 之外的任何单元格重叠。您可以通过以下方式轻松找到这些单元格子集创建一个图，其中每个单元格都有一个顶点，两个顶点之间有一条边，只要它们（部分）被分数解决方案中的同一个正方形覆盖：该图的每个连接组件都是一个（最小）这样的子集。

给定一个分数解，上面有一些精确覆盖的单元子集 C 和正方形子集 S，令 T 是仅与 C 中的单元重叠的所有正方形的集合（显然 T 是 S 的超集）。我们知道，LP 子问题的任何最优解 X 仅由单元子集 C（以及候选方格的相关子集 T）组成，其总权重必须与 S 相同，因为如果不这样，这将与原始 LP 的分数解决方案：您可以将 S 替换为 X 并获得更好的解决方案。

现在，原始问题有两组解决方案（其中任何一个都可能是空的）：没有正方形覆盖 C 中的单元格和 C 外部单元格的那些解决方案，以及至少有一些正方形覆盖的那些解决方案。我们要禁止总权重 < RoundUp(w)的第一类解决方案。令 U 是与 C 中至少一个单元格和 C 外至少一个单元格重叠的所有正方形的集合。我们可以通过添加约束来实现这一点

Sum_{square_i in T}(x_i) + RoundUp(w) * Sum_{square_j in U}(x_j) >= RoundUp(w)

将 LHS 上的第二项乘以 RoundUp(w) 的效果是，即使在解决方案中包含一个同时覆盖 C 中的一个单元格和某个其他单元格的单个正方形，该约束也有效地“消失”。这是必要的，因为 S 和 C 没有告诉我们有关原始问题的此类解决方案的任何信息，因此我们不能排除它们。请注意，包含正方形子集 S 的原始解决方案将被此约束禁止，因为 U 中的每个正方形在此解决方案中的权重必须为 0。

没有灵丹妙药

第二种方法比第一种方法更强大，因为它可能会发生，例如，图形包含两个分量，每个分量都有奇数个正方形，所有正方形的权重均为 0.5：这意味着总体上存在偶数个平方数，意味着整体目标函数值是整数，防止在目标函数上添加切割的可能性。但即使一次又一次地应用这些削减并不能保证最终会找到一个可行的解决方案：作为一个具体的例子，任何时候网格本身是水平和/或垂直对称但可以被一组不对称的正方形覆盖，然后它可以很容易地被该组正方形的水平和/或垂直翻转版本所覆盖——更烦人的是，被任何“仿射组合”覆盖 这两个正方形集合（即，通过权重总和为 1 的任何组合）。一般来说，可能有许多同样好的可行解决方案，我在这里描述的削减无法阻止 LP 求解器返回一个包含所有 k 个“叠加”的解决方案，所有正方形的权重为 1/ ķ。

[编辑 2015 年 1 月 7 日]

光明的一面！

虽然，正如我上面提到的，没有办法让 LP 求解器从几个对称最优覆盖的部分“叠加”中“隔离”一个特定的可行覆盖，但有一个好消息：如果你确实得到了这样的叠加，实际上很容易从中恢复一个最优的、可行的覆盖。您需要做的就是贪婪地挑选重量不为零的方块，每次都划掉与您刚刚挑选的方块重叠的任何方块。如果解决方案是我所描述的叠加，则保证可以工作，并且同样重要的是：如果此过程适用于分数解决方案（也就是说，如果重复这个贪婪的步骤最终覆盖了所有的单元格）那么你得到的解决方案一定是最优的！（假设不是：让 X 是 LP 求解器返回的最优分数解，让 F 是你刚刚从它贪婪地提取的可行解，让 y 是 F 中任何正方形的最小权重。请注意，每个正方形在 F 中，至少 y 对每个像元的覆盖值有贡献；因此，由于假设 F 是次优的，因此从 F 中每个正方形的权重中减去 y 并将 X 中的所有其他权重按 1/(1-y) 缩放将给出另一个（可能是分数）较低权重的解，与 X 的最优性相矛盾。）

证明任何分数解决方案（i）在“覆盖图”中具有非整数总重量的某些分量，或（ii）由这样的叠加组成，这将非常有用：这意味着您可以继续应用我的“将军”削减直到你得到一个叠加，然后你可以贪婪地解决它。但就目前而言，这两个类别之外可能还有分数解决方案。

于 2015-07-01T01:44:26.570 回答
2

我会使用像A*这样的搜索来找到解决方案。重要的是要注意A*类似于贪婪 的最佳优先搜索，因为它可以使用启发式来引导自己。假设您有正确的启发式方法，它将在合理的时间内找到接近最优 (~0.95) 的解决方案。

在此处输入图像描述

示例解决方案使用 18 个块而不是示例中所示的 19 个。除了启发式之外，您还可以使用一些预计算来提高算法的有效性。例如，我计算了每个位置的自由梯度。例如，您的初始地图变成了一个舞台：

在此处输入图像描述

您可以拥有自己的启发式方法，它可以同样好，甚至更好。我使用它只是因为我发现它是微不足道的。阶段数字具有以下含义：数字越大 - 越有可能出现在一个大盒子中（您可以得出更多的限制，但这是一个开始）。

阶段值是 4 个酒窖自动化规则的总和。

在此处输入图像描述

例如左上角

cell(x,y) := min(cell(x,y-1) ?? 0, cell(x-1,y) ?? 0, cell(x-1,y-1) ?? 0) + 1

这 ？？运算符称为空合并运算符。如果操作数不为空，则返回左侧操作数；否则返回右手操作数。

此外，您可以通过删除从预计算和每个阶段获得的已知解决方案来减少所需的计算工作。在这种情况下，状态 0：

在此处输入图像描述

算法本身会重复：

  1. 订购单元格并取最高值
  2. 订单自动化规则结果并取最高
  3. 寻找微不足道的切入点

在此处输入图像描述 在此处输入图像描述

如果您想为更大的网格获得更快的结果，那么一种相当直接的方法是扩展预计算以编译模板。之后，您可以进行模板缩减。

例如，您可以有一个模板（左上角）

--+++
+-+++
+++++

您可以生成它的哈希并将其添加到值为 4 的 hashmap/dictionary（这意味着它至少需要 4 个矩形来覆盖 +'s）。然后你有 5x3 范围和相同的散列，你知道这是一个微不足道的截断，成本为 4。

这更快的原因是与计算接近恒定速度的哈希相比，比较需要很多时间。

或者，有一种方法可以催眠我们是否或正在寻找什么样的解决方案。使用 Wolfram Mathematica 函数FindMinimum它看起来像：

FindMinimum[{
  a + b + c + d + e + f + g, 
  (a 1^2 + b 2^2 + c 3^2 + d 4^2 + e 5^2 + f 6^2 + g 7^2) == 119 &&
  a >= 0 && b >= 0 && c >= 0 && d >= 0 && e >= 0 && f >= 0 && g >= 0 &&
  a \[Element] Integers &&
  b \[Element] Integers &&
  c \[Element] Integers &&
  d \[Element] Integers &&
  e \[Element] Integers &&
  f \[Element] Integers &&
  g \[Element] Integers
}, {a,b,c,d,e,f,g}]

这是基于我们有 119 个单元格的 12x12 网格的假设，它将为我们提供使用网格大小计数的最佳解决方案。

遗憾的是， wolfram alpha搜索引擎可能不会解释这一点，也许在将来。

于 2015-07-02T10:40:09.787 回答
1

动态编程：选择一个单元格（任何单元格都可以），计算覆盖它的所有有效方格（即仅覆盖当前单元格和网格中的其他单元格）。对于每个这样的正方形，递归获取剩余区域的最小覆盖值（网格减去正方形），然后从中选择最小值（结果是该值 + 1）。为了使事情变得更快，请尝试在每个递归级别中选择一个具有最少有效覆盖方块的单元格（从而减少每个级别中的递归调用次数）。

真的很简单。

于 2015-06-30T19:23:00.133 回答
0

除了没有重叠的约束之外，如何使用正方形的总面积等于要覆盖的总面积的约束？这应该比检查双覆盖约束更胖。

于 2015-06-30T11:35:44.970 回答