- LPU MCA Semester 1
- CAB107
- Unit 5
CAB107 · Unit 5: Artificial intelligence techniques
Search algorithms and heuristic search
10 practice questions · in the ETE syllabus
Key points
- A* uses f(n) = g(n) + h(n)
- Admissible heuristics never overestimate
- Greedy best-first is fast but not optimal
- Alpha-beta gives the same answer as minimax with fewer nodes
A search problem has states, actions, a goal test and a path cost. Uninformed search uses no estimate of closeness to the goal; informed (heuristic) search uses a heuristic h(n), the estimated remaining cost.
| Algorithm | Orders nodes by | Optimal? |
|---|---|---|
| Breadth-first | Depth, level by level | Yes for equal step costs |
| Uniform-cost | Path cost g(n) | Yes |
| Greedy best-first | h(n) only | No |
| A* | f(n) = g(n) + h(n) | Yes if h is admissible |
Greedy best-first expands the node with the lowest h(n), so it is fast but not guaranteed to find the optimal path. A* is optimal if the heuristic is admissible, meaning it never overestimates the true remaining cost. If h(n) = 5 for a node whose true remaining cost is 3, the heuristic is not admissible, so A* may return a path that is not optimal.
Minimax plays a two-player game assuming optimal opponents, with MAX choosing the highest and MIN the lowest value. Alpha-beta pruning returns the same result as minimax but skips branches that cannot influence the decision. If a MIN node already has a value of 2 while MAX has a guaranteed 3 elsewhere, its remaining leaves can be pruned.
Exam trap: admissible means never overestimating. Underestimating is allowed; overestimating can make A* skip the optimal route.
Try two questions
A heuristic is admissible when it:
- Always overestimates the true cost to reach the goal
- Is equal to zero at every node of the graph
- Never overestimates the true cost to reach the goal
- Is computed after the search finishes
Show the answer
C. Admissibility guarantees A* returns an optimal path (with tree search).
Why not A: Overestimates can make A* miss the optimal path.
Why not B: A zero heuristic is admissible but not the definition.
Why not D: Heuristics are used during the search.
Starting from A, a depth-first search on the graph with edges A-B, A-C, B-D, B-E, C-F, E-F visits neighbours alphabetically. Which visiting order results?
- A, B, C, D, E, F
- A, B, D, E, F, C
- A, C, F, E, B, D
- A, B, D, C, F, E
Show the answer
B. DFS goes deep: A, B, D, back to B, E, F, back to A, then C, which is already reached through F.
Why not A: This is the breadth-first order.
Why not C: This goes down the C branch first and is not alphabetical.
Why not D: After D, DFS goes on to E before C.