Understanding the greedy “best first” search algorithm

Introduction

How to get the shortest path? However, a smart troubleshooter, if using the Greedy Best-First Search (GBFS) algorithm, will be willing to help. Think of it as that friend who always does his best. In this series of articles, I will explain Greedy Best-First Search and show examples using Python code. In this blog post, let's look at the wonders of Greedy Best-First Search as you make smart decisions and when you're fit 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.
• Discuss the advantages and disadvantages of using GBFS for route finding.
• Apply GBFS to solve path finding problems in grid-based scenarios.

How does GBFS work?

Below is a simple way to understand the GBFS algorithm:

• Start at the beginning: You start at the initial position or node.
• Evaluate options: Check out all the places you can go below.
• Choose the best option: Choose the place that seems closest to the goal.
• Repeat: Continue moving towards the next most attractive location until you reach the finish line.

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 at the moment, without considering the entire journey.

Step by step example

Let's look at an example using a simple grid. Let's 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 is 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 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

This is 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)

Code Explanation

• Node class: This class represents a point on the grid. 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 choose the next node with the lowest cost.
• Visited set: To keep track of which nodes we have already checked, we use a set called “visited”.
• Addresses: These are the possible movements (up, down, left, right) that 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). Choose the next step based on which seems closest to the goal using Euclidean distance.

Advantages and disadvantages

Advantages:

• Simple and easy to implement: The GBFS algorithm is simple to understand.
• Fast: You can quickly find a path to the goal if the heuristics are good.

Disadvantages:

• It is not always optimal: it does not guarantee the shortest path.
• You can get stuck: Sometimes you can get stuck in a loop or reach a dead end if the heuristics are misleading.

Conclusion

The Greedy Best-First Search algorithm provides a valuable technique for addressing path-finding problems on grids or graphs. Its strength lies in quickly identifying promising paths to the goal by leveraging a well-designed heuristic function. However, it is essential to understand that the GBFS approach does not guarantee finding the shortest and optimal path. Your greedy nature can sometimes lead you astray if the heuristics are imperfect or misleading.

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

Frequent questions