home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / ai / 4733 < prev    next >
Encoding:
Text File  |  1993-01-04  |  1.6 KB  |  41 lines
  1. Newsgroups: comp.ai
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!saimiri.primate.wisc.edu!aplcen.apl.jhu.edu!aplcenmp!hall
  3. From: hall@aplcenmp.apl.jhu.edu (Marty Hall)
  4. Subject: Re: Admissible Heuristic help
  5. Message-ID: <C0CAFu.AvJ@aplcenmp.apl.jhu.edu>
  6. Organization: AAI Corp AI Lab, JHU P/T CS Faculty
  7. References: <1992Dec28.124626.23201@cs.wayne.edu> <Dec.28.21.05.52.1992.26957@paul.rutgers.edu>
  8. Distribution: na
  9. Date: Mon, 4 Jan 1993 17:11:53 GMT
  10. Lines: 29
  11.  
  12. dcohen@paul.rutgers.edu (Dawn Myfanwy Cohen) writes:
  13. >(Jason Leigh) writes:
  14. >
  15. >> If any one can give me a definition, I'd really appreciate it, i.e. what
  16. >> does and does not make a heuristic admissible.  And if you know of a book
  17. >> where I can find this in, I'd like to know too.
  18. >
  19. >see Nilsson, Principles of Artificial Intelligence, 1980, p.76.
  20. >
  21. >"Let us say  that a search algorithm is  admissible if [first solution
  22. found is an optimal one]
  23.  
  24. Well, I have always maintained a distinction between an admissible algorithm
  25. and an admissible heuristic, although I'm not sure if this is normal usage.
  26. I've always used "Admissible Heuristic" to mean a heuristic for which A* is 
  27. admissible, ie one that is always non-overestimating and yields 0 for 
  28. solution nodes.
  29.  
  30. Search references that I like that probably discuss this are Pearl's 
  31. _Heuristics_, and Kanal and Kumar's  _Search in Artificial Intelligence_, 
  32. esp Chapter 8, "Optimal Path Finding Algorithms" by Rich Korf.
  33.  
  34.                         - Marty
  35. ------------------------------------------------------
  36. hall@aplcen.apl.jhu.edu, hall%aplcen@jhunix.bitnet, ..uunet!aplcen!hall
  37. Artificial Intelligence Lab, AAI Corp, PO Box 126, Hunt Valley, MD 21030
  38.  
  39. (proclaim '(inline skates))
  40. ---
  41.