查找树的最小权重

Question

我正在尝试找到一种算法，该算法可以找到给定树的最小总权重。

我得到一棵树和所有节点的权重（每个节点可以具有不同的权重）。例如，在此图中，每个节点的权重为1：tree with weights

然后给了我至少两个数字的集合，我们称它们为X。例如X：2、3、4、5。每个节点被分配一个X值，而两个相邻节点不能具有相同的X值。结果，每个节点的总权重为X *权重。在添加所有节点的总权重之后，我们得到了树的总权重。tree result

目标是找到一种算法，该算法可以找到一种这样的X值分布，以便使树的权重最小。

任何帮助将不胜感激。

Answer 1

您可以使用自下而上的方法（通过递归），其中对于每个节点，针对该节点的每种因子选择（来自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的分布

可以扩展上述算法以获得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()));