home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / ai / 4710 < prev    next >
Encoding:
Internet Message Format  |  1992-12-29  |  3.0 KB
  1. Path: sparky!uunet!wupost!uwm.edu!psuvax1!rutgers!igor.rutgers.edu!paul.rutgers.edu!dcohen
  2. From: dcohen@paul.rutgers.edu (Dawn Myfanwy Cohen)
  3. Newsgroups: comp.ai
  4. Subject: Re: Admissible Heuristic help
  5. Message-ID: <Dec.28.21.05.52.1992.26957@paul.rutgers.edu>
  6. Date: 29 Dec 92 02:05:52 GMT
  7. References: <1992Dec28.124626.23201@cs.wayne.edu>
  8. Distribution: na
  9. Organization: Rutgers Univ., New Brunswick, N.J.
  10. Lines: 56
  11.  
  12. (Jason Leigh) writes:
  13.  
  14. > If any one can give me a definition, I'd really appreciate it, i.e. what
  15. > does and does not make a heuristic admissible.  And if you know of a book
  16. > where I can find this in, I'd like to know too.
  17.  
  18. see Nilsson, Principles of Artificial Intelligence, 1980, p.76.
  19.  
  20. "Let us say  that a search algorithm is  admissible if, for any graph,
  21. it always terminates in an optimal path from s to a goal node whenever
  22. a path from s to a goal node exists."
  23.  
  24. Now, I think that what you probably have in  mind, given  that you are
  25. talking about "heuristic", is the A* algorithm, which is a variant  on
  26. algorithm A...back up a couple of pages from the above quote.
  27.  
  28. Algorithm  A is a way  to  search  a  graph.   It  uses  a  notion  of
  29. evaluation functions.  You are  trying to reach a goal node, x, from a
  30. current node, n, having paid a certain price to  get to n,  from start
  31. node s.  You want to  minimize the total cost of getting from s  to x.
  32. That optimum total cost is given by
  33.                     f*(n) = g*(n) + h*(n)
  34. where g*(n) is the cost of getting from s to n and h*(n) is the cost
  35. of getting from n to any goal.  
  36.  
  37. Now, in general, you have got a handle on g*(n):  you know how much it
  38. has already cost you  to get from s to  n, given that you have already
  39. searched from s to n.   The hard part is figuring out what the optimal
  40. cost of a path from n to any goal node, given that you  don't yet know
  41. where a goal node is in the graph.
  42.  
  43. This is where heuristics come into the picture.  You can replace h*(n)
  44. with  your  favorite   estimate  (heuristic)  h(n)  for  h*(n).   Now,
  45. depending on  how close your  estimate  of h(n) is  to h*(n), the more
  46. accurate will be your estimate of the total cost of going from s  to x
  47. through  n.  If your estimate  of  the cost is  accurate, then you can
  48. always find an optimal path exactly.  If your estimate of the  cost is
  49. almost accurate, you can probably find  an optimal path exactly (or an
  50. almost optimal path).
  51.  
  52. However,  if  you use  an  admissible  heuristic,  then,  even if  the
  53. estimate is  not  close, you are still  guaranteed to find an  optimal
  54. path (possibly by  spending a  lot of search time  in identifying  the
  55. path.)   An admissible heuristic is one  that  NEVER OVERESTIMATES the
  56. cost of going from n to  a goal  node.  I.e. h(n) <= h*(n) for every n
  57. in the graph.  You can see Nilsson for a proof.
  58.  
  59. --Dawn
  60. -- 
  61. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  62. Good Morning!        
  63. --Dawn
  64.  
  65. Send fan mail to:
  66. uucp:  {ames,bosgd,harvard,moss}!rutgers!paul.rutgers.edu!dcohen
  67. arpa:  dcohen@paul.rutgers.edu
  68.