Understanding the Greedy Best-First Search (GBFS) Algorithm in Python

Introduction  

How to get the shortest path? A clever problem-solver, however, if you use the Greedy Best-First Search (GBFS) algorithm, you are willing to help. Think of it as that one friend who always puts the best foot forward. In this series of articles, I will explain Greedy Best-First Search and show examples using Python code. In this blog post, Let us see the wonders of Greedy Best-First Search while it makes smart choices and when it is apt for the job.

Learning Outcomes

• Understand the basic principles of the Greedy Best-First Search (GBFS) algorithm.
• Learn how to implement the GBFS algorithm in Python.
• Explore the use of Euclidean distance as a heuristic for GBFS.
• Analyze the advantages and disadvantages of using GBFS for pathfinding.
• Apply GBFS to solve pathfinding problems in grid-based scenarios.

How does GBFS Work?

Here’s a simple way to understand the GBFS algorithm:

• Start at the beginning: You start at the initial position or node.
• Evaluate options: Look at all the places you can go next.
• Choose the best option: Pick the place that looks closest to the goal.
• Repeat: Keep moving to the best-looking next place until you reach the goal.

Sounds simple, right? But there’s a catch! The GBFS algorithm doesn’t always find the shortest path because it only looks at what seems best right now, not considering the whole journey.

Step-by-Step Example

Let’s see an example using a simple grid. Imagine we have a 4×4 grid, and we want to go from the top-left corner (0, 0) to the bottom-right corner (3, 3). Here’s the grid with some obstacles:

[ [0, 1, 1, 1]
[1, 0, 1, 1]
[1, 0, 0, 1]
[1, 1, 0, 0] ]

In this grid, 1 means you can’t go through that cell, and 0 means you can. We’ll use the Euclidean distance as our heuristic, which is just a fancy way of saying the straight-line distance to the goal.

Writing the GBFS Algorithm in Python

Here’s how we can write the Greedy Best-First Search algorithm in Python.

Python Code:

import heapq
import math
class Node:
    def __init__(self, x, y, cost):
        self.x = x
        self.y = y
        self.cost = cost
    def __lt__(self, other):
        return self.cost < other.cost
def euclidean_distance(x1, y1, x2, y2):
    return math.sqrt((x1 - x2)**2 + (y1 - y2)**2)
def greedy_best_first_search(grid, start, goal):
    rows = len(grid)
    cols = len(grid[0])
    pq = []
    heapq.heappush(pq, Node(start[0], start[1], 0))
    visited = set()
    visited.add((start[0], start[1]))
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while pq:
        current = heapq.heappop(pq)
        if (current.x, current.y) == goal:
            print(f"Goal reached at ({current.x}, {current.y})")
            return
        for d in directions:
            new_x, new_y = current.x + d[0], current.y + d[1]
            if 0 <= new_x < rows and 0 <= new_y < cols and grid[new_x][new_y] == 0 and (new_x, new_y) not in visited:
                cost = euclidean_distance(new_x, new_y, goal[0], goal[1])
                heapq.heappush(pq, Node(new_x, new_y, cost))
                visited.add((new_x, new_y))
    print("Goal not reachable")

# Example grid
grid = [
    [0, 1, 1, 1],
    [1, 0, 1, 1],
    [1, 0, 0, 1],
    [1, 1, 0, 0]

]

start = (0, 0)
goal = (3, 3)
greedy_best_first_search(grid, start, goal)

Explanation of the Code

• Node Class: This class represents a point in the grid. It stores the x and y coordinates and the cost to reach that node.
• Euclidean Distance: This function calculates the straight-line distance between two points, which we use as our heuristic.
• Priority Queue: We use Python’s `heapq` to manage our priority queue. This helps us always pick the next node with the smallest cost.
• Visited Set: To keep track of the nodes we have already checked, we use a set called `visited`.
• Directions: These are the possible moves (up, down, left, right) we can make from any point.

Running the Algorithm

When you run this code, it starts from the top-left corner (0, 0) and tries to move to the bottom-right corner (3, 3). It picks the next step based on which one looks closest to the goal using the Euclidean distance.

Advantages and Disadvantages

Advantages:

• Simple and Easy to Implement: The GBFS algorithm is straightforward to understand.
• Fast: It can quickly find a path to the goal if the heuristic is good.

Disadvantages:

• Not Always Optimal: It doesn’t guarantee the shortest path.
• Can Get Stuck: Sometimes, it might get stuck in a loop or go down a dead-end path if the heuristic is misleading.

Conclusion

The Greedy Best-First Search algorithm provides a valuable technique for tackling pathfinding problems in grids or graphs. Its strength lies in rapidly identifying promising routes toward the goal by leveraging a well-designed heuristic function. However, it’s crucial to understand that the GBFS approach does not guarantee finding the optimal, shortest path. Its greedy nature may sometimes lead it astray if the heuristic is imperfect or misleading.

Despite this limitation, the algorithm’s simplicity, efficiency, and ability to produce reasonably good solutions quickly make it a valuable tool for programmers, particularly in time-sensitive situations where a near-optimal solution is preferable to an exhaustive but computationally expensive search for the absolute shortest path. Careful implementation and heuristic design can help harness the power of GBFS for a wide range of pathfinding challenges.

Frequently Asked Questions

NISHANT TIWARI

Seasoned AI enthusiast with a deep passion for the ever-evolving world of artificial intelligence. With a sharp eye for detail and a knack for translating complex concepts into accessible language, we are at the forefront of AI updates for you. Having covered AI breakthroughs, new LLM model launches, and expert opinions, we deliver insightful and engaging content that keeps readers informed and intrigued. With a finger on the pulse of AI research and innovation, we bring a fresh perspective to the dynamic field, allowing readers to stay up-to-date on the latest developments.