⇤ ← Revision 1 as of 2011-01-24 11:56:08
3419
Comment:
|
3425
|
Deletions are marked like this. | Additions are marked like this. |
Line 9: | Line 9: |
Line 10: | Line 11: |
Line 11: | Line 13: |
Line 13: | Line 16: |
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. | 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. |
Line 30: | Line 33: |
b. an integer mv, verify if there is a tree T with these n leaves satisfying conditions (i)-(iv) whose total weight is less or equal to mv. | b. an integer mv, verify if there is a tree T with these n leaves satisfying conditions "i"-"iv" whose total weight is less or equal to mv. |
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)