I am trying to find an algorithm, which can find the minimal total weight of a given tree.
I am given a tree and a weight of all nodes (each node can have a different weight). For example in this graph, where each node has weight 1: tree with weights
Then I am given a set of at least two numbers, let's call them X. For example X: 2, 3, 4, 5. Each node is assigned one X value, while no two adjacent nodes can have the same X value. In result, each node has a total weight of X * weight. After adding total weight of all nodes, we get the total weight of the tree. tree result
The goal is to find an algorithm, which can find one such distribution of X values, so that we get a minimal weight of the tree.
Any help would be appreciated.
You can use a bottom up approach (through recursion), where for each node you calculate the minimal total weight of the subtree rooted in that node, for each choice of factor (from X) for that node.
So if X has 10 factors, each node will get 10 calculated weights, each one corresponding to a choice of factor.
As you go up one level from a node to its parent, you collect the same information. When looking at one particular child of that parent, take the two minimal weights calculated for that child (from the 10). Let's say they are for factor i and factor j respectively. Then if you make the calculation of the total weight for the parent for factor i, you must take into account the child's weight that corresponds to factor j. In all other cases you can take the one that corresponds to factor i.
Here is the idea expressed in 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.This algorithm thus has a time complexity of O(nm), where n is the number of nodes, and m = |X|.
When the maximum branching factor b is known, then you can clip X to the b+2 smallest of them (so m = b+2). At any rate X can be clipped to the n smallest values.
The above algorithm can be extended to get an optimal distribution of the X factors. For that the minimal weights (per factor, per node) should be stored for each node. Then a new DFS traversal should find the index having the minimum weight, and assign the corresponding X factor to the node. In recursion that index should be excluded from being assigned to the direct children.
Here is the same code with that extension:
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()));