找到一棵树的最小重量

Question

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

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

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

我们的目标是找到一种算法，它可以找到一个这样的 X 值分布，以便我们得到最小权重的树。

如有任何帮助，我们将不胜感激。

Answer 1

您可以使用自下而上的方法（通过递归），对于每个节点，您计算以该节点为根的子树的最小总权重，对于每个因子选择（来自 X) 对于那个节点。

所以如果X有10个因素，每个节点将得到10个计算权重，每个权重对应一个因素选择。

当你从一个节点上升到它的 parent 一级时，你会收集相同的信息。当查看 parent 中的一个特定 child 时，取为 child 计算的两个最小权重（从 10）。假设它们分别用于因子 i 和因子 j。那么如果你计算 parent 对因子 i 的总权重，你必须考虑 child 对应于因子 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因子分配给该节点。在递归中，应该排除索引被分配给直接 children.

这是具有该扩展名的相同代码：

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()));

找到一棵树的最小重量

Find minimal weight of a tree

algorithm

tree

weighted

graph-algorithm

weighted-graph

得到X的分布