Generalized A* for C-yoliic AND/OR Graphs *
Supriyo Ghose · 1998
The A* algorithm (Hart, Nilsson and Raphael 1968) has been the cornerstone of state-space search methods. Simultaneously, the vexing problem of cycles in AND/OR graphs has received considerable attention in recent times (Ghose 1998, Hvalica 1996, Chakrabarti 1994). We propose a generalization of A* to search AND/OR graphs that may contain cycles. The basic idea is that, if each AND node in an AND/OR graph has exactly one child, then the graph is virtually an ordinary (OR) graph and can be searched by applying