[gecode-users] Number of failed nodes

Patrik Haslum patrik.haslum at anu.edu.au
Thu Jan 8 11:25:21 CET 2009

Lars Kotthoff wrote:

>> If you set the c-d parameter to 1, I think the number of clones
>> equals the number of nodes explored (maybe plus or minus 1 or 2 or
>> so...)
> According to the manual, this will make the number of clones equal to the number
> of commits (a clone is created for every commit) -- is the number of commits
> equivalent to the number of nodes?

Right, my mistake. The number of commits plus one should be the right 
number. For an exhausted binary search tree, the number of clones seems 
to be about half that (which makes sense assuming the optimisation that 
a clone is only created for one of the branches, and the other commit 
applied directly to the parent node).

On an example that is small enough to view in Gist, I get a (binary) 
search tree with 14 leaf nodes (all failed, since the problem is 
unsolvable) and 13 internal nodes. The statistics for this tree are:

Failed: 14
Clones: 13 (one for every node that has a child / two children)
Commits: 26 (one for every node except the root).

If c-d is greater than 1, the number of commits goes up.

			/P at trik

More information about the gecode-users mailing list