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 suggestions? Any papers? Any boosk?   
      
   Thank you,   
   Lucas   
      
   [ comp.ai is moderated ... your article may take a while to appear. ]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)