这是一个关于IT技术的翻译问题。以下是需要翻译的内容:
一个函数会为范围内所有节点创建幂集,并为每个组合分配一个数字分数。负分将被移除,结果形成以下数组
最佳解决方案,最大化分数,应该是:
这是对于之前问题Finding max value of a weighted subset sum of a power set的跟进问题。 虽然之前的问题可以在合理的时间内解决规模小于等于15的问题(达到最优解),但我想解决规模约为2000的问题,接近最优解。
作为一个小例子,我会给出一定范围内的节点:
var range = [0,1,2,3,4];
一个函数会为范围内所有节点创建幂集,并为每个组合分配一个数字分数。负分将被移除,结果形成以下数组
S
。S[n][0]
是所有包含节点的按位OR运算,S[n][1]
是得分:var S = [
[1,0], //0
[2,0], //1
[4,0], //2
[8,0], //3
[16,0], //4
[3,50], //0-1
[5,100], //0-2
[6,75], //1-2
[20,130], //2-4
[7,179] //0-1-2 e.g. combining 0-1-2 has a key of 7 (bitwise `1|2|4`) and a score of 179.
];
最佳解决方案,最大化分数,应该是:
var solution = [[8,3,20],180]
其中solution[0]
是由S
中的组合数组,solution[1]
是得分结果。请注意,按位8 & 3 & 20 == 0
,表示每个节点仅使用一次。
问题具体描述:每个节点必须恰好使用一次,单节点组合的得分始终为0,如上面的S
数组所示。
我的当前解决方案(在这里查看)使用动态规划,并适用于小问题。我已经看到了涉及动态规划的启发式方法,例如https://youtu.be/ze1Xa28h_Ns,但无法弄清如何将其应用于多维问题。鉴于问题约束条件,应用什么样的合理启发式方法?
编辑: 我尝试过的事情
- 贪心方法(将
score
从大到小排序,选择下一个可行的候选项) - 与上述相同,但按
score/cardinality(combo)
排序 - GRASP(将每个
score
编辑高达10%,然后排序,在x秒内重复,直到找到更好的解决方案为止)