Interview Prep
Career
GenAI
Prompt Engg
ChatGPT
LLM
Langchain
RAG
AI Agents
Machine Learning
Deep Learning
GenAI Tools
LLMOps
Python
NLP
SQL
AIML Projects

Reading list

Machine Learning Basics for a Newbie
6 Steps of Machine learning Lifecycle Introduction to Predictive Modeling
Introduction to Exploratory Data Analysis & Data Insights Descriptive Statistics Inferential Statistics How to Understand Population Distributions?
Reading Data Files into Python Different Variable Datatypes
Probability for Data Science Basic Concepts of Probability Axioms of Probability Conditional Probability
Central Tendencies for Continuous Variables Spread of Data KDE plots for Continuous Variable Overview of Distribution for Continuous variables Normal Distribution Skewed Distribution Skeweness and Kurtosis Distribution for Continuous Variable
Central Tendencies for Categorical Variables Understanding Discrete Distributions Performing EDA on Categorical Variables
Dealing with Missing Values Understanding Outliers Identifying Outliers in Data Outlier Detection in Python Outliers Detection Using IQR, Z-score, LOF and DBSCAN
Sample and Population Central Limit Theorem Confidence Interval and Margin of Error
Bivariate Analysis Introduction
Covariance Pearson Correlation Spearman's Correlation & Kendall's Tau Correlation versus Causation Tabular and Graphical methods for Bivariate Analysis Performing Bivariate Analysis on Continuous-Continuous Variables
Tabular and Graphical methods for Continuous-Categorical Variables Introduction to Hypothesis Testing P-value Two sample Z-test T-test T-test vs Z-test Performing Bivariate Analysis on Continuous-Catagorical variables
Chi-Squares Test Bivariate Analysis on Categorical Categorical Variables
Multivariate Analysis A Comprehensive Guide to Data Exploration The Data Science behind IPL
Supervised Learning vs Unsupervised Learning Reinforcement Learning Generative and Descriminative Models Parametric and Non Parametric model
Machine Learning Pipeline Preparing Dataset Build a Benchmark Model: Regression Build a Benchmark Model: Classification
Evaluation Metrics for Machine Learning Everyone should know Confusion Matrix Accuracy Precision and Recall AUC-ROC Log Loss R2 and Adjusted R2
Dealing with Missing Values Replacing Missing Values Imputing Missing Values in Data Working with Categorical Variables Working with Outliers Preprocessing Data for Model Building
Understanding Cost Function Understanding Gradient Descent Math Behind Gradient Descent Assumptions of Linear Regression Implement Linear Regression from Scratch Train Linear Regression in Python Implementing Linear Regression in R Diagnosing Residual Plots in Linear Regression Models Generalized Linear Models Introduction to Logistic Regression Odds Ratio Implementing Logistic Regression from Scratch Introduction to Scikit-learn in Python Train Logistic Regression in python Multiclass using Logistic Regression How to use Multinomial and Ordinal Logistic Regression in R ? Challenges with Linear Regression Introduction to Regularisation Implementing Regularisation Ridge Regression Lasso Regression
Introduction to K Nearest Neighbours Determining the Right Value of K in KNN Implement KNN from Scratch Implement KNN in Python
Bias Variance Tradeoff Introduction to Overfitting and Underfitting Visualizing Overfitting and Underfitting Selecting the Right Model What is Validation? Hold-Out Validation Understanding K Fold Cross Validation
Introduction to Feature Selection Feature Selection Algorithms Missing Value Ratio Low Variance Filter High Correlation Filter Backward Feature Elimination Forward Feature Selection Implement Feature Selection in Python Implement Feature Selection in R
Introduction to Decision Tree Purity in Decision Tree Terminologies Related to Decision Tree How to Select Best Split Point in Decision Tree? Chi-Squares Information Gain Reduction in Variance Optimizing Performance of Decision Tree Train Decision Tree using Scikit Learn Pruning of Decision Trees
Introduction to Feature Engineering Feature Transformation Feature Scaling Feature Engineering Frequency Encoding Automated Feature Engineering: Feature Tools
Introduction to Naive Bayes Conditional Probability and Bayes Theorem Introduction to Bayesian Adjustment Rating: The Incredible Concept Behind Online Ratings! Working of Naive Bayes Math behind Naive Bayes Types of Naive Bayes Implementation of Naive Bayes
Understanding how to solve Multiclass and Multilabled Classification Problem Evaluation Metrics: Multi Class Classification
Introduction to Ensemble Techniques Basic Ensemble Techniques Implementing Basic Ensemble Techniques Finding Optimal Weights of Ensemble Learner using Neural Network Why Ensemble Models Work well?
Introduction to Stacking Implementing Stacking Variants of Stacking Implementing Variants of Stacking Introduction to Blending Bootstrap Sampling Introduction to Random Sampling Hyper-parameters of Random Forest Implementing Random Forest Out-of-Bag (OOB) Score in the Random Forest IPL Team Win Prediction Project Using Machine Learning Introduction to Boosting Gradient Boosting Algorithm Math behind GBM Implementing GBM in python Regularized Greedy Forests Extreme Gradient Boosting Implementing XGBM in python Tuning Hyperparameters of XGBoost in Python Implement XGBM in R/H2O Adaptive Boosting Implementing Adaptive Boosing LightGBM Implementing LightGBM in Python Catboost Implementing Catboost in Python
Different Hyperparameter Tuning methods Implementing Different Hyperparameter Tuning methods GridsearchCV RandomizedsearchCV Bayesian Optimization for Hyperparameter Tuning Hyperopt
Understanding SVM Algorithm SVM Kernels In-depth Intuition and Practical Implementation SVM Kernel Tricks Kernels and Hyperparameters in SVM Implementing SVM from Scratch in Python and R
Introduction to Principal Component Analysis Steps to Perform Principal Compound Analysis Computation of Covariance Matrix Finding Eigenvectors and Eigenvalues Implementing PCA in python Visualizing PCA A Brief Introduction to Linear Discriminant Analysis Introduction to Factor Analysis
Introduction to Clustering Applications of Clustering Evaluation Metrics for Clustering Understanding K-Means Implementation of K-Means in Python Implementation of K-Means in R Choosing Right Value for K Profiling Market Segments using K-Means Clustering Hierarchical Clustering Implementation of Hierarchial Clustering DBSCAN Defining Similarity between clusters Build Better and Accurate Clusters with Gaussian Mixture Models
Understand Basics of Recommendation Engine with Case Study
8 Ways to Improve Accuracy of Machine Learning Models
Introduction to Dask Working with CuML
Introduction to Machine Learning Interpretability Framework and Interpretable Models model Agnostic Methods for Interpretability Implementing Interpretable Model Understanding SHAP Out-of-Core ML Introduction to Interpretable Machine Learning Models Model Agnostic Methods for Interpretability Game Theory & Shapley Values
Introduction to Machine Learning Interpretability Framework and Interpretable Models model Agnostic Methods for Interpretability Implementing Interpretable Model Understanding SHAP Out-of-Core ML Introduction to Interpretable Machine Learning Models Model Agnostic Methods for Interpretability Game Theory & Shapley Values
Introduction to AutoML Implementation of MLBox Introduction to PyCaret TPOT Auto-Sklearn EvalML
Pickle and Joblib Introduction to Model Deployment
Deploying Machine Learning Model using Streamlit Deploying ML Models in Docker Deploy Using Streamlit Deploy on Heroku Deploy Using Netlify Introduction to Amazon Sagemaker Setting up Amazon SageMaker Using SageMaker Endpoint to Generate Inference Deploy on Microsoft Azure Cloud Introduction to Flask for Model Deploying ML model using Flask
Model Deployment in Android Model Deployment in Iphone

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

NISHANT TIWARI
NISHANT TIWARI Last Updated : 08 Jun, 2024
4 min read

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.
Greedy Best-First Search

Table of contents

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

Q1. What is the Greedy Best-First Search (GBFS) algorithm?

A. The Greedy Best-First Search algorithm is a pathfinding technique that selects the next move based on which option appears closest to the goal, using a heuristic to guide its decisions.

Q2. How does GBFS differ from other pathfinding algorithms?

A. Unlike algorithms like A* that consider both the current cost and the estimated cost to the goal, GBFS focuses only on the heuristic estimate to the goal, making it faster but not always optimal.

Q3. Can GBFS guarantee finding the shortest path?

A. No, GBFS does not guarantee the shortest path because it only considers the heuristic estimate and not the overall cost from the start to the goal.

NISHANT TIWARI
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.

Free Courses

Generative AI 4.7

Generative AI - A Way of Life

Explore Generative AI for beginners: create text and images, use top AI tools, learn practical skills, and ethics.
Large Language Models 4.5

Getting Started with Large Language Models

Master Large Language Models (LLMs) with this course, offering clear guidance in NLP and model training made simple.
Prompt Engineering 4.6

Building LLM Applications using Prompt Engineering

This free course guides you on building LLM apps, mastering prompt engineering, and developing chatbots with enterprise data.
LlamaIndex 4.8

Improving Real World RAG Systems: Key Challenges & Practical Solutions

Explore practical solutions, advanced retrieval strategies, and agentic RAG systems to improve context, relevance, and accuracy in AI-driven applications.
RAG systems using LlamaIndex 4.7

Microsoft Excel: Formulas & Functions

Master MS Excel for data analysis with key formulas, functions, and LookUp tools in this comprehensive course.

Recommended Articles

Responses From Readers

Clear

Write for us

Write, captivate, and earn accolades and rewards for your work
  • Reach a Global Audience
  • Get Expert Feedback
  • Build Your Brand & Audience
  • Cash In on Your Knowledge
  • Join a Thriving Community
  • Level Up Your Data Science Game
imag

We use cookies essential for this site to function well. Please click to help us improve its usefulness with additional cookies. Learn about our use of cookies in our Privacy Policy & Cookies Policy.

Show details