- How To Stop Windows 10 Auto Update
- What is an Antenna In Telecommunication
- TCP Model In Computer Networking
- Ip Address And Its Classes
- How to setup Xampp Tomcat In Netbean
- OSI Model In Networking
- Classical Waterfall model In Software Engineering
- What Is Software Engineering?
- How To Retrieve Input data From Input Field
- What Is V-Model In Software Engineering

Welcome back to LiveiPlmatch.Com. we are going to discuss Problem Redundancy AO Search, It is the type of problem reduction.

Problem reduction search requires **And/Or** Graph/Tree.

**Problem Reduction :**

To find the best way to solve the problem if the problem decomposed into subprblem such that there exist multiple ways of decompositions.

Any problem in problem reduction search can be represented using AND/OR Graph.

In such graph each node ‘n’ represents a sub-problem which is to be forther decomposed.

An ‘OR’ node in the graph represents a choice between alternate decomposeitions.

‘AND’ node represents a possible decompositions into sub-problem where each must be solved.

Each node ‘n’ can have an Heuristic value i.e. h(n). Where h(n) is an estimation of the cost to solve ‘n’.

SOLVING…..

**Given = {G , S , T}**

G : It is an AND / OR graph.

S : initial state i.e. it represents a problem which should be solved

T : Set of terminal value

h(n) : Heuristic Value

We need to find G* which is a marked subtree that gives the best decompositions.

**Algorithm**

Step 1 : G* = { s } , f(x) = h(s)

if S E T mark s as solved

Step 2 : if S is labelled as solved then return G*

Step 3 : Select a non-terminal leaf from marked subtree & let it be n.

Step 4 : Generate successor of n

for each successor m of n

f(m) = h(m)

Step 5 : cost_revise(n)

Step 6 : go to step 2.

COST_REVISION(n):

Step 1 : x = {n}

Step 2 : if x={} then return

Step 3 : remove a state m from x which do not have any children in x

Step 4 : if m is AND node having successor r1,r2,r3…………..rk

for each Ri

f(m) = Ef(ri) + cost(MiRi)

marked each edege m to ri

Step 5 : If m is OR node having successor

ri…….rk

for each ri

f(m) = min { f(ri) + cost(MiRi) }

mark best successor m —>Ri

Step 6 : if f(m) has changed then insert parent (m) in x

Step 7 : Go to Step 2.

Related Posts