AO* may require several subproblems instead of one A* path. Some notes call branch-and-bound over partial paths branch-based search. These traces make each choice, backup and discarded branch checkable by hand.
AO* and branch-based search solve different search structures
In an ordinary state space, a node is a state, an edge is a costed choice, and a solution is one start-to-goal path. Review frontier, expansion and path-cost vocabulary in Graph Algorithms: BFS, DFS and Dijkstra Traced Step by Step.
AO* works on an AND/OR graph. At an OR choice, one alternative is enough. At an AND decomposition, every child in the connector is required. Its answer can therefore be a solution subgraph, not one path.
Here, branch-based search means branch-and-bound over partial paths. Each branch gets a lower bound. Once a complete solution supplies an incumbent, a branch that cannot improve it can be discarded. Labels vary across textbooks, so follow the stated selection and pruning rules. For the wider preparation route, see the GATE CS Exam Preparation Courses & Test Series.
The AO* cost rule: choose across alternatives, add across requirements
Represent a decomposition from n by connector set K. Its backed-up cost is:
Q(n,K) = sum over m in K of [c(n,m) + F(m)]
Then F(n) = min over connectors K of Q(n,K). A singleton is an OR alternative; a multi-child connector is an AND requirement. A terminal goal has remaining cost 0.
Keep three numbers separate. c(n,m) is an edge cost, h(n) is the initial estimate at an unexpanded node, and F(n) is the backed-up estimate after expansion. For minimisation, an admissible h is a lower bound. Do not add OR alternatives or keep only the cheapest child of an AND connector.
AO* marks the cheapest root connector, follows it to an unsolved tip, expands that tip, backs up revised values and marks the cheapest connector again. A node is solved only when every child required by its marked connector is solved. Implementations must also handle cycles and repeated states; this example is acyclic.
Worked AO* example: back up values and switch connectors
Root S has an AND connector {A,B}, with both edge costs equal to 1, and a singleton connector {C} with edge cost 2. Initially, h(A)=2, h(B)=1 and h(C)=2.
The first backup at S is:
{A,B}:(1+2)+(1+1)=5{C}:2+2=4
AO* marks {C}. Expanding C reveals terminal choices H at cost 4 and I at cost 6, so F(C)=min(4+0,6+0)=4. Its root connector now costs 2+4=6. The unexpanded {A,B} estimate is still 5, so the marked connector switches.
Expanding A reveals terminal D at cost 2 and terminal E at cost 5. Thus F(A)=min(2,5)=2 through D. Expanding B reveals terminal F at cost 4 and terminal G at cost 1, so F(B)=min(4,1)=1 through G.
The complete AND connector costs (1+2)+(1+1)=5. The final solution subgraph is S -> {A,B}, A -> D and B -> G, with total cost 5. The alternative S -> C -> H costs 2+4=6. Choosing only A is incomplete because the marked connector requires both A and B.
Worked branch-based example: lower bounds and an incumbent
Score a live branch by L(n)=g(n)+h(n), where g(n) is its exact cost from S and admissible h(n) is a lower bound on what remains. Let U be the incumbent complete cost. Select the smallest L. For one optimum, prune when L >= U; to list every equal optimum, use a strict comparison.
Initially, A: g=2, h=4, L=6; B: g=1, h=2, L=3; and C: g=4, h=0, L=4. Expand B. Its cost-2 edge produces D, where g(D)=3, h(D)=2 and L(D)=5. Its cost-7 edge reaches G1 at 1+7=8, so set U=8.
Expand C next because L(C)=4. An edge of cost 3 reaches G2 at 4+3=7, improving the incumbent to U=7. Next expand D, whose lower bound is 5. Its goal edge costs 5, so S -> B -> D -> G3 costs 3+5=8 and cannot improve U.
Now expand A, whose lower bound is 6. Its direct goal edge of cost 6 gives 2+6=8. Its edge of cost 1 reaches E, with g(E)=3, h(E)=4 and L(E)=7. Prune E at equality because this run needs one optimal answer. No live branch has a bound below 7, so the result is S -> C -> G2, cost 7.
AO*, A* and branch-and-bound use different rules
Question | A* | AO* | Branch-and-bound |
|---|---|---|---|
Search object | Root-to-tip path | Partial solution graph | Root-to-tip branch |
Combination | Uses | Minimises across connectors, adds all children inside an AND connector | Uses a valid problem-specific bound |
Completion | Reaches a goal path under its termination conditions | Solves every child required by the marked connector | Proves the incumbent cannot be improved |
Stored state | Frontier and path information | Frontier plus marked connectors and solved status | Live branches plus incumbent |
Decision focus | Best estimated path | Best backed-up decomposition | Best bound and safe pruning |
A low estimate guides the search but does not prove optimality. That also needs the right lower-bound conditions and termination test. An overestimate can hide a cheaper solution, while a bound in the wrong direction proves nothing.
This differs from committing to a locally attractive choice, the viewpoint explained in Greedy Algorithms: Huffman, Knapsack, Activity Selection. Here {C} looks best at 4, but its backup becomes 6, so AO* switches to {A,B} at 5.
Traps that change the numerical answer
OR versus AND:
min(1+2,1+1)=2is not the cost of{A,B}because both branches are required. The correct result is3+2=5.Missing edge costs:
F(A)+F(B)=3omits the two unit edges fromS. The root cost is(1+2)+(1+1)=5.Frozen heuristic: retaining
h(C)=2after expandingCleaves its connector at an incorrect4. The backed-up value is2+F(C)=2+4=6.Pruning without an incumbent:
L(A)=6being greater thanL(C)=4does not justify pruningA. Neither value is a complete solution cost.Equality without checking the goal: after
U=7, pruningEatL(E)=7is safe for one optimum, but not when every cost-7solution is required.
Two ordinary OR edges from S do not show that A and B are jointly required, so keep the connector visible. A shared descendant may be miscounted unless the cost model says whether each use is charged. Cycles and duplicate states require implementation-specific handling.
How objective and numerical questions test the ideas
Typical tasks include identifying AND and OR nodes, backing up a value, marking a connector, selecting a tip, updating an incumbent, pruning branches or reporting the final cost. For numericals, record node or connector, g, h or current F, and solved, live or pruned status.
Try a 60-second check. Before expanding C, the root marks {C} at 4. After F(C) becomes 4, the root marks {A,B} at 5. The final AO* cost is 5. In the second trace, the first branch selected is B at lower bound 3, the final incumbent is 7, and E is equality-pruned at lower bound 7.
Generated nodes can still grow exponentially with depth and branching, especially with weak bounds. Frontiers and partial solution graphs consume memory. No universal Big-O expression applies without fixing the graph model, depth, branching, duplicate handling and heuristic quality.
Short version and the next practice step
One child is enough: it is an OR choice, so take the cheapest connector.
Several children are jointly required: it is AND, so add every required branch.
AO* backs revised values into a marked solution graph. Here the final cost is
5.Branch-and-bound keeps an incumbent and prunes against a valid bound. Here the final cost is
7.
Redraw both diagrams, hide the highlights and recompute every value. Then change only h(C) from 2 to 5. {A,B} is marked initially because 2+5=7 exceeds 5. This comparison does not claim that 5 is admissible when the true remaining cost from C is 4.
For practical AI, continue with the AI & ML for Placements. For structured GATE CS preparation, use GATE Guidance by Sanchit Sir. Keep final costs 5 and 7 as anchors, but rebuild them from the correct rule.
