Chapter 3 · Watch, then practise
Search Techniques
Compare uninformed and heuristic search by frontier ordering, solution cost and the assumptions needed for guarantees.
3 questions · 3 with related videos. Matches are based on playlist titles; broader background matches are labeled.
What to study
- Breadth-first and depth-first search
- Uniform-cost search
- Greedy search and A*
- Admissible and consistent heuristics
Chapter playlists
Choose a playlist
Notes
Lec-7: Breadth First Search (BFS) with example | Uninformed Search | Artificial Intelligence
Gate Smashers · 12:57
Choose a video · 2 lectures
BFS and DFS frontier rules are covered by these chapter lectures; use the written answer for the uniform-cost comparison.
1. Choose a frontier
How do BFS, DFS and uniform-cost search choose a node?
BFS uses a queue to expand shallow nodes first; DFS uses a stack to explore deeply; uniform-cost search chooses minimum path cost g. BFS gives a shortest action sequence when action costs are equal. With unequal costs, the fewest actions need not be the cheapest route.
A* Algorithm Explained In The Easiest And Quickest Way Ever With Example (HINDI)
5 Minutes Engineering · 6:36
An A* example supports using g + h to order the frontier; its numbers are not this exercise.
2. A* evaluation
Two frontier nodes have (g,h) values (6,4) and (3,8). Which does A* prefer?
A* evaluates f = g + h, giving 10 and 11, so it prefers the first. Greedy best-first search uses only h. An admissible heuristic does not overestimate remaining cost; consistency additionally requires h(n) ≤ cost(n,n′) + h(n′).
Lec-21: How to Proof A* Admissible| Underestimation & Overestimation of A* in Hindi
Gate Smashers · 12:25
The supplementary A* admissibility lecture matches the optimality-guarantee topic; retain the search-variant conditions stated in the answer.
3. State the guarantee
When does A* find an optimal solution?
A* tree search finds an optimal solution with a nonnegative admissible heuristic, finite branching and step costs bounded below by a positive constant. Graph search that never reopens closed states needs consistency; with an inconsistent admissible heuristic, reopen a state when a cheaper path appears. Test goals when removing nodes from the frontier.