Algorithms for searching explicit AND/OR graphs and their applications to problem reduction search

摘要

We present algorithms for finding out optimal cost solutions of an explicit AND/OR graph. We show that these new algorithms can work on AND/OR graphs containing cycles. Finally, we show how these algorithms can be incorporated in implicit graph search schemes like AO∗ so that they work for transformation rules which lead to graphs with cycles.