A general best first search algorithm in AND/OR graphs

Chakrabarti, P. P. ; Ghose, S. (1992) A general best first search algorithm in AND/OR graphs Journal of Algorithms, 13 (2). pp. 177-187. ISSN 0196-6774

Full text not available from this repository.

Official URL: http://linkinghub.elsevier.com/retrieve/pii/019667...

Related URL: http://dx.doi.org/10.1016/0196-6774(92)90014-4


A general formulation of best first search in the setting of AND/OR graphs has been considered where both minimization and maximization occur together. This leads to the development of an AND/OR graph search algorithm called GEN-AO* which works with two types of OR nodes, MIN and MAX, and uses both upper and lower bound estimates. It is shown that this algorithm generates optimal cost solutions. The worst case set of nodes expanded is examined. Such an algorithm generalizes other known algorithms. Pruning conditions for the depth-first variation is examined.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
ID Code:5957
Deposited On:19 Oct 2010 10:03
Last Modified:20 May 2011 09:48

Repository Staff Only: item control page