30

背景

乐高生产的X-Large Grey Baseplate是一块大型积木板，宽 48 个螺柱，高 48 个螺柱，总面积为 2304 个螺柱。作为一个乐高狂热者，我制作了一些马赛克风格的设计模型，这些设计可以放在这些底板上，然后可能挂在墙上或展示中（参见：Android、梦剧场、银河帝国、口袋妖怪）。

挑战

我现在的挑战是以最低的成本购买这些设计。购买 2304 个单独的 1x1 板可能会变得昂贵。使用BrickLink，本质上是乐高的 eBay，我可以找到数据来确定给定颜色最便宜的零件。例如，0.10 美元（或每个螺柱 0.025 美元）的 1x4 板将比 2.16 美元（或每个螺柱 0.06 美元）的 6x6 板便宜。我们还可以确定可用于组合图像的所有可能板块的列表：

1x1
1x2
1x3
1x4
1x6
1x8
1x10
1x12    
2x2 corner!    
2x2
2x3
2x4
2x6
2x8
2x10
2x12
2x16    
4x4 corner!    
4x4
4x6
4x8
4x10
4x12    
6x6
6x8
6x10
6x12
6x14
6x16
6x24    
8x8
8x11
8x16    
16x16

问题

对于这个问题，假设我们有一个所有盘子的列表、它们的颜色以及每个盘子的“重量”或成本。为了简单起见，我们甚至可以移除角落部分，但这将是一个有趣的挑战。您如何找到最便宜的组件来创建 48x48 图像？您如何找到使用最少组件（不一定是最便宜）的解决方案？如果我们将角件添加为允许件，您将如何解释它们？

我们可以假设我们有一些通过查询 BrickLink 获得的主列表，获取给定颜色的给定砖的平均价格，并将其作为元素添加到列表中。因此，不会仅仅因为它不是制造或出售的黑色 16x16 板。然而，16x16 亮绿色板的价值为 3.74 美元，按当前可用的平均价格计算。

我希望我对这个问题的描述足够简洁。这是我这几天一直在想的事情，我很好奇你们的想法。我将其标记为“面试问题”是因为它具有挑战性，而不是因为我通过面试得到了它（尽管我认为这将是一个有趣的问题！）。

编辑

这是2x2 角件和4x4 角件的链接。答案不一定需要考虑颜色，但它应该可以扩展以涵盖该场景。这种情况是，并非所有的盘子都提供所有颜色，所以想象我们有一个元素数组来标识一个盘子、它的颜色和该盘子的平均成本（一个例子如下）。感谢本杰明提供赏金！

1x1|white|.07
1x1|yellow|.04
[...]
1x2|white|.05
1x2|yellow|.04
[...]

此列表不会包含以下条目：

8x8|yellow|imaginarydollaramount

这是因为不存在 8x8 黄色板。该列表本身是微不足道的，只应被视为为解决方案提供参考；它不会影响解决方案本身。

编辑2

为了清楚起见，更改了一些措辞。

4

4 回答 4

7

Karl 的方法基本上是合理的，但可以使用更多细节。它将找到最佳成本解决方案，但对于某些输入来说太慢了。尤其是大型开放区域将有太多天真地搜索的可能性。

无论如何，我在这里用 C++ 快速实现了：http: //pastebin.com/S6FpuBMc

它用 4 种不同的砖块解决了填充空白空间（周期）的问题：

0: 1x1 cost = 1000
1: 1x2 cost = 150
2: 2x1 cost = 150
3: 1x3 cost = 250
4: 3x1 cost = 250
5: 3x3 cost = 1

..........       1112222221
...#####..       111#####11
..#....#..       11#2222#13
..####.#..       11####1#13
..#....#..       22#1221#13
..........       1221122555
..##..#...  -->  11##11#555
..#.#.#...       11#1#1#555
..#..##...       11#11##221
..........       1122112211
......#..#       122221#11#
...####.#.       555####1#0
...#..##..       555#22##22
...####...       555####444  total cost = 7352

因此，该算法填充给定区域。它是递归的（DFS）：

FindBestCostToFillInRemainingArea()
{  
  - find next empty square
  - if no empty square, return 0
  - for each piece type available
    - if it's legal to place the piece with upper-left corner on the empty square
      - place the piece
      - total cost = cost to place this piece + FindBestCostToFillInRemainingArea()
      - remove the piece
  return the cheapest "total cost" found
}

一旦我们找出填充子区域的最便宜的方法，我们将缓存结果。为了非常有效地识别子区域，我们将使用 64 位整数和Zobrist散列法。警告：哈希冲突可能导致不正确的结果。一旦我们的例程返回，我们就可以根据我们的缓存值重建最佳解决方案。

优化： 在示例中，探索了 41936 个节点（递归调用）（从上到下搜索空方格）。然而，如果我们从左到右搜索空方格，大约有 900,000 个节点被探索。

对于大型开放区域：我建议找到最具成本效益的一块并用该块填充很多开放区域作为预处理步骤。另一种技术是将您的图像划分为几个区域，并分别优化每个区域。

祝你好运！我将在 3 月 26 日之前无法使用，所以希望我没有错过任何东西！

于 2011-03-18T21:45:35.290 回答
4

脚步

第 1 步：遍历所有解决方案。

第 2 步：找到最便宜的解决方案。

创建件库存

对于一组可能的棋子（包括每种颜色的单个棋子），每个棋子至少复制 n 个副本，其中 n = max(board#/piece# of each color)。因此，最多 n 块可以按区域覆盖整个电路板的所有颜色。

现在我们有大量可能的棋子集合，有界，因为可以保证这个集合的一个子集将完全填满棋盘。

然后它变成了一个子集问题，即NP-Complete。

解决子集问题

For each unused piece in the set
  For each possible rotation (e.g. for a square only 1, for a rectangle piece 2, for an elbow piece 4)
    For each possible position in the *remaining* open places on board matching the color and rotation of the piece
      - Put down the piece
      - Mark the piece as used from the set
      - Recursively decent on the board (with already some pieces filled)

优化

显然，作为一个 O(2^n) 算法，尽早修剪搜索树至关重要。必须尽早进行优化以避免长时间运行。n 是一个很大的数；只需考虑一块 48x48 板——仅单件就有 48x48xc（其中 c = 颜色数）。

因此，必须从前几百层中修剪 99% 的搜索树，以便该算法随时完成。例如，记录迄今为止找到的最低成本解决方案，并在当前成本加上（空板位置数 x 每种颜色的最低平均成本）> 当前最低成本解决方案时停止搜索所有较低层并回溯。

例如，通过始终优先考虑最大的部分（或最低的平均成本部分）来进一步优化，以便尽快降低基线最低成本解决方案并修剪尽可能多的未来案例。

寻找最便宜的

计算每个解决方案的成本，找到最便宜的！

注释

这个算法是通用的。它不假设一块是相同的颜色（你可以有多色的块！）。它并不假设大件比小件的总和便宜。它并没有真正假设任何事情。

如果可以做出一些假设，那么这个信息可以被用来尽可能早地进一步修剪搜索树。例如，当仅使用单色棋子时，您可以修剪棋盘的大部分（颜色错误）并修剪一组中的大量棋子（颜色错误）。

建议

不要试图一次做 48x48。尝试在一些小的东西上，比如 8x8，用一组相当小的碎片。然后逐步增加件数和板尺寸。我真的不知道该计划需要多长时间 - 但希望有人告诉我！

于 2011-03-22T13:22:21.703 回答
2

首先，您使用洪水填充将问题分解为填充乐高积木的连续区域。然后对于其中的每一个，您都可以使用带有您希望的记忆功能的 dfs。洪水填充是微不足道的，所以我不会再描述它了。

确保在扩展搜索树以不重复状态时遵循右手规则。

于 2011-03-15T05:24:41.303 回答
1

我的解决方案是：

  1. 按螺柱成本对所有部分进行排序。
  2. 对于排序列表中的每一块，尝试将尽可能多的放在盘子中：
    • 光栅化您的设计的 2D 图像，寻找具有统一颜色的图像区域、当前部件的形状以及该部件将使用的每个螺柱的自由螺柱。
    • 如果该特定部分不存在找到的区域颜色，则忽略继续搜索。
    • 如果颜色存在：标记该件使用的螺柱并为该件和该颜色增加一个计数器。
    • 步骤 2 将针对方形棋子进行一次，对矩形棋子进行两次（一次垂直和一次水平），对角棋子进行 4 次。
  3. 重复到 2 直到盘子装满或没有更多类型的碎片可用。

一旦到达终点，您将以最低的成本获得所需的每种类型和每种颜色的数量。

如果按存根计算的成本可以按颜色更改，那么原始排序列表必须不仅包括按件的类型，还包括颜色。

于 2011-03-23T17:25:55.060 回答