Greedy BFS

Duration: 2 min

This video lesson is available to enrolled students.

Enroll to watch — ZERO TO HERO

AI Summary

An AI-generated summary of this video lecture.

The video lecture introduces Greedy Best-first Search, defining it as an algorithm that always attempts to continue with the node that seems closest to the goal. The instructor distinguishes this from A* search by writing the evaluation function f(n) = h(n), indicating it relies solely on the heuristic. A diagram with nodes A, B, C, and D illustrates a scenario where the search might fail to find the best path. The lecture explicitly states that Greedy Best-first Search is neither optimal nor complete, similar to Depth-First Search. The session concludes by listing the algorithm's properties: it is not complete due to potential loops (e.g., Iasi -> Neamt -> Iasi), has a time complexity of O(b^m), a space complexity of O(b^m) because it keeps all nodes in memory, and is not optimal, demonstrated by a path cost comparison where the found path cost 450 versus an optimal cost of 418.

Chapters

  1. 0:00 – 1:38 00:00-01:38

    The video begins by defining Greedy Best-first Search as prioritizing nodes closest to the goal, writing the formula f(n) = h(n) to show it ignores path cost. A diagram with nodes A, B, C, and D illustrates a graph where the search might get stuck or take a longer route, leading to the text stating the method is 'not optimal' and 'not complete.' The instructor underlines these key limitations. The slide then transitions to a list of properties, detailing that the algorithm is not complete because it can get stuck in loops like Iasi -> Neamt -> Iasi. It lists time complexity as O(b^m) and space complexity as O(b^m), noting that a good heuristic can improve time but space remains high. Finally, it confirms the algorithm is not optimal, providing a specific example where a found path cost 450, while a better path (Arad to Bucharest) cost 418.

The lesson progresses from a conceptual definition of Greedy Best-first Search to its practical limitations and formal properties. By comparing it to A* and using a visual graph, the instructor highlights why relying solely on the heuristic h(n) leads to suboptimal solutions and potential infinite loops. The final slide consolidates these findings into standard search algorithm metrics (completeness, time, space, optimality), providing specific numerical examples to reinforce the theoretical claims.