g_harrison@vger.nsu.edu (George C. Harrison, Norfolk State University) (06/21/91)
Does anyone have any pointers to references on the A* algorithm? I have read (and understood) the A* algorithm section in Tanimoto's _The Elements of Artificial Intelligence_, but I'd like more. Is there a major text that uses this algorithm in many search applications? Thanks. George -- George C. Harrison ----------------------- ----- Professor of Computer Science ----------------------- ----- Norfolk State University ----------------------- ----- 2401 Corprew Avenue, Norfolk, Virginia 23504 ----------------------- ----- INTERNET: g_harrison@vger.nsu.edu ---------------------------------
hall@aplcen.apl.jhu.edu (Marty Hall) (06/24/91)
In article <1095.28610dc6@vger.nsu.edu> g_harrison@vger.nsu.edu (George C. Harrison, Norfolk State University) writes: >Does anyone have any pointers to references on the A* algorithm? > >I have read (and understood) the A* algorithm section in Tanimoto's _The >Elements of Artificial Intelligence_, but I'd like more. Is there a major text >that uses this algorithm in many search applications? Judea Pearl's _Heuristics_ (Addison Wesley, 1984/1985) has lots of theoretical discussion regarding A*. However, if you are looking for examples of A* application, then this may be too theoretical. Pearl does things like prove admissibility (ie that the first solution found will be the best one if the heuristic is non-overestimating), looking at time and space complexities, showing that the time complexity is the best possible among algorithms that calculate the weighting function (f) in the same manner, etc. Also, my opinion is that Richard Korf's IDA* (Iterative Deepening A*) is somewhat neglected, and is preferable to A* in many cases, running slightly faster (often), having a simple implementation, and with *linear* space complexity (as opposed to A*'s exponential memory requirements). Look at Korf's chapter on Search in either _Search in Artificial Intelligence_ by Kanal and Kumar eds (Springer Verlag, 1988) or _Exploring Artificial Intelligence_, edited by Shrobe (Morgan Kaufman, 1988). - Marty Hall ------------------------------------------------------ hall@aplcen.apl.jhu.edu, hall%aplcen@jhunix.bitnet, ..uunet!aplcen!hall Artificial Intelligence Lab, AAI Corp, PO Box 126, Hunt Valley, MD 21030 (setf (need-p 'disclaimer) NIL)