1
$\begingroup$

Given

  • a unbalanced k-ary tree base (with internal nodes that represent operators and leafs representing values) from the space of all unbalanced k-ary trees T
  • a distance function delta(t, t') = number of edit operations to transform t into t'
  • the edit operations add(t) (adding a random leaf), remove(t) (removing a random subtree), relabel(t) (relabel a random node) merge(t, t') (merge t and t')
For a genetic algorithm I need to generate a population of n trees that are not more than k edit operations away from base. I must prove that any tree within this space has equal propablity to be generated and that any tree can be generated.

The only idea I can think of was:

  1. draw a random number l within [0, k]

  2. define a random sequence seq of size l edit operations

  3. apply seq to base

This aproach though does not garanty that any tree less than k away from base is generated?!

//EDIT

My other approach:

  1. Generate a random tree rt

  2. Measure distance d and calculate seq the optimal set of edit operations beween rt and base

  3. apply [k-d, d] edit operations to rt

I am not shure if in that way any tree can be generated with the same propability.

$\endgroup$
  • $\begingroup$ Welcome to CS.SE! It suffices to ask how to generate a single tree with the right distribution. If you can do that, you can repeat the procedure $n$ times. However, sampling with exactly that distribution looks like it might be challenging. Your methods don't yield a uniform distribution on trees. I imagine you could read about MCMC methods, but I don't know if they'll be applicable here. Would you be OK with a sampler that has approximately the right distribution, even if it's not exactly right? (Still seems like a hard problem.) $\endgroup$ – D.W. Aug 3 '18 at 19:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.