ijd@otter.hpl.hp.com (Ian Dickinson) (01/25/89)
Does anyone know of an overview, anthology or bibliography of _current_ [heuristically guided] graph searching techniques or algorithms? Ie, I am more interested in the results of recent research than techniques like A*, though modifications to that algorithm might be interesting. Of particular interest would be algorithms for locating solutions comprising a set of nodes, rather than a single node. Thanks in advance, Ian. | Ian Dickinson, HP Labs, Information Systems Centre, Bristol, England | | net: ijd%otter@hplabs.hp.com | | | or: ijd@hplb.uucp | ?- mind(X), body(X), spirit(X). | | These opinions are all my own work. | |
apl_aimh@jhunix.HCF.JHU.EDU (Marty Hall) (01/27/89)
In <2070025@otter.hpl.hp.com> ijd@otter.hpl.hp.com (Ian Dickinson) writes: > >Does anyone know of an overview, anthology or bibliography of _current_ >[heuristically guided] graph searching techniques or algorithms? Ie, I >am more interested in the results of recent research than techniques like >A*, though modifications to that algorithm might be interesting. Of >particular interest would be algorithms for locating solutions comprising >a set of nodes, rather than a single node. My favorite overview of search is "Search: A Survey of Recent Results" by Richard Korf of UCLA. It appears in Shrobe, Howard, ed, _Exploring Artificial Intelligence_, Morgan Kaufmann, 1988, pp 197-238. It is basically the survey talk Dr. Korf gave at last summer's AAAI meeting. Several extensions to A* are discussed, especially an Iterative-Deepening version, IDA* (which is not all that new) and Real-Time A* (RTA*), which as far as I recall, was first presented at the Seattle AAAI. If you can't find this book, a very similar paper by Korf is Chapter 7, "Optimal Path Finding Algorithms" in Kanal & Kumar, eds, _Search in Artificial Intelligence_, Springer-Verlag, 1988. This book has the advantage of several other good chapters on recent results in search, although the Shrobe book has several other terrific survey talks from AAAI, just not on search. Enjoy! - Marty Hall apl_aimh@jhunix.hcf.jhu.edu Artificial Intelligence Laboratory, MS 100/601 ...uunet!jhunix!apl_aimh AAI Corporation apl_aimh@jhunix.bitnet PO Box 126 (301) 683-6455 Hunt Valley, MD 21030
sbc@wucs1.wustl.edu (Steve B Cousins) (01/28/89)
There is also a nice survey by J. Pearl (it was co-authored, but I don't have it in front of me) in the 1987 Annual Review of Computer Science. It may be the same paper as the Korf one mentioned. Steve Cousins sbc@wucs1.WUSTL.EDU