如何改进此算法来解决修改过的邮票拼图？

Question

飞镖之子问题是 Al Zimmermann编程竞赛的竞赛,于2010年6月20日结束:

• 假设您有一个划分为R区域的飞镖靶.每个飞镖靶区域具有与其相关联的正整数值.进一步假设你有D型飞镖并且你把它们扔在飞镖上.每个飞镖都落在一块板的R区域或完全错过了板.您的分数是飞镖落地区域的值的总和.错过董事会的飞镖对你的分数没有贡献.如果多个飞镖落在同一区域,则会多次累积该区域的值.

• 例如,假设R = 5,即飞镖区域具有值(1,2,4,7,11),并且D = 3.如果您的三个飞镖落在区域2,4和11中,则得分为17分.如果一个飞镖错过了棋盘而另外两个掉落在7区,则得到14分.

• 飞镖问题是:对于给定的R和D,确定应该与飞镖的R区域相关联的值,以便最大化通过投掷D飞镖无法达到的最小分数.

  D = number of darts    R = number of dartboard regions
      3                      1 through 40
      4                      1 through 30
      5                      1 through 20
      6                      1 through 10
  

================================================== ================================

使用的基本算法(解释D = 3)

• 我从下面显示的结果数组开始.0和1是飞镖靶区域应该存在的分数.0表示飞镖错过了电路板.所以,我将为41个元素生成这个数组(一个额外补偿0).1是强制性的,因为否则没有其他方式来生成1.

   ____ ____ 
  |    |    |
  |  0 |  1 |
  |____|____|
  

• 我生成了一个临时数组,它使用结果数组中的dart分数显示所有总数是可以实现的,三次抛出.带下划线的元素是用于生成划痕的元素.

  0 = 0 + 0 + 0
  1 = 1 + 0 + 0
  2 = 1 + 1 + 0
  3 = 1 + 1 + 1
   ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____
  | *  | *  | *  | *  |    |    |    |    |    |    |    |    |    |
  |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 | 10 | 11 | 12 |
  |__-_|__-_|____|____|____|____|____|____|____|____|____|____|____|
  

• 现在的结果阵列中的下一个元素的候选者是2,3或4.

  • 2 =元素1大于当前最大元素

  • 4 =极不可能的元素

• 我依次尝试这些候选人,看看每个案例中最小的无法实现的最大元素.例如

  (0,1,2)

   ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ 
  | *  | *  | *  | *  | *  | *  | *  |    |    |    |    |    |    |
  |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 | 10 | 11 | 12 |
  |__-_|__-_|__-_|____|____|____|____|____|____|____|____|____|____|
  

  (0,1,3)

   ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ 
  | *  | *  | *  | *  | *  | *  | *  | *  |    | *  |    |    |    |
  |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 | 10 | 11 | 12 |
  |__-_|__-_|____|__-_|____|____|____|____|____|____|____|____|____|
  

  (0,1,4)

   ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ 
  | *  | *  | *  | *  | *  | *  | *  |    | *  | *  |    |    | *  |
  |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 | 10 | 11 | 12 |
  |__-_|__-_|____|____|__-_|____|____|____|____|____|____|____|____|
  

• max (7, 8, 7) = 8.因此,选择3作为下一个元素.

• 如果假设有一条领带,例如,如果我不得不之间进行选择(0,1,2)和(0,1,4),打破平局我将计数达到号码的数目,其在以下情况下是更(0,1,4).所以,我会选择(0,1,4)在(0,1,2).

• 但在这种情况下,(0,1,3)是赢家和结果集看起来像的下方.然后,我重复这些步骤,直到我有41个元素.

   ____ ____ ____
  |    |    |    |
  |  0 |  1 |  3 |
  |____|____|____|
  

• 该算法是贪婪的,因为它假设(R = 20的解)是(R = 30的解)的子集.因此,我不计算R的每个值的结果,但是我确实计算了D的每个值的结果.因此,对于D = 3,我预测R = 40的结果然后取R的结果的前30个元素例如,= 30.

• 该算法是贪婪的,因为它假设每个步骤(在创建结果数组中)的目标是在阶段达到最小的无法实现的总数.

• 为了能够比强力执行更好,该算法消除了结果数组的一些候选者.例如,在下图所示的情况下(对于(0,1,4)结果数组),我只考虑5,6和7作为下一个元素的候选,并排除2和3,尽管它们仍未使用.在某些情况下,这种假设可能会给我带来不理想的结果,但是当划痕增长到数千个元素时,它确实减少了大量计算.

   ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ 
  | *  | *  | *  | *  | *  | *  | *  |    | *  | *  |    |    | *  |
  |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 | 10 | 11 | 12 |
  |__-_|__-_|____|____|__-_|____|____|____|____|____|____|____|____|
  

对算法的改进

• 由于这没有给出太好的结果,我尝试为D的每个值生成一组结果.例如,我可以选择第二个最佳或第三个最佳元素,而不是为结果选择最佳的下一个元素.因此,对于39个步骤(结果中的41个元素),我可以生成大约3 ^ 39(对于每个选择,我可以有最佳或第二个最佳或第三个最佳元素)的情况太多了.所以,我决定采用最好的一秒钟,最多三分之一的最佳选择.这使案件数量减少到大约⁴⁰ C ₁*³⁹ C ₁ = 577980.如果不是这样的话会导致大量的R值更高的情况(对于更高的D值).

• 在我所拥有的这些~6E5结果中,我计算了每个R值从1到40的最小不可实现元素.因此,每个R值都可以从这些6E5值中选择最佳值.

问题

• 该算法不会产生最佳结果集,甚至不会产生结果.

• 我甚至为D = 3选择了第四和第五个最佳选择,并且他们没有对结果进行任何重大改进.所以,我不知道应该在哪里调整算法.

哪里可以调整此算法以获得更好的结果？

这个算法有没有明显的错误？

欢迎提出任何意见/建议.

_{有关于同一主题的另一个问题在这里.我更想知道我的算法可以改进的地方.}

Answer 1

感谢您提出一个非常有趣的问题！我花了几分钟理解这个问题。

我没有看到这个问题的符号表述，所以，让我尝试在这里提出一个符号。

首先，观察（正如您所做的那样），其中一个区域必须为 1，否则将无法达到 1。

其次，由于我们试图最大化无法达到的分数，因此重复区域值没有意义。

因此，这给出了退化（但不是最优）解决方案：1,2,3,...R

该简并解的目标函数值为： D*R+1

例如，如果您有 D = 4 个飞镖，并且您用分数 1, 2. ..40 为飞镖板着色，那么从值 1 到 160 的每个分数都是可以获得的。161是达不到的。

显然这个解决方案不是最优的，最优解决方案可能涉及 2 的一些幂，并且肯定需要一些思考。

现在的符号：

令 f(X,D,{Y_1..Y_R}) =

• 如果在范围为 Y_1...Y_R 的飞镖板上使用 D 支飞镖可获得 X 分，则为 1
• 如果无法达到则为 0

作为前面讨论的一个例子。f(160,4,{1..40}) = 1 且 f(161,4,{1..40}) = 0

puzzle 的目标函数值可以表示为：

g(D, (Y_1..Y_R}) = 最小 X | f(X,D,{Y_1..Y_R}) = 0

通过之前的观察 1，我们可以假设 Y_1 = 1。

此外，函数f的递归公式可以如下。

f(X,D,{1..Y_R} = 1 如果：

• X=0，或
• 对于某些 j，f(X-Y_j,D-1,{1..Y_R}) = 1

[将继续致力于此工作并在开发时发布更多内容。]