Re: Tree search

Since your procedure traverses the tree from the root to some leaf
node, wouldn't the average amount of steps required for a solution be
the sum of the steps required to reach every leaf node, this divided by
the number of leaf nodes?

--
Bernd


kingpin@xxxxxxxxxxx wrote:
Hi to all,

you have a problem. Its search speace is modeled with a tree with
finite height. You have an evaluation function (heuristic) that says,
at every level i of the tree, if a node is better than another. The
heuristic is not perfect in the sense that it has some error. The
solutions is a path from the root to a node on the leaves that has some
property. Obviously, you don't heave enough information to decide
anything else: you must search.

I want to use A* (or best-first search) and study the aveage number of
nodes expandend before a solution is found.

How should i proceed? How should i specify the error the heuristic make
in order to simplify the analysis?

For example: the heuristic h is strictly monotonic, the tree is binary
and the problem is a minimization one.

I start to search with a b-f search. If, at level i, i make the wrong
decisions, i must search the whole sub-tree rooted at the son selected
before i can use the right node:

[i] level i
| \
| \
[1] [2] sons of level i

Since h([1]) < h([2]), than for every node n in the subtree rooted at
[1], h(n) < h([2]).

So, the "delay" is exponential....

I'am interested in the case that h is not strictly monotonic....

Any suggestion? Any paper? Any book?

Thank you,
Lucas

.

Relevant Pages

  • Re: Index tree
    ... But why it also affect the depth of the tree? ... The leaf pages store both the indexed values and the corresponding values ... The root page will have the indexed values of the first row on ...
    (microsoft.public.sqlserver.server)
  • Re: binary tree question
    ... starting with the root node and proceeding downward to a leaf (a node ... the following tree has exactly four root- ... Given a binary tree and a sum, return true if the tree has a root-to- ... is the base case and happens only when we have an empty subtree, i.e. the left subtree and right subtree of any leaf; in the example the nodes containing 7, 2 and 1 are leaves. ...
    (comp.programming)
  • Re: Questions for the Next Manifestation
    ... of this earth, have failed, throughout the long period of their ... When a tree grows, every step of the way, that part ... of the tree was destined to be a leaf. ... being the preservation of our genetic code to the preservation of our ...
    (soc.religion.bahai)
  • binary tree question
    ... starting with the root node and proceeding downward to a leaf (a node ... the following tree has exactly four root- ... Given a binary tree and a sum, return true if the tree has a root-to- ... int hasPathSum(struct node* node, int sum) { ...
    (comp.programming)
  • Re: binary tree question
    ... starting with the root node and proceeding downward to a leaf (a node ... the following tree has exactly four root- ... Given a tree and a sum, return true if there is a path from the root ... is the base case and happens only when we have an empty subtree, ...
    (comp.programming)