假设我有以下内容：
A 2
B 2
C 2
D 6
E 12
F 3
G 3
我希望有一个函数，输入所需的群组数量，并根据数量/权重创建“cluster”（聚类）。例如，如果所需的群组数量是4，则可以返回以下内容：
(A, B, C), (D), (F, G), (E)
A+B+C = 6
D = 6
F + G = 6
E = 12
是否有一些算法/函数可以让我得到这样的结果？是否有某种理想的方法？
基于节点权重进行聚类的算法/函数是什么？
3
- Rolando
3
请看一下K-means。 - JerryM
不清楚您的需求。您是想将所有权重相同的节点收集到单独的群集中吗？如果群集数量与唯一权重的数量不同怎么办？还是说您希望群集的聚合权重相同？（那么您示例中的 E 不是一个好的群集。） - DYZ
尽可能地使聚类的权重总和相同。 - Rolando
2个回答
0
首先，过滤掉大于6的任何值。但这里有一个问题。
因为你需要将组内所有操作数的结果相加得到6，所以无法从具有有限操作数的小集合中获得任意数量的组。你可以在组内产生不同的操作数组合，但这要求组内所有操作数的加法结果都为6。除非是你的示例中操作数大于或等于6的情况，这些操作数形成了它们自己的组（例如E和D）。
就像你有两个2，一个3和只有一个1，你可以通过使用每个组内唯一的操作数，在不同的组合中使用这些数字来得到多少个7？
A = 2
B = 2
C = 3
D = 1
A = 2
B = 2
C = 3
D = 1
以上的操作数 < 7
让我们对这些操作数进行排列组合：
A + B = 4
A + C = 3
A + D = 3
A + B + C = 7
A + B + D = 5
A + C + D = 6
B + C = 5
B + D = 3
B + C + D = 6
C + D = 4
答案只有一组，当我们把它的所有操作数加起来得到7时。这个组由三个操作数组成A + B + C。
这是您所需算法中的情况。尽管有时候您可以获得任意数量的组，但即使使用其他组中已使用的操作数，这也并不总是保证的，就像上面的例子一样，只有恰好一个组，当我们将其所有操作数相加时，得到7。
另外，加法是可交换的（A + B = B + A），所以我没有包括 B + A, C + B, D + C等。
因此，您可以获得仅基于上述集合只能得到一组，当我们把它的所有操作数加起来得到7. 问题不仅在于一组内的操作数的唯一性；也在于我们有限的值集的本质，防止我们获得任意数量的组。
- GIZ
0
这似乎是根据作业权重均匀分组以分配到n个线程中。
对于少量的作业，组合数学可能是一种方法，但如果您有成千上万的作业需要分组并分布在数百个线程上，那么组合数学肯定不可行。
因此，我的方法是一个更简单但是两阶段的解决方案。第一阶段返回几乎完美的结果，第二阶段试图将其完善。
由于时间有限，我现在只实现第一阶段，并将第二阶段留给接下来的几天。同时，请将其视为一项研究，并尝试自己实现它。
第一阶段的想法非常简单。
- 按降序排序作业（因此重型作业首先插入，轻型作业用于平衡）
- 找到最轻的块。
- 将第一个作业插入到找到的块中。
- 找到最轻的块。
- 将下一个作业插入到找到的块中，并继续执行步骤4。
这就是我实现的方式;
function chunkJobs(js,cc){ // jobs and chunk count as arguments
var init = [...Array(cc)].map(_ => ({"jobs": [], "weight": 0}));
return js.sort((a,b) => b.weight - a.weight)
.reduce(function (cs,j){
var c = cs.reduce((p,c) => p.weight < c.weight ? p : c);
c.jobs.push(j.id);
c.weight += j.weight;
return cs;
}, init);
}
var jobs = [{id: "A", weight: 2},
{id: "B", weight: 2},
{id: "C", weight: 2},
{id: "D", weight: 6},
{id: "F", weight: 3},
{id: "G", weight: 3}],
result = chunkJobs(jobs,3);
console.log(result)所以你看到的输出是
[ { jobs: [ 'G', 'B' ], weight: 5 },
{ jobs: [ 'F', 'A', 'C' ], weight: 7 },
{ jobs: [ 'D' ], weight: 6 } ]
正如我之前提到的，尽管这可能不是大量工作的理想解决方案，但它非常接近理想。例如，让我们将数据更改为具有97个作业，每个作业的随机权重选择在0-20之间，并添加3个非常重的作业{"id": 98, "weight": 113},{"id": 99, "weight": 63},{"id": 100, "weight": 91}
function chunkJobs(js,cc){ // jobs and chunk count as arguments
var init = [...Array(cc)].map(_ => ({"jobs": [], "weight": 0}));
return js.sort((a,b) => b.weight - a.weight)
.reduce(function (cs,j){
var c = cs.reduce((p,c) => p.weight < c.weight ? p : c);
c.jobs.push(j.id);
c.weight += j.weight;
return cs;
}, init);
}
var jobs = [...Array(97)].map((_,i) => ({"id": i+1, "weight": ~~(Math.random()*20)})).concat({"id": 98, "weight": 113},{"id": 99, "weight": 63},{"id": 100, "weight": 91});
result = chunkJobs(jobs,16);
console.log(result);类似这样的东西
[ { jobs: [ 50, 91, 40, 33, 75, 41, 32 ], weight: 67 },
{ jobs: [ 70, 1, 20, 19, 30, 93, 97 ], weight: 67 },
{ jobs: [ 59, 8, 64, 29, 78, 13, 68 ], weight: 67 },
{ jobs: [ 17, 66, 65, 2, 73, 67, 14 ], weight: 67 },
{ jobs: [ 60, 43, 11, 84, 45, 35, 56 ], weight: 67 },
{ jobs: [ 90, 77, 21, 18, 9, 34, 37 ], weight: 67 },
{ jobs: [ 52, 5, 42, 69, 86, 72, 46 ], weight: 68 },
{ jobs: [ 95, 85, 54, 48, 38, 61, 88 ], weight: 68 },
{ jobs: [ 79, 82, 92, 31, 74, 25, 15 ], weight: 68 },
{ jobs: [ 87, 44, 58, 47, 51, 4 ], weight: 67 },
{ jobs: [ 26, 22, 49, 10, 39, 27, 7, 96, 71, 89, 55, 23 ], weight: 67 },
{ jobs: [ 6, 83, 28, 53, 63, 81, 36 ], weight: 68 },
{ jobs: [ 76, 62, 12, 24, 94, 80, 57 ], weight: 68 },
{ jobs: [ 99, 3, 16 ], weight: 69 },
{ jobs: [ 100 ], weight: 91 },
{ jobs: [ 98 ], weight: 113 } ]
然而，我们不会满足于此，将继续在第二阶段中完善结果。关于第二阶段的提示是...我认为对于单个作业解决的线程（如上面示例中的最后两个），我们无法做任何事情，但对于其余部分，一种基于线程权重差异交换作业的动态规划方法可能是一个不错的起点。
- Redu
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接