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

Uninformed Search Strategy for State Space Search Solving

NEHAAL
NEHAAL Last Updated : 18 Sep, 2022
5 min read

This article was published as a part of the Data Science Blogathon.

Introduction

 We saw the importance of PEAS representation in the article here. PEAS stands for Performance evaluation, Environment, Actuators, and Sensors. Agents understand their environment through sensors and perform relevant actions using Actuators. The search strategies of the agent decide this “relevant” action. This helps the agent choose the right move to reach the destination. Hence, It is important to compute the path for the agent to serve its purpose. AI uses different Search Strategies to compute the path for the agent.

Initial state and goal state of 8 puzzle. | Download Scientific Diagram

Why is Search Strategy Important?

Search Strategy

A simple Tic-Tac-Toe game can have 362880(9!) different states possible, and only a few of them lead us to victory. Similarly, the famous Missionaries and Cannibals problem also has many possible states. Do I even need to say about Chess? Lmao.

Cannibals & Missioneries : Plastelina Logic Games : Free Download, Borrow, and Streaming : Internet Archive

Search Strategies are structured ways to solve issues. Rational or Problem-solving agents in AI usually use these search strategies to solve a given problem and provide the best solution.

 Search Strategies are majorly classified into two:

  • Uninformed Search
  • Informed Search

Uninformed Search Strategy

Uninformed Search Strategies are search strategies that work in a brute force approach. Uninformed Search Strategy does not have any knowledge except what is defined in the problem’s constraints. They only work by blinding traversing through the different states and finding the path to the destination.
The 4 parameters on which we will evaluate the strategies are:

  • Completeness: If a search strategy can identify the path to the goal of our agent, then only we can call it complete.
  • Time Complexity: Measure of time.
  • Space Complexity: Maximum storage for worst-case conditions.
  • Optimal solution: The term “optimal solution” refers to a solution for an algorithm that is the best solution possible (lowest route cost).

The 6 Uninformed Search strategies that we will cover today are,

  • Breadth-first Search
  • Depth-first Search
  • Uniform cost search
  • Depth-limited Search
  • Iterative deepening depth-first search
  • Bidirectional Search


Breadth-First Search

The most popular search method for traversing a tree or graph is breadth-first search, which follows the level order traversing method. The breadth-first search algorithm performs level-by-level searches in a tree or graph. The BFS algorithm begins its search at the tree’s root node and grows every child node at the current level before moving on to nodes at the next level. We use a queue to implement BFS.
The BFS promises to provide a solution (if it exists). But this increases the time and space complexity when the goal states are situated very deep in a tree/graph. A BFS solution by me to the Missionaries and Cannibals problem is here.

 

Depth-First Search

A recursive approach for exploring a tree or graph is called depth-first search. The depth-first search begins at the root node, travels down each path until the depth of the tree by expanding one of its children, and then moves on to the next path. We use Stack to implement DFS.
DFS just needs to store a stack of the nodes on the path from the root node to the current node, hence it uses relatively little memory compared to other strategies. Since DFS goes for the depths first, it sometimes enters an infinite loop. Hence, DFS doesn’t ensure a complete solution.

Uniform-cost Search

Uniform-cost search can be used when the graphs have weighted vertices. It helps in finding the goal in one of the most optimal ways for a utility-based agent. The idea is to expand the cheapest node every time. This is done so by maintaining a frontier i.e. A priority queue ordered by the path cost(lower states are given higher priority).
Any graph or tree that requires the optimal cost can be solved with it. This strategy sometimes loses itself in an infinite loop as it focuses more only on path cost.

Depth limited Search

Depth Limited Search is similar to Depth First Search, but it is predetermined with a depth limit (say l). The nodes below the depth l are used as if they have no successors i.e., leaf nodes. This helps us in solving the infinite path problem of DFS. But this, too, can’t assure a complete solution. It may fail when our goal state lies in one of the levels below l.
It recursively moves to traverse the depth of the graph until the limit is reached. If it reaches the limit, it cutoffs and backtracks toward the other nodes for searching.

Iterative deepening depth-first search

This is one of the widely used strategies as it looks to combine the benefits of both the DFS and the BFS. This is beneficial for cases when the search space is too large and the solution’s depth is unknown. It starts with depth limit 0 of the tree and explores all its nodes before increasing the limit by 1 every time. This is done until one of the goals is found.
Like DFS, its memory requirements are modest. Like BFS, it promises a complete solution and an optimal one too, when the path cost is a non-decreasing function of the depth of the node.
For a graph/tree with branching factor 10 and depth 5, the Breadth-first search traverses 111,110 nodes in its worst case. At the same time, the iterative Deepening Depth-first search traverses 123,450 nodes.

 

Bidirectional Search

Bidirectional Search is a two-way search. i.e., one forward search from the initial state and the other backward search from the goal state. We hope the two searches may meet in the middle of one of the states.
The notion of using this search is that b^(d/2) + b^(d/2) is much less than b^d. Replace the goal test and determine whether the frontiers of the two searches intersect, if they do, a solution has been found. A schematic view of a bidirectional search is about to succeed when a branch from the start node meets a branch from the goal node.

 

Conclusion

Search Strategy

The above comparison chart compares the different uninformed search strategies based on the 4 parameters. This helps in understanding and correctly choosing our strategy for our agent to solve the problem we are working for. We can conclude that based on the requirements and expectations from the agent, we can choose a strategy and work accordingly.
What if I told you we could explore to experience and use the heuristics to get better strategies? Let’s see in the next article.

The media shown in this article is not owned by Analytics Vidhya and is used at the Author’s discretion.

NEHAAL
NEHAAL

🎓 I'm a Final-year Undergrad pursuing my BTech in Computer Science from MIT Academy Of Engineering, Pune. As a curious learner, I am also working on my honors in Data Science to expand my expertise in this domain.

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