自动皮带宽度算法
我非常感谢有关这个实际问题的一些评论。
快速描述。 我有可变数量的链接，可用于组成给定的皮带宽度。问题是，每个链接有多少个。 选择标准：最好使用较长的物品。
示例。 假设我们想要创建一个带宽， W = 1024.0 其中一种型号具有以下链接长度： L = [34.0, 65.0, 96.0, 126.0]
问题是，每个链接要制作多少个宽度。
这是我尝试过的一些方法。
1.贪婪（选择最长的第一个以满足条件） c = [0,0,0,8] 其中 c 是每个项目的计数。 这留下了 16.0 的间隙，我什至无法容纳一件最小的物品。 贪婪很容易，但不好。
2.选择循环 不太容易，我认为这是一个难题。 我尝试了很多策略：填充小物品，然后依次删除它们以适应下一个尺寸。
3.背包法 不太合适，因为这是基于给定数量的项目。
4.子集和问题 这是背包的子类，但我无法让它工作。
5.装箱问题 听起来很相似，但我无法将其应用于我的问题。
6.暴力破解（随机选择） 奇怪的是，这个找到了很多完全匹配的内容。 我使用计数的简单多项式作为评级。 评级 = n[0] + n[1]*2 + n[2]*3 + n[4]**4 + ... 暴力解决方案之一是 [4, 0, 4, 4] 正好给出 1024。 问题是，这种方法经常会出现不同的选择，因此并不理想。
7.详尽的搜索 不实用，因为选择太多。
8.模拟退火 从暴力破解的成功来看，这看起来是一个不错的选择。 有人能给我举一个简单的例子吗（请不要是另一个旅行推销员）。
9.遗传与粒子群 不确定这些。
现在，我陷入困境和沮丧。 有没有直接的算法可以解决这个问题？
I would really appreciate some comments about this practical problem.
Quick description.
I have a variable number of links that can be used to make up a given belt width. The question is, how many of each link.
Selection criteria: it is better to use longer items.
Example.
Let's say we want to create a belt width,
W = 1024.0
One of the models has the following link lengths:
L = [34.0, 65.0, 96.0, 126.0]
The question is, how many of each link to make the width.
Here is a few approaches I have tried.
1. Greedy (select longest 1st to satisfy criteria)
c = [0,0,0,8]
where c is the count of each item.
This leaves a gap of 16.0 and I can't fit even 1 of the smallest items.
Greedy is easy but not good.
2. Selection loop
Not too easy, I think that this is a difficult problem.
I have tried many strategies: filling with small items then removing them sequentially to fit the next size up.
3. Knapsack method
Not really appropriate because this is based on a given number of items.
4. Subset sum problem
This is a sub-class of Knapsack but I have not been able to get it working.
5. Bin Packing problem
It sounds similar but I couldn't get it to apply to my problem.
6. Brute force (random selection)
Strangely, this one finds many exact matches.
I use a simple polynomial of the count as a rating.
rating = n[0] + n[1]*2 + n[2]*3 + n[4]**4 + ...
One of the solutions from brute force is
[4, 0, 4, 4] giving exactly 1024.
The problem is, this method often comes up with a different selection so it is not ideal.
7. Exhaustive search
Not practical because there are too many choices.
8. Simulated Annealing
From the success of brute force, this looks like a good alternative.
Can someone point me to a simple example (please not another traveling salesman).
9. Genetic and particle swarm
Not sure about these.
Now, I am stuck and frustrated.
Is there a direct algorithm that can be used for this problem?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
好吧，如果我正确理解这个问题，你需要选择x1个长度为34的对象，x2个长度为65的对象，等等，这样所有这些对象的总和等于W，但是有一个偏向较长的对象（在本例中，126.0 将是最受欢迎的对象）。
我想你可以创建一个像这样的目标函数：
f(x1,x2,..,xn) = b1*x1*L1 + b2*x2*L2 + ... + bn*xn*Ln - p*( W - x1*L1 + x2*L2 + ... + xn*Ln)^2
其中 b1 到 bn 是对这些对象的偏见（正数表示有利，负数表示该对象不受欢迎）， L1 到 Ln 是这些对象的长度，p 是对不完全是 W 的惩罚（如果它必须完全是 W，p 就是 inf。）
（我们也可以将其表示为矩阵形式 f(X) = b^ T*X*L - p*(W - I^T*X*L)^2，其中 b 和 L 是向量，X 是 x1, x2, ..., xn 的方对角稀疏矩阵 I 是向量1 的个数，T 是转置。）
因此，目标通过搜索整数 x1、x2、...、xn 的 n 元组集来最大化 f。
哇好的，现在我想我明白了这个问题。 :)
这是某种整数规划问题，但我不认为它完全符合二次整数规划问题。也许其他人知道那是什么。
我在研究中对模拟退火进行了大量的研究和实验。它通常可以轻松解决这些类型的离散优化问题。您可能可以仅使用线性或对数温度表来解决此问题。
如果你只有几个对象，而不打算大规模扩展，那么蛮力可能就可以了。但是，如果您要对数百或数千个对象执行此操作，那么遗传算法、粒子群或模拟退火可能是明智的想法。据我所知，实际上不可能先验地知道哪种优化启发式效果最好（例如，在令人满意的时间范围内找到所需精度的结果）。
我对其他解决方法了解不够，无法提供评论。
Alright, if I understand the problem correctly, you need to choose x1 objects of length 34, x2 objects of length 65, etc., etc., such that the sum of all these objects is equal to W, but there is a bias towards the longer objects (in this case, 126.0 would be the most favored object).
I suppose you could make an objective function that is like this:
f(x1,x2,..,xn) = b1*x1*L1 + b2*x2*L2 + ... + bn*xn*Ln - p*(W - x1*L1 + x2*L2 + ... + xn*Ln)^2
Where b1 thru bn are biases on those objects (positive numbers are favorable, negative numbers mean the object is disfavored), L1 thru Ln are the lengths of those objects, and p is a penalty for not being exactly W (if it must be exactly W, p is inf.)
(We could also put it in matrix form as f(X) = b^T*X*L - p*(W - I^T*X*L)^2, where b and L are vectors, X is a square diagonal sparse matrix of x1, x2, ..., xn I is a vector of 1's, and T is transposition.)
So the objective then it maximize f by searching over the n-tuple set of integers x1, x2, ..., xn.
whew Ok, now I think I understand the problem. :)
This is an integer programming problem of some sort, but I don't think it exactly qualifies as a quadratic-integer programming problem. Perhaps someone else knows what it is.
I've been studying and experimenting with simulated annealing a lot in my research. It usually can solve these types of discrete optimization problems easily. You can probably just use a linear or logarithmic temperature schedule for this problem.
If you only have a few objects though, with no intent on wide-scaling, then brute force would probably be fine. But if you are going to be doing this on hundreds or thousands of objects, then genetic algorithm, particle-swarm, or simulated annealing would probably be smart ideas. To the best of my knowledge, it is not really possible to know which optimization heuristic will work the best (e.g. find the result of desired accuracy in a satisfactory time frame) a priori.
I do not know enough about the other solution methods to provide comment.