25:31
B&B - A* - wA* - Best First
NPTEL-NOC IITM
Overview
This video introduces a generalized framework for understanding various search algorithms like Best-First Search, Branch and Bound, A*, and Weighted A* (wA*). It explains how these algorithms can be viewed as instances of a single function f(n) = g(n) + w * h(n), where g(n) is the cost from the start, h(n) is the heuristic estimate to the goal, and 'w' is a weight controlling the emphasis on the heuristic. By varying 'w', different search behaviors emerge, trading off optimality for speed and memory usage. The video uses a concrete example to illustrate how different values of 'w' affect pathfinding and node exploration.
How was this?
Save this permanently with flashcards, quizzes, and AI chat
Chapters
- Search algorithms can be unified under a framework using the function f(n) = g(n) + w * h(n).
- g(n) represents the 'pull' towards the source (cost incurred so far).
- h(n) represents the 'push' towards the goal (heuristic estimate of remaining cost).
- The weight 'w' controls the balance between exploring paths close to the source (low w) and paths that seem close to the goal (high w).
Understanding this generalized framework allows for a deeper comprehension of how different search strategies prioritize exploration and why they yield different results in terms of path quality and efficiency.
The function f(n) = g(n) + w * h(n) is introduced as the unifying concept.
- When w=0, f(n) = g(n), prioritizing only the cost from the start. This behavior is characteristic of Branch and Bound (or Dijkstra's algorithm).
- When w tends to infinity, f(n) is dominated by h(n), prioritizing only the heuristic estimate to the goal. This behavior is characteristic of greedy Best-First Search.
- These extremes represent algorithms that either strictly follow the cost from the source or aggressively pursue the estimated closest path to the goal.
Recognizing these extremes helps in understanding the fundamental trade-offs: focusing solely on past cost guarantees optimality but can be slow, while focusing solely on estimated future cost is fast but may not be optimal.
Setting w=0 makes f(n) equal to g(n), reducing the search to algorithms like Branch and Bound. Letting w approach infinity prioritizes h(n), mimicking Best-First Search.
- A* search is a special case of the generalized framework where w=1.
- It balances the cost incurred (g(n)) with the estimated cost to the goal (h(n)).
- If the heuristic function h(n) is admissible (never overestimates the true cost), A* guarantees finding the optimal path.
- A* explores nodes in an order determined by the sum of actual cost and estimated cost.
A* is a widely used and important algorithm because it offers a principled way to find the optimal path efficiently by combining information about past costs and future estimates.
In the example graph, A* calculates f-values (g+h) for nodes and selects the one with the lowest f-value to expand.
- Weighted A* (wA*) uses a weight w > 1 in the f(n) = g(n) + w * h(n) function.
- Increasing 'w' gives more importance to the heuristic function h(n), pushing the search more aggressively towards the goal.
- This increased heuristic emphasis can lead to faster search (fewer nodes explored) but may sacrifice optimality.
- When w > 1, the heuristic function is no longer guaranteed to be admissible, meaning wA* might not find the shortest path.
wA* provides a mechanism to tune the search performance, allowing learners to trade optimality for speed and reduced memory usage when an exact optimal path is not strictly necessary.
With w=2, wA* in the example graph prioritizes nodes with lower heuristic values more strongly, potentially diverging from the optimal path found by A*.
- Branch and Bound (w=0) explores exhaustively based on g(n) and guarantees optimality but can be slow and memory-intensive.
- Best-First Search (w=infinity) greedily follows h(n), is fast but often non-optimal.
- A* (w=1) with an admissible heuristic finds the optimal path and is generally more efficient than Branch and Bound.
- Weighted A* (w>1) offers a faster search than A* by increasing heuristic weight, but sacrifices guaranteed optimality.
- As 'w' increases, the number of nodes explored generally decreases, but the path cost may increase.
Comparing these algorithms highlights the fundamental trade-offs in search: optimality versus speed and memory, and how heuristic weighting influences these factors.
A table compares the number of nodes explored and path costs for Branch and Bound (23 nodes), A* (14 nodes, cost 148), and wA* (9 nodes, cost 153) on the same example graph.
Key takeaways
- Search algorithms can be generalized using f(n) = g(n) + w * h(n), where 'w' controls the heuristic's influence.
- Branch and Bound (w=0) prioritizes cost from the start (g(n)) and guarantees optimality.
- Best-First Search (w=infinity) prioritizes estimated cost to the goal (h(n)) and is fast but not optimal.
- A* (w=1) balances g(n) and h(n) to find optimal paths efficiently, provided the heuristic is admissible.
- Weighted A* (w>1) speeds up search by emphasizing h(n) but may yield non-optimal paths because the heuristic becomes inadmissible.
- There is a direct trade-off between search speed/memory and path optimality, influenced by the weighting of the heuristic function.
- Understanding these trade-offs is crucial for selecting the appropriate search algorithm for a given problem.
Key terms
Search AlgorithmsState SpacePlan SpaceBranch and BoundBest-First SearchA* SearchWeighted A* (wA*)Heuristic Function (h(n))Cost Function (g(n))Admissible Heuristic
Test your understanding
- How does the weight 'w' in the function f(n) = g(n) + w * h(n) affect the search behavior of an algorithm?
- What is the primary difference in exploration strategy between Branch and Bound (w=0) and Best-First Search (w approaching infinity)?
- Under what condition does A* search guarantee finding the optimal path?
- Why might Weighted A* (w>1) find a path faster than A*, but not necessarily the optimal path?
- Explain the trade-off between search efficiency (speed and memory) and path optimality when choosing between A* and Weighted A*.