Weight-Assignment Tree
Contents
Problem Description
Weight-Assignment Tree problem is inspired by cost-based "join-order" optimization of SQL queries problem in databases. It is concerned with a full-binary tree with n leaves such that
- its leaves are pairs (weight,cardinality), where weight and cardinality are integers ii. the right child of an inner node is a leaf, iii. each inner node is a pair (color,weight), where color is either green, red, or blue. iv. there are 1 .. n-1 inner nodes such that node "n-1" is a root node and inner node "i-1" is the left child of inner node "i" for i=2..n-1 .
Condition (ii) implies that the trees of interest are paths going to the left with each node on the path having the right child being a leaf of the tree. The weights of inner nodes are computed recursively (or to put it differently, are subject to constraints) based on their colors, weights and the cardinalities of their children. Specifically, the weight of an inner node X satisfies the formulas (constraint): if color of X is green weight(X) = weight(right child of X) + cardinality(right child of X) if color of X is red weight(X) = weight(right child of X) + weight(left child of X) if color(X) is blue weight(X) = cardinality(right child of X) + weight(left child of X) Total weight of a tree is the sum of the weights of its inner nodes. The problem is: Given
Input: leafWeightCardinality/3, num/1, max_total_weight/1, innerNode/1 Output: exists/0, leafWeightCardinality/3, innerNodeColor/2, innerLeftRight/3, num/1, max_total_weight/1
An input consists of the following parts: b. The number of leaves in the tree is given by num(n). c. Integer mv is given by max_total_weight(mv). d. n-1 inner nodes are given:
A solution is represented by means of a constant "exists" if there is a tree T and a specification of T in the following format Otherwise, no answer set is returned.
Given: Output contains: Explanation: Total weight of the tree in the output is 7.
Predicates
Input format
leafWeightCardinality(leaf1,w1,c1).
...
leafWeightCardinality(leafn,wn,cn).
where w1..wn, c1..cn are integers.
innerNode(1).
...
innerNode(n-1).
Output format
innerNodeColor(1,color1)
...
innerNodeColor(n-1,color_n-1)
innerLeftRight(1,leafL_id_1, leafR_id_1).
..
innerLeftRight(n-1,n-2, leafR_id_n-1).
leafWeightCardinality/3. %as in input instance
...
max_total_weight/1. %as in input instance
num/1. %as in input instance
Example(s)
leafWeightCardinality(leaf1,4,5).
leafWeightCardinality(leaf2,3,7).
innerNode(1).
num(2).
max_total_weight(9).
exists.
leafWeightCardinality(leaf1,4,5).
leafWeightCardinality(leaf2,3,7).
innerNodeColor(1,red).
innerLeftRight(1,leaf2,leaf1).
max_total_weight(9).
num(2).
Author(s)