算法的问题：包装棒成一排 [英] Algorithm problem: Packing rods into a row

问题描述

好了，这可能是一个棘手的问题。它实际上是一个比喻与我的实际应用程序的另一个类似的问题，但我已经简化成为清楚起见，这个假设的问题。这里有云：

Alright, this might be a tricky problem. It is actually an analogy for another similar problem relating to my actual application, but I've simplified it into this hypothetical problem for clarity. Here goes:

1. 在我有一个线棒，我需要进行排序的。因为它是一个行中，只有1维需要关注的问题。
2. 棒是不同的长度和不同的权重。有体重和长度之间没有相关性。小棒可以是非常沉重的，而一个大拉杆可以很轻。
3. 的棒需要由重量排序。
4. 的的真正的前提条件是，但是，的部分的棒只能放置的不超过的某些从线开始的距离，更不管他们的体重。任何地方在这之前是好的，但。
5. 在不保证此限制将被隔开足够远，互相prevent约束棒的可能性挤进重叠。在此（希望罕见）情况下，或者在杆需要被重新安排以某种方式的限制范围内，以产生所需的空间，或一个理想的折衷解决方案可能需要被找到（如违反至少光杆的约束，为例子）。
6. 是可能的在该附加约束可被添加*除了长度约束，以指示特定的（和甚至非妥协）的边界线，其中棒的内的未来日期不能的重叠成。

1. I have a line of rods I need to be sorted. Because it is a line, only 1 dimension needs to be of concern.
2. Rods are different lengths and different weights. There is no correlation between weight and length. A small rod can be extremely heavy, while a large rod can be very light.
3. The rods need to be sorted by weight.
4. The real catch is, however, some rods can only be placed no more than certain distances from the start of the line, regardless of their weight. Anywhere before that is fine, though.
5. No guarantee is given that constraints will be spaced enough away from each other to prevent the possibility of constrained rods being squeezed into overlapping. In this (hopefully rare) case, either the rods need to be re-arranged somehow within their constraints to create the needed space, or an ideal compromise solution may need to be found (such as violating a constraint of the least light rod, for example).
6. It is possible at a future date that additional constraints may be added *in addition to the length constraint to indicate specific (and even non-compromising) boundaries within the line where rods cannot overlap into.

我目前的解决方案，不占后者的情况下，他们听起来像他们会涉及到一些复杂的工作来解决这些问题。

My current solution does not account for the latter situations, and they sound like they'll involve some complex work to resolve them.

请注意，这是一个客户端Web应用程序，因此使得href="http://stackoverflow.com/questions/3829762/linear-programming-with-javascript">适用于Javascript的将是有益的！

Note that this is for a client-side web application, so making the solution apply to Javascript would be helpful!

推荐答案

起初，我试图接近这是一个排序问题。但我认为这是更好地把它看成一个优化问题。让我尝试到正式确定问题。鉴于：

At first, I tried to approach this as a sorting problem. But I think it is better to think of it as an optimization problem. Let me try to formalize the problem. Given:

• 是W <子>我：重棒的我的
• →<子>我：棒的长度的我的
• M <子>我：杆的最大距离的我的从原产地。如果没有限制，你可以设置这个值来总结（I = 1，N，L <子>我）

• w_i: weight of rod i
• l_i: length of rod i
• m_i: maximum distance of rod i from origin. If there is no constraint, you can set this value to sum(i=1,n, l_i)

的问题是要找到一个置换一个<子>我，使得该成本函数：

The problem is to find a permutation a_i, such that the cost function:

J = SUM（I = 1，N，W <子>一<子>我 *总和（J = 1，I-1，L <子>一<子>Ĵ ））

J=sum(i=1,n, w_ai*sum(j=1,i-1, l_aj))

被最小化，限制

总和（J = 1，I-1，L <子>一<子>Ĵ ）＆LT; = M <子>我 1＆LT; = I＆LT; ñ

sum(j=1,i-1, l_aj) <= m_i, 1 <= i<n

是满意的。

我不知道这是一个正确的提法，虽然。没有任何限制，最优的解决方案是不总是杆排序（重量）。例如，让升= {1,4}，以及w = {1,3}。如果一个= {1,2}，则J是1 * 0 + 3 * 1 = 3，并且如果= {2,1}（依重量计），J是3 * 0 + 1 * 4 = 4。显然，未分类的解决方案最小化成本函数，但我不知道这是你想要的。

I am not sure this is a correct formulation, though. Without any constraints, the optimal solution is not always the rods sorted by weight. For example, let l={1,4}, and w={1,3}. If a={1,2}, then J is 1*0+3*1=3, and if a={2,1} (sorted by weight), J is 3*0+1*4=4. Clearly, the unsorted solution minimizes the cost function, but I am not sure this is what you want.

另外，我不知道如何解决这个问题呢。你可以尝试一些在短期内启发式搜索。我写这改写，以便其他人可以提供一个解决方案，同时，我认为更多的解决方案。如果它是正确的，当然。

Also, I don't know how to solve the problem yet. You could try a heuristic search of some kind in the short term. I am writing this reformulation so that someone else can provide a solution while I think more about the solution. If it is correct, of course.

另外要注意的是，你没有找到完整的解决方案，看看是否有一个解决方案。可以忽略不位置限制杆，并尝试解决这个问题，只有在约束杆。如果有一个解决办法，则问题确实有一个溶液（一个明显的次优解决方案是将无约束杆进行排序，并将其追加到降低问题的解决）。

Another thing to note is that you don't have to find the complete solution to see if there is a solution. You can ignore the rods without position constraints, and try to solve the problem with only the constrained rods. If there is a solution to this, then the problem does have a solution (an obvious suboptimal solution is to sort the unconstrained rods, and append them to the solution of the reduced problem).

在说这一切，我想下面的算法会做的伎俩。我会形容它一点视觉上，使之更容易理解。我们的想法是把棒上的线段由左到右（原点是线段的最左边的点），按您的问题描述。

After saying all this, I think the algorithm below would do the trick. I will describe it a bit visually to make it easier to understand. The idea is to place rods on a line segment from left to right (origin is the leftmost point of the line segment) as per your problem description.

1. 分离出棒与他们位置的限制。然后，把它们放置，使得它们在它们的位置的限制的限制。
2. 如果没有重叠棒，转到第4步
3. 对于每个重叠对杆，移动所述一个更接近原点朝向原点，使得它们不再重叠。这个步骤可能需要其他的棒就行了要转向的起源开辟一些空间。您可以通过检查检测到这一点，如果移动的棒现在一个只是为了它的左边重叠。如果你不能创造足够的空间（移动最接近杆原点0仍然无法腾出足够的空间），那么就没有解决问题的办法。在这里，你有机会找到放宽对原有重叠对的最右边杆约束的解决方案：只要把它移离原点，直到有没有重叠（您可能需要按preceding棒右，直到所有重叠在这之前是固定的）。
4. 现在，我们有一些棒的人选，而他们周围的一些自由空间。开始填补的自由空间，其中的最高杆（包括那些与约束它们的自由空间的右侧），将适合于它。如果你不能找到一个能适合任何棒，只是转移在空间右侧的下一杆，以缩小差距。
5. 在重复步骤4，直到达到最右边的约束杆。剩下的线段是完全自由的空间。
6. 排序的所有遗留杆重量，并将它们放置在剩余的可用空间。

关于算法的几个注意事项：

A few notes about the algorithm:

• 它并没有解决我刚才所说的问题。它试图仅根据权重棒进行排序。

• It doesn't solve the problem I stated earlier. It tries to sort the rods according to their weights only.

我觉得有一些失去的机会做的更好，因为我们滑一些棒对产地来源，使他们所有的拟合（步骤3），有时从这些挤在地方挑重棒，并把它们更接近原点（在步骤4）。这将释放一定的空间，但我们不滑动推开杆回到自己的约束位置的限制。它可能会要做到这一点，但我将不得不修改算法时，我的大脑更好地工作。

I think there are some lost opportunities to do better, because we slide some rods towards the origin to make them all fit (in step 3), and sometimes pick the heavy rods from these "squeezed in" places, and put them closer to origin (in step 4). This frees up some room, but we don't slide the pushed away rods back to the limits of their constrained positions. It may be possible to do this, but I will have to revise the algorithm when my brain is working better.

这不是一个非常有效的算法。我有一种感觉，它可以在O完成（N ^ 2），但更好的东西，需要创造性的数据结构。你需要能够找到的最重的杆比一个给定的长度L小于速度比为O（n）做的更好。

It is not a terribly efficient algorithm. I have a feeling that it can be done in O(n^2), but anything better would require creative data structures. You need to be able to find the heaviest rod with length less than a given L faster than O(n) to do better.

这篇关于算法的问题：包装棒成一排的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！