ASP Competition 2011: ProblemsDescription/WeightAssignmentTree

Weight-Assignment Tree

Problem Description

Problem is concerned with a full-binary tree such that

  1. its leaves are pairs (weight,cardinality), where weight and cardinality are integers
  2. the right child of an inner node is a leaf,
  3. each inner node is a pair (color,weight), where color is either green, red, or blue.

Condition (2) 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.

In the problem, the weights and cardinality values of n leaves and the colors of all inner nodes are given. 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):

Total weight of a tree is the sum of the weights of its inner nodes.

The problem is: given a tree T, with all weight and cardinalities assigned to leaves, and colors specified for the internal nodes, verify if there is a tree T' with the same set of leaves as T satisfying conditions (1)-(3) whose total weight is less than a total weight of T. The leaves in the tree T' may be arranged differently than in the tree T, and the colors of the internal nodes may be different.

Input format

An input consists of the following parts:

a. n leaves are given with corresponding weight and cardinality (there are 1..n leaves): leafWeightCardinality(leaf1,w1,c1). ... leafWeightCardinality(leafn,wn,cn). where w1..wn, c1..cn are integers.

b. for each inner node (there are 1..n-1 inner nodes), its assigned color is specified: innerNodeColor(1,color1) ... innerNodeColor(n-1,color_n-1) where color1..color_n-1 is one of the three colors {green, red, blue}

c. tree structure of T is given by predicates innerLeftRight(1,leafL_id_1, leafR_id_1). .. innerLeftRight(n-1,leafL_id_n-1, leafR_id_n-1). where leafL_id_1, leafR_id_1... are ids of leaves 1..n.

Output format

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 innerNodeColorPrime(1,color1) ... innerNodeColorPrime(n-1,color_n-1) innerLeftRightPrime(1,leafL_id_1, leafR_id_1). .. innerLeftRightPrime(n-1,leafL_id_n-1, leafR_id_n-1).

Otherwise, no answer set is returned.

Example

Given:

leafWeightCardinality(leaf1,4,5). leafWeightCardinality(leaf2,3,7). innerNodeColor(1,green). innerLeftRight(1,leaf1,leaf2).

Output contains: exists innerNodeColorPrime(1,red). innerLeftRightPrime(1,leaf2,leaf1).

Explanation: Total weight of the tree in the example is 10

Total weight of the tree in the output is 7.

Author(s)

ASP Competition 2011: ProblemsDescription/WeightAssignmentTree (last edited 2011-01-10 10:25:55 by CarmenSantoro)