如何改善这种算法求解修改后的邮票拼图？ [英] How can I improve this algorithm for solving a modified Postage Stamp puzzle?

问题描述

的飞镖问题儿子 是对的

Son of Darts Problem was a contest on Al Zimmermann's Programming Contests that ended on 20 Jun 2010 :

  

• 假设你有被划分为R区飞镖盘。每个飞镖地区都有与之相关联的正整数值。再假设你有d飞镖，你在飞镖扔他们每个人。每个镖无论是土地在董事会的ř地区之一或者完全忽略了董事会。你的分数是对于其中飞镖降落的区域中的值的总和。这忽略了董事会飞镖无助于你的分数。如果多个飞镖在同一区域内的土地，你积累了该区域的值多次。

• Suppose that you have a dartboard that is divided into R regions. Each dartboard region has a positive integer value associated with it. Further suppose that you have D darts and that you throw each of them at the dartboard. Each dart either lands in one of the board's R regions or misses the board altogether. Your score is the sum of the values for the regions in which the darts land. A dart that misses the board contributes nothing to your score. If multiple darts land in the same region, you accumulate the value for that region multiple times.

例如，假定R = 5，该飞镖区域具有值（1，2，4，7，11），以及D = 3。如果您的三杆的区域的土地2,4和11你的分数17分。如果一个人镖忽略了董事会和其他两个土地区7中14分。

For example, suppose that R = 5, that the dartboard regions have values (1, 2, 4, 7, 11), and that D = 3. If your three darts land in regions 2, 4 and 11 you score 17 points. If one dart misses the board and the other two land in region 7 you score 14 points.

飞镖问题是这样的：对于一个给定的R＆D，确定哪些值应该用飞镖的ř地区，以便通过投掷飞镖ð最大化最小的得分达不到相关联

The Darts Problem is this: for a given R and D, determine what values should be associated with a dartboard's R regions in order to maximize the smallest score unattainable by throwing D darts.

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 ）

BASIC ALGORITHM USED (explained for D = 3)

• 我开始在结果如下图所示排列。 0 和 1 是应该在那里的飞镖的区域的分数。 0 表示镖错过了董事会。所以，我要产生这个阵列41元（一个额外的补偿 0 ）。 1 是必须放，否则没有其他的方式来产生的 1

• I start with the result array shown below. 0 and 1 are the scores that should be there on the regions of the dartboard. 0 indicates that the dart missed the board. So, I am going to generate this array for 41 elements (one extra to compensate for 0). 1 is compulsary because otherwise there is no other way to generate 1.

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

我产生的从头阵列，它展示了所有总量是可以实现用镖得分结果数组中，三罚全中。强调元素是被用来生成从头那些

I generate the scratch array which shows what all totals are achievable using the dart scores in the result array, in three throws. The elements underlined are the ones that were used to generate the scratch.

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 =元素一个比目前最大的元素更大

• 2 = element one greater than the current largest element

4 =的smallent无法实现的元素

4 = the smallent unachievable element

我尝试这些候选人依次和看到，这是在每种情况下无​​法实现最小元素的最大值。  例如

I try each of these candidates in turn and see that which is the maximum of smallest unachievable elements in each case. For example

（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 被选为下一个元素。

max (7, 8, 7) = 8. So, 3 is chosen as the next element.

如果假设有一条领带，举例来说，如果我有（0，1， 2 ）和（0,1之间进行选择， 4 ），打破平局我也算实现号码的数目是的情况下（0,1更， 4 ）。所以，我会选择（0，1， 4 ）在（0，1， 2 ）。

If suppose there was a tie, for example, if I had to choose between (0, 1, 2) and (0, 1, 4), to break the tie I would count the number of achievable numbers which is more in case of (0, 1, 4). So, I would choose (0, 1, 4) over (0, 1, 2).

但在这种情况下，（0，1， 3 ）是胜​​利者，结果集看起来像下面。然后，我重复上述步骤，直到我有41元。

But in this case, (0, 1, 3) is the winner and the result set looks like below. Then, I repeat the steps until I have 41 elements.

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

的算法是贪婪的，即它假定（对于R = 20溶液）是（溶液对于R = 30）的子集。所以，我没有计算结果对R的每一个值，但我计算D.所以每个值结果为D = 3，我cauculate导致了R = 40，然后把结果R的第30个元素= 30，例如

The algorithm is greedy in the sense that it assumes that (solution for R = 20) is a subset of (solution for R = 30). So, I do not calculate results for each value of R, but I do calculate results for each value of D. So, for D = 3, I cauculate result for R = 40 and then take the first 30 elements of the result for R = 30, for example.

该算法是贪婪的，因为它假设在每一步的目标（在创建的结果数组）是实现最低无法实现总在舞台上的感觉。

The algorithm is greedy in the sense that it assumes that the target at each step (in creating the result array) is to achieve the minimum unachievable total at the stage.

要能够执行比蛮力更好，该算法消除了部分考生的结果数组。例如，在该情况下，下图中描绘的（对于一个（0，1，4）的结果阵列），我只考虑5，第6和7作为候选人的下一个元素并排除2 3，虽然他们还没有使用。这种假设可能给我不理想的结果在某些情况下，但它确实减少了很多的计算时的从头长到数千个元素。

To be able to perform better than brute force, the algorithm eliminates some candidates for the result array. For example, in the case depicted in the diagram below (for a (0, 1, 4) result array), I only consider 5, 6 and 7 as candidates for the next element and exclude 2 and 3 though they are still not used. This assumption might give me suboptimal results in some cases, but it does cut down on a lot of calculation when scratch grows to thousands of elements.

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

改进了算法

• 由于这是没有给予太多的好成绩，我试过发电机组成绩为D的各个值。例如，而不是选择最好的下一个元素对于结果，我也选择第二个最好的或第三最佳元素。因此，对于39步走（到结果41元），我可能会产生约3 ^ 39（每个选择，我可以有最好的还是退而求其次或第三极品元），这是太多的情况下。所以，我决定去与atmost1秒最好atmost三分之一的最佳选择。这减少了病例数约 ⁴⁰ C ₁ * ³⁹ C ₁ = 577980的结果。任何比这更会导致案件数量庞大的R较高的值（的D值越高）。

• Since this was not giving too good results, I tried generating sets of results for each value of D. For example, instead of choosing the best next element for result, I could also choose the second best or the third best element. So, for 39 steps to go (to 41 elements in result), I could generate around 3^39 (for each choice, I can have either the best or the second best or the third best element) cases which is too many. So, I decided to go with atmost one second best and atmost one third best choices. That reduced the number of cases to around ⁴⁰C₁ * ³⁹C₁ = 577980 results. Any more than this would lead to HUGE number of cases for higher values of R (for higher values of D).

出的，我有这些〜6E5的结果，我计算的R 1〜40所以，每一R值到达这些6E5值选择最好的。每个值最小无法实现的元素

Out of these ~6E5 results that I have, I calculate the minimum unachievable element for each value of R from 1 to 40. So, each of the R values gets to choose the best from these 6E5 values.

问题

• 该算法不产生最佳的结果套​​，甚至接近。

我甚为D = 3第四和第五的最佳选择，他们没有给在结果的任何重大改善。所以，我不知道我应该调整我的算法。

I even went to fourth and fifth best choices for D = 3, and they did not give any major improvements in the results. So, I did not know where I should tune my algorithm.

如果所有我可以调整这个算法，以获得更好的结果？

是否有任何明显的失误，该算法使？

Are there any obvious mistakes that the algorithm makes?

任何意见/建议，欢迎。

Any comments/suggestions are welcome.

<子>有关于同一主题的另外一个问题在这里。我更想知道在我的算法可以得到改善。

_{There was another question on the same topic here. I am more interested in knowing where my algorithm can be improved.}

推荐答案

其实，我参加了本次比赛，因为你注意到我把100整体采用收集87.00点。其实我用你的方法，因为我意识到发生的每一个问题一个合理的解决方案是要克服的第一道关卡。在我跑了的时候，所产生的点就足以把我周围的94分，但由于高收入者提高自己的分数，这一数字迅速下降到75左右。

I actually participated in this contest, as you notice I placed 100th overall with 87.00 points collected.  I actually used your method because I realized generating a "reasonable" solution for every problem was the first hurdle to overcome.  At the time I ran it, the points generated were enough to put me up around 94 points but as the top earners improved their scores, that number fell quickly to around 75.  

您可以做的第一和最简单的事情是要认识到你的程序在瞬间运行，如果没有，你应该花时间优化屁滚尿流的第一位。一旦它运行在足够快的时间，您就可以在 D = 3 ， R＆其中每一个可能的设置; = 5 在任何时候都。然后，您可以使用内置 R = 5 作为种子的贪心算法。而不是一个贪婪的解决方案，现在，你有几千个，而你只需要跟踪每个电平R产生的最高值，并造成了它的价值。这是很容易做的，这将让你的分数高达80以上。

The first and easiest thing you can do is to realize that your program runs in an instant, and if it doesn't you should spend time optimizing the crap out of that first.  Once it runs in fast enough time, you can generate every possible set for D = 3, R <= 5 in no time at all.  You can then use the sets at R = 5 as seeds for your greedy algorithm.  Now instead of one greedy solution, you have a few thousand, and you just need to keep track of the highest value generated at each level R and the values which create it.  That is easy enough to do, and this will get your score up above 80.

我花了近一个月的优化，可以测试任何随机的输入设置，以便我能够泵出我的种子发生器 R = 10 并运行它在功能约8小时的单核。这保证了有D = 3，最佳的解决方案为r = 10'和更好的答案时， R＆GT; 10 比我早与原来的贪婪造成的。这引起了我的分数pretty的接近的地方，它运行后，结束了研究了尽可能高的每个 D 同时仍能够在单个天运行该程序。我能达到 R = 9 为 D = 4 ， R = 8 为 D = 5 和 R = 8 为 D = 6 。

I spent almost a month optimizing the function which can test any random input set so that I was able to pump up my seed generator to R = 10 and run it in about 8 hours on a single core.  This guaranteed having the best possible solution for 'D = 3', 'R <= 10' and much better answers when R > 10 than I had with the original greedy result.  This got my score pretty close to where it ended after running R up as high as possible for each D while still being able to run the program in a single day.  I was able to reach R = 9 for D = 4, R = 8 for D = 5, and R = 8 for D = 6.

在这些被运行我计算过，我将无法增加研究 1为任何 D 刚刚上市过的数字，并将它完成其执行在我的有生之年。显然，现在是时候寻找新的技术。我想我在做由测试前端每一个可能的起始段一项伟大的工作，那么为什么通过为每个我的出发段的测试更深的结果集不移位一些是到后端。而是抓住了最好的下一个结果在同一水平上，我进行了2级向前看，从两个层次深以最好的下一个值。举例来说，你总是以一个1，那么你列举所有值 R = 2（2，3，4），然后为每个的，评估所有可能的值为 R = 3 。所以 2（3，4，5，6，7），3-（4，5，6，7，8），4（5，6，7）。以最高的那些评价，然后选择在 R = 2 的值，其中包含了 R = 3 。这需要更多的处理时间，并要求我降低最高研究我可以用种子，但它产生了更深层次的搜索更好的结果。

After these were run I calculated that I wouldn't be able to increase R by 1 for any D over the numbers just listed and have it complete its execution in my lifetime.  Obviously it was time to look for a new technique.  I figured I was doing a great job on the front end by test every possible starting segment, so why not shift some of that to the back end by testing deeper result sets for each of my starting segments.  Instead of grabbing the best next result on the same level, I performed a 2 level look ahead and take the best next value from two levels deep.  For instance, you always start with a 1, then you enumerate all values for R = 2 (2, 3, 4) and then for each of those, evaluate all possible values for R = 3.  So 2 (3, 4, 5, 6, 7), 3 (4, 5, 6, 7, 8), 4 (5, 6, 7).  Take the highest of all those evaluations, and then choose the value at R = 2 which contains the highest value for R = 3.  This required a lot more processing time and required me to lower the max R I could use to seed it, but it produced better results for the deeper searches.

在这一点上我放弃了贪婪的方法和用于本次大赛以扩大我的AI知识。我尝试使用各种蒙特卡洛技术以及一个基本遗传算法。我学到了很多关于蒙特卡洛，并在查找一些顶级表演者在这场竞争中，找到优化的蒙特卡罗选择标准这是超出了我的理解的出版物。我希望我能帮助你进一步，但我有信心他们认为突破90点贪婪的做法是不太可能在我的有生之年。我很想看看如何更好的答案会得到，如果它是多线程的，和一帮权力被扔吧。

At this point I gave up on greedy approaches and used this competition to expand my AI knowledge.  I tried using various monte carlo techniques as well as a basic genetic algorithm.  I learned a lot about monte carlo, and in looking up some of the top performers in this competition, found publications on optimizations for monte carlo selection criteria which was beyond my understanding.  I wish I could help you out further, but I feel confident in arguing that breaking 90 points with a greedy approach is very unlikely in my lifetime.  I would be interested to see how much better the answers would get if it were multithreaded and a bunch of power was thrown at it.

我没有任何我做的这个问题，我的工作，但我记得显示，向前看，开始种子更大的枚举要贪心算法对于这个问题只有两个可能的改进。我对那些东西今晚发布的思维过程在这里如果我能找到的注意事项。

I don't have any of the work I did for this problem with me, but I remember showing that look ahead and greater enumeration of starting seeds were the only two possible improvements to the greedy algorithm for this problem.  I'll for that stuff tonight and post the thought process here if I can find the notes.

编辑：code最初发布在已废弃的服务器。请留言，如果你想它重新发布。

code originally posted on server which has been abandoned. Please message if you'd like it to be re-posted.

这篇关于如何改善这种算法求解修改后的邮票拼图？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！