Scribd
Upload
2 views11 pages

Lecture 8

The document discusses the AO* algorithm in the context of problem reduction search, particularly using AND-OR graphs or trees. It explains how problems can be decomposed into subproblems, with AND arcs representing the need for all subproblems to be solved for a complete solution. The document highlights the limitations of the A* algorithm in efficiently searching AND-OR graphs.

Uploaded by

hogwartsgryffindor007
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views11 pages

Lecture 8

The document discusses the AO* algorithm in the context of problem reduction search, particularly using AND-OR graphs or trees. It explains how problems can be decomposed into subproblems, with AND arcs representing the need for all subproblems to be solved for a complete solution. The document highlights the limitations of the A* algorithm in efficiently searching AND-OR graphs.

Uploaded by

hogwartsgryffindor007
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 11

FOUNDAMENTALS IN AI and ML

School of Computer Science and Engineering

LECTURE-8
Problem Reduction Search
Problem Reduction with AO*
Algorithm

Purchase TV

Goto
Steal TV Money Purchase
Shop
Problem Reduction with AO*
Algorithm

When a problem can be divided into a set of sub problems, where each sub
problem can be solved separately and a combination of these will be a solution,
AND-OR graphs or AND – OR trees are used for representing the solution. The
decomposition of the problem or problem reduction generates AND arcs. One
AND are may point to any number of successor nodes. All these must be solved
so that the arc will rise to many arcs, indicating several possible solutions.

Hence the graph is known as AND - OR instead of AND. Figure shows an AND
- OR graph. An algorithm to find a solution in an AND - OR graph must handle
AND area appropriately. A*algorithm can not search AND - OR graphs
efficiently
Problem Reduction with AO*
Algorithm
AO* Algorithm
AO* Algorithm
AO* Algorithm
AO* Algorithm
AO* Algorithm

You might also like