挑战：拍摄48x48图像，查找连续的区域，从而导致最便宜的乐高解决方案来创建该图像！ [关闭
https://stackoverflow.com/questions/5307253
-
24-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
背景
乐高产生 X大灰色底板, 这是一个大型建筑板，宽48个螺柱，高48个螺柱，总面积为2304个螺柱。作为乐高狂热者，我已经建模了一些镶嵌风格的设计，这些设计可以放在这些基础板上，然后可能挂在墙壁上或显示屏上（请参阅：请参阅： 安卓, 梦想剧院, 银河帝国, 口袋妖怪).
挑战
我的挑战现在是获得购买这些设计的最低成本。购买2304个单独的1x1板会变得昂贵。使用 砖砌, ，本质上是乐高的eBay，我可以找到数据来确定给定颜色最便宜的零件。例如，1x4板的价格为0.10美元（或每螺柱0.025美元），比6x6板的价格便宜，价格为$ 2.16（或每螺柱0.06美元）。我们还可以确定所有可用于组装图像的可能板的列表：
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图像？您如何找到使用最少的组件（不一定是最便宜）的解决方案？如果我们要添加角落件作为允许的作品，您将如何考虑它们？
我们可以假设我们有一些通过查询砖链接，获得给定颜色的给定砖的平均价格获得的主列表，并将其作为列表中的元素添加。因此，仅仅因为没有制造或出售黑色16x16板。然而，16x16亮绿板的价值为3.74美元， 当前可用平均价格.
我希望我对这个问题的文章足够瘦。这是我几天一直在想的事情，我对你们的想法感到好奇。我将其标记为“面试问题”，因为它具有挑战性，不是因为我通过面试获得了它（尽管我认为这是一个有趣的问题！）。
编辑
这是指向 2x2角片 和 4x4角落. 。答案不一定需要考虑到颜色，但是应该可以扩展以涵盖该方案。场景是，并非所有板块都有所有颜色可用，因此请想象我们有一系列元素可以识别板，其颜色和该板的平均成本（示例为下面）。感谢本杰明提供赏金！
1x1|white|.07
1x1|yellow|.04
[...]
1x2|white|.05
1x2|yellow|.04
[...]
此列表将没有条目：
8x8|yellow|imaginarydollaramount
这是因为不存在8x8黄板。列表本身是微不足道的，只能被认为是为解决方案提供参考。它不会影响解决方案本身。
Edit2
为了清楚起见，改变了一些措辞。
解决方案
卡尔的方法基本上是合理的，但可以使用更多细节。它将找到最佳的成本解决方案，但是对于某些输入而言，它太慢了。大型开放区域，特别是有太多的可能性来搜寻天真。
无论如何，我在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日，我将无法使用，所以希望我什么都没有错过！
其他提示
脚步
步骤1：遍历所有解决方案。
步骤2：找到最便宜的解决方案。
创建库存
对于可能的一系列可能的碎片（包括每种颜色的单块），请至少对每块n重复，其中n = max（每种颜色的板＃/件＃）。因此，最多可以按区域覆盖整个板的所有颜色。
现在，我们有了大量可能的作品，因为保证该系列的一部分将完全填充板子。
然后它成为一个子集问题，它是NP完整的。
解决子集问题
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上尝试使用它，并带有一组相当小的碎片。然后逐渐增加碎片和板尺寸。我真的不知道该程序会花多长时间 - 但是很想有人告诉我！
首先，您使用洪水填充物将问题分解为填补乐高积木的连续区域。然后，对于每个人，您都可以使用带有回忆的DFS。洪水填充是微不足道的，所以我不会更远地描述它。
确保遵循右手规则，同时将搜索树扩展到不重复状态。
我的解决方案将是：
- 按螺柱成本对所有零件进行排序。
- 对于排序列表中的每个作品，请尝试将尽可能多的放置在盘子中：
- 栅格是您设计的2D图像，寻找具有均匀颜色的图像区域，当前件的形状和该件将使用的每个螺柱的免费螺柱。
- 如果该特定作品中发现的区域的颜色不存在，请忽略继续搜索。
- 如果存在颜色：标记该零件使用的螺柱，并为这种颜料和该颜色增加计数器。
- 第2步将用于平方零件，两次用于矩形碎片（一次垂直和水平一次），转角块4次。
- 迭代到2，直到盘子已满或没有更多类型的碎片。
到达结束后，您将拥有每种碎片的数量和每种颜色的数量，而您将需要最低成本。
如果存根的成本可以按颜色改变，那么原始排序列表不仅必须包括颜色的零件类型。
