Re: dynamic programming on a tree

On Sun, 29 Jan 2006 11:39:34 -0800, tenida@xxxxxxxxx wrote:
> I have a binary tree. ...
> Each leaf L also has a number associated with it, A(L). In addition user
> inputs an interval [a,b].
>
> Now, I have to assign weights w_i (positive reals) to all nodes
> including leafs such that product of weights from root to a leaf j equals
> A(j).
>
> But, I want to assign weights such that the total number of weights
> that are outside a specified interval [a,b] is minimized. ...

You might try memoizing the number of allowed out-of-interval (OOI)
weights for each node, and the interval of weights that would achieve it.
If the allowed interval is [2,5] and your tree is
root
/ \
20 40
at the node marked 20, for 0 (zero) OOI weights the root could be in the
interval [4,10] (with 4 the weight could be 5 and with 10 the weight
could be 2). At the node marked 40, for 0 OOI weights the root could be
in the interval [8,20]. At the root 0 OOI weights can be satisfied with
anything in [8,10].

Start with 0 (zero) OOI weights at the root. Recrusively propagate the
number of allowed OOI weights down, and the satisfying weight internals
up. If there is no solution at a node, pass back "failure" and the
caller must increase the OOI weight allowance. If at the root, increment
the OOI weights allowance.

-paul-
--
Paul E. Black (p.black@xxxxxxx)

.

Relevant Pages

  • dynamic programming on a tree
    ... I have a binary tree. ... So there is a unique path from root to each ... Each leaf L also has a number associated with it, ... I have to assign weights w_i to all nodes ...
    (comp.theory)
  • Re: MLE
    ... ranges maximise the expression: typically you will find the maximum ... the quotient of the sum of all weights of all samples that fall in the ... leaf, divided by the volume of the leaf. ...
    (sci.stat.math)
  • Re: Seperate MDX Aggregation formulas for non-leaf members of a dimension
    ... Unary operators are supported in AS 2000, but since weights can't be ... The leaf values themselves should appear unmodified to end-users. ... Deepak Puri ...
    (microsoft.public.sqlserver.olap)
  • Re: Metal weights around plants - toxic?
    ... Java ferns eventually root if you tie the plant to a rock or piece of driftwood using thread. ... I found a package of weights that aren't lead, ... I discard weights that could be made of lead, since it dissolves into water under acidic conditions. ...
    (rec.aquaria.freshwater.plants)