您可以使用自下而上的方法（通过递归），对于每个节点，您计算以该节点为根的子树的最小总权重，对于该节点的每个因子选择（来自X）。
所以如果X有 10 个因子，每个节点将得到 10 个计算权重，每个权重对应一个因子的选择。
当您从一个节点上升到其父节点的一层时，您会收集相同的信息。在查看该父母的一个特定孩子时，取为该孩子计算的两个最小权重（从 10 个）。假设它们分别用于因子i和因子j。然后，如果您计算因子i的父母的总重量，则必须考虑与因子j对应的孩子的体重。在所有其他情况下，您可以采用与因子i对应的那个。
这是用 JavaScript 表达的想法：
class Node {
constructor(weight, ...children) {
this.weight = weight;
this.children = children;
}
getMinWeights(factors) {
// Get the node's own weight for each choice of factor:
let weights = [];
for (let i = 0; i < factors.length; i++) {
weights[i] += factors[i] * this.weight);
}
// For each child of this node:
for (let child of this.children) {
// Get the min weight corresponding to each factor-choice
// made for the child node
let childWeights = child.getMinWeights(factors);
// Get positions (i.e. factor indices) of the 2 smallest results
let minIndex1 = 0;
for (let i = 1; i < childWeights.length; i++) {
if (childWeights[i] < childWeights[minIndex1]) {
minIndex1 = i;
}
}
let minIndex2 = minIndex1 > 0 ? 0 : 1;
for (let i = 0; i < childWeights.length; i++) {
if (i !== minIndex1 && childWeights[i] < childWeights[minIndex2]) {
minIndex2 = i;
}
}
// For each factor choice in this node, determine the best choice
// of factor in the child, and add the corresponding weight
// to the total weight for this node's subtree.
for (let i = 0; i < childWeights.length; i++) {
weights[i] += childWeights[i === minIndex1 ? minIndex2 : minIndex1];
}
}
return weights;
}
}
// Example:
let tree = new Node(1,
new Node(1), new Node(1), new Node(1,
new Node(1), new Node(1), new Node(1)
)
);
let result = tree.getMinWeights([2, 3, 4, 5]);
console.log(Math.min(...result)); // Return the minimum of the values we got back.因此，该算法的时间复杂度为O(nm)，其中n是节点数，m = |X| .
当最大分支因子b已知时，您可以将X剪辑为b+2中最小的一个（因此m = b+2）。无论如何， X可以被裁剪为n 个最小值。
可以扩展上述算法以获得X因子的最佳分布。为此，应为每个节点存储最小权重（每个因子，每个节点）。然后一个新的 DFS 遍历应该找到具有最小权重的索引，并将相应的 X 因子分配给节点。在递归中，该索引应该被排除在分配给直接子代的范围之外。
这是与该扩展相同的代码：
class Node {
constructor(weight, ...children) {
this.weight = weight;
this.children = children;
}
getMinWeights(factors) {
// Get the node's own weight for each choice of factor:
let weights = [];
for (let i = 0; i < factors.length; i++) {
weights[i] += factors[i] * this.weight;
}
// For each child of this node:
for (let child of this.children) {
// Get the min weight corresponding to each factor-choice
// made for the child node
let childWeights = child.getMinWeights(factors);
// Get positions (i.e. factor indices) of the 2 smallest results
let minIndex1 = 0;
for (let i = 1; i < childWeights.length; i++) {
if (childWeights[i] < childWeights[minIndex1]) {
minIndex1 = i;
}
}
let minIndex2 = minIndex1 > 0 ? 0 : 1;
for (let i = 0; i < childWeights.length; i++) {
if (i !== minIndex1 && childWeights[i] < childWeights[minIndex2]) {
minIndex2 = i;
}
}
// For each factor choice in this node, determine the best choice
// of factor in the child, and add the corresponding weight
// to the total weight for this node's subtree.
for (let i = 0; i < childWeights.length; i++) {
weights[i] += childWeights[i === minIndex1 ? minIndex2 : minIndex1];
}
}
// Extra: store the weights with the node
this.weights = weights;
return weights;
}
// Extra: method to distribute the X-factors to each node. Must run after method above.
assignFactors(factors, excludeIndex=-1) {
if (excludeIndex === -1) this.getMinWeights(factors); // First do this...
// Get the index of the factor that results in the minimal weight
let minIndex = excludeIndex === 0 ? 1 : 0;
for (let i = 1; i < this.weights.length; i++) {
if (i !== excludeIndex && this.weights[i] < this.weights[minIndex]) {
minIndex = i;
}
}
// Assign the corresponding factor to this node
this.factor = factors[minIndex];
// For each child of this node:
for (let child of this.children) {
// recurse, and pass the chosen factor index, so it will not be used
// for the child:
child.assignFactors(factors, minIndex);
}
}
toArray() {
return this.children.length ? [this.factor, this.children.map(child => child.toArray())] : this.factor;
}
}
// Example:
let tree = new Node(1,
new Node(1), new Node(1), new Node(1,
new Node(1), new Node(1), new Node(1)
)
);
tree.assignFactors([2, 3, 4, 5]);
console.log(JSON.stringify(tree.toArray()));