Searching is the universal technique of problem solving in AI. There are some single-player games such as tile games, Sudoku, crossword, etc. The search algorithms assist you to search for a particular position in such games.

Single Agent Pathfinding Problems

The games like 3X3 eight-tile, 4X4 fifteen-tile, and 5X5 twenty-four tile puzzles are single-agent-path-finding challenges. They contain a matrix of tiles with a blank tile. The player is required to rearrange the tiles by sliding a tile either vertically or horizontally into a space with the aim of accomplishing some objective.

The other examples of single agent pathfinding problems are Travelling Salesman Problem, Rubik’s Cube, and Theorem Proving.

Search Terminology

Problem Space − it’s the environment during which the search takes place. (A set of states and set of operators to vary those states)
Problem Instance − it’s Initial state + Goal state.
Problem Space Graph − It represents problem state. States are shown by nodes and operators are shown by edges.
Depth of a drag − Length of a shortest path or shortest sequence of operators from Initial State to goal state.
Space Complexity − the utmost number of nodes that are stored in memory.
Time Complexity − the utmost number of nodes that are created.
Admissibility − A property of an algorithm to always find an optimal solution.
Branching Factor − the typical number of kid nodes within the problem space graph.
Depth − Length of the shortest path from initial state to goal state.

Brute-Force Search Strategies

They are most straightforward, as they do not need any domain-specific knowledge. They work fine with small number of possible states.

Requirements −

State description
A set of valid operators
Initial state
Goal state description

Breadth-First Search

It starts from the basis node, explores the neighboring nodes first and moves towards subsequent level neighbors. It generates one tree at a time until the answer is found. It is often implemented using FIFO queue arrangement. This method provides shortest path to the answer.

If branching factor (average number of child nodes for a given node) = b and depth = d, then number of nodes at level d = b^d.

The total no of nodes created in worst case is b + b² + b³ + … + b^d.

Disadvantage − Since each level of nodes is saved for creating next one, it consumes a lot of memory space. Space requirement to store nodes is exponential.

Its complexity depends on the number of nodes. It can check duplicate nodes.

2.1 1

Depth-First Search

It is implemented in recursion with LIFO stack data structure. It creates the same set of nodes as Breadth-First method, only in the different order.

As the nodes on the single path are stored in each iteration from root to leaf node, the space requirement to store nodes is linear. With branching factor b and depth as m, the storage space is bm.

Disadvantage − This algorithm may not terminate and go on infinitely on one path. The solution to this issue is to choose a cut-off depth. If the ideal cut-off is d, and if chosen cut-off is lesser than d, then this algorithm may fail. If chosen cut-off is more than d, then execution time increases.

Its complexity depends on the number of paths. It cannot check duplicate nodes.

2.2

Bidirectional Search

It searches forward from initial state and backward from goal state till both meet to identify a common state.

The path from initial state is concatenated with the inverse path from the goal state. Each search is done only up to half of the total path.

Uniform Cost Search

Sorting is done in increasing cost of the path to a node. It always expands the least cost node. It is identical to Breadth First search if each transition has the same cost.

It explores paths in the increasing order of cost.

Disadvantage − There can be multiple long paths with the cost ≤ C*. Uniform Cost search must explore them all.

Iterative Deepening Depth-First Search

It performs depth-first search to level 1, starts over, executes a complete depth-first search to level 2, and continues in such way till the solution is found.

It never creates a node until all lower nodes are generated. It only saves a stack of nodes. The algorithm ends when it finds a solution at depth d. The number of nodes created at depth d is b^d and at depth d-1 is b^d-1.

2.3

Comparison of Various Algorithms Complexities

Let us see the performance of algorithms based on various criteria −

Criterion	Breadth First	Depth First	Bidirectional	Uniform Cost	Interactive Deepening
Time	b^d	b^m	b^d/2	b^d	b^d
Space	b^d	b^m	b^d/2	b^d	b^d
Optimality	Yes	No	Yes	Yes	Yes
Completeness	Yes	No	Yes	Yes	Yes

Informed (Heuristic) Search Strategies

To solve large problems with sizable amount of possible states, problem-specific knowledge must be added to extend the efficiency of search algorithms.

Heuristic Evaluation Functions

They calculate the value of optimal path between two states. A heuristic function for sliding-tiles games is computed by counting number of moves that every tile makes from its goal state and adding these number of moves for all tiles.

Pure Heuristic Search

It expands nodes within the order of their heuristic values. It creates two lists, a closed list for the already expanded nodes and an open list for the created but unexpanded nodes.

In each iteration, a node with a minimum heuristic value is expanded, all its child nodes are created and placed within the closed list. Then, the heuristic function is applied to the kid nodes and that they are placed within the open list consistent with their heuristic value. The shorter paths are saved and therefore the longer ones are disposed.

**A * Search**

It is best-known sort of Best First search. It avoids expanding paths that are already expensive, but expands most promising paths first.

f(n) = g(n) + h(n), where

g(n) the cost (so far) to reach the node
h(n) estimated cost to get from the node to the goal
f(n) estimated total cost of path through n to goal. It is implemented using priority queue by increasing f(n).

Greedy Best First Search

It expands the node that is estimated to be closest to goal. It expands nodes based on f(n) = h(n). It is implemented using priority queue.

Disadvantage − It can get stuck in loops. It is not optimal.

Local Search Algorithms

They start from a prospective solution and then move to a neighboring solution. They can return a valid solution even if it is interrupted at any time before they end.

Hill-Climbing Search

It is an iterative algorithm that starts with an arbitrary solution to a drag and attempts to seek out a far better solution by changing one element of the answer incrementally. If the change produces a far better solution, an incremental change is taken as a replacement solution. This process is repeated until there are not any further improvements.

function Hill-Climbing (problem), returns a state that is a local maximum.

inputs: problem, a problem

local variables: current, a node

neighbor, a node

current <-Make_Node(Initial-State[problem])

loop

do neighbor <- a highest_valued successor of current

if Value[neighbor] ≤ Value[current] then

return State[current]

current <- neighbor

end

Disadvantage − This algorithm is neither complete, nor optimal.

Local Beam Search

In this algorithm, it holds k number of states at any given time. At the start, these states are generated randomly. The successors of these k states are computed with the help of objective function. If any of these successors is the maximum value of the objective function, then the algorithm stops.

Otherwise the (initial k states and k number of successors of the states = 2k) states are placed in a pool. The pool is then sorted numerically. The highest k states are selected as new initial states. This process continues until a maximum value is reached.

function BeamSearch( problem, k), returns a solution state.

start with k randomly generated states

loop

generate all successors of all k states

if any of the states = solution, then return the state

else select the k best successors

end

Simulated Annealing

Annealing is the process of heating and cooling a metal to change its internal structure for modifying its physical properties. When the metal cools, its new structure is seized, and the metal retains its newly obtained properties. In simulated annealing process, the temperature is kept variable.

We initially set the temperature high and then allow it to ‘cool’ slowly as the algorithm proceeds. When the temperature is high, the algorithm is allowed to accept worse solutions with high frequency.

Start

Initialize k = 0; L = integer number of variables;
From i → j, search the performance difference Δ.
If Δ <= 0 then accept else if exp(-Δ/T(k)) > random(0,1) then accept;
Repeat steps 1 and 2 for L(k) steps.
k = k + 1;

Repeat steps 1 through 4 till the criteria is met.

End

Travelling Salesman Problem

In this algorithm, the objective is to find a low-cost tour that starts from a city, visits all cities en-route exactly once and ends at the same starting city.

Start

Find out all (n -1)! Possible solutions, where n is the total number of cities.

Determine the minimum cost by finding out the cost of each of these (n -1)! solutions.

Finally, keep the one with the minimum cost.

end

2.4

So, this brings us to the end of blog. This Tecklearn ‘AI – Popular Search Algorithms’ blog helps you with commonly asked questions if you are looking out for a job in Artificial Intelligence. If you wish to learn Artificial Intelligence and build a career in AI or Machine Learning domain, then check out our interactive, Artificial Intelligence and Deep Learning with TensorFlow Training, that comes with 24*7 support to guide you throughout your learning period. Please find the link for course details:

https://www.tecklearn.com/course/artificial-intelligence-and-deep-learning-with-tensorflow/

Artificial Intelligence and Deep Learning with TensorFlow Training

About the Course

Tecklearn’s Artificial Intelligence and Deep Learning with Tensor Flow course is curated by industry professionals as per the industry requirements & demands and aligned with the latest best practices. You’ll master convolutional neural networks (CNN), TensorFlow, TensorFlow code, transfer learning, graph visualization, recurrent neural networks (RNN), Deep Learning libraries, GPU in Deep Learning, Keras and TFLearn APIs, backpropagation, and hyperparameters via hands-on projects. The trainee will learn AI by mastering natural language processing, deep neural networks, predictive analytics, reinforcement learning, and more programming languages needed to shine in this field.

Why Should you take Artificial Intelligence and Deep Learning with Tensor Flow Training?

According to Paysa.com, an Artificial Intelligence Engineer earns an average of $171,715, ranging from $124,542 at the 25th percentile to $201,853 at the 75th percentile, with top earners earning more than $257,530.
Worldwide Spending on Artificial Intelligence Systems Will Be Nearly $98 Billion in 2023, According to New IDC Spending Guide at a GACR of 28.5%.
IBM, Amazon, Apple, Google, Facebook, Microsoft, Oracle and almost all the leading companies are working on Artificial Intelligence to innovate future technologies.

What you will Learn in this Course?

Introduction to Deep Learning and AI

What is Deep Learning?
Advantage of Deep Learning over Machine learning
Real-Life use cases of Deep Learning
Review of Machine Learning: Regression, Classification, Clustering, Reinforcement Learning, Underfitting and Overfitting, Optimization
Pre-requisites for AI & DL
Python Programming Language
Installation & IDE

Environment Set Up and Essentials

Installation
Python – NumPy
Python for Data Science and AI
Python Language Essentials
Python Libraries – Numpy and Pandas
Numpy for Mathematical Computing

More Prerequisites for Deep Learning and AI

Pandas for Data Analysis
Machine Learning Basic Concepts
Normalization
Data Set
Machine Learning Concepts
Regression
Logistic Regression
SVM – Support Vector Machines
Decision Trees
Python Libraries for Data Science and AI

Introduction to Neural Networks

Creating Module
Neural Network Equation
Sigmoid Function
Multi-layered perception
Weights, Biases
Activation Functions
Gradient Decent or Error function
Epoch, Forward & backword propagation
What is TensorFlow?
TensorFlow code-basics
Graph Visualization
Constants, Placeholders, Variables

Multi-layered Neural Networks

Error Back propagation issues
Drop outs

Regularization techniques in Deep Learning

Deep Learning Libraries

Tensorflow
Keras
OpenCV
SkImage
PIL

Building of Simple Neural Network from Scratch from Simple Equation

Training the model

Dual Equation Neural Network

TensorFlow
Predicting Algorithm

Introduction to Keras API

Define Keras
How to compose Models in Keras
Sequential Composition
Functional Composition
Predefined Neural Network Layers
What is Batch Normalization
Saving and Loading a model with Keras
Customizing the Training Process
Using TensorBoard with Keras
Use-Case Implementation with Keras

GPU in Deep Learning

Introduction to GPUs and how they differ from CPUs
Importance of GPUs in training Deep Learning Networks
The GPU constituent with simpler core and concurrent hardware
Keras Model Saving and Reusing
Deploying Keras with TensorBoard

Keras Cat Vs Dog Modelling

Activation Functions in Neural Network

Optimization Techniques

Some Examples for Neural Network

Convolutional Neural Networks (CNN)

Introduction to CNNs
CNNs Application
Architecture of a CNN
Convolution and Pooling layers in a CNN
Understanding and Visualizing a CNN

RNN: Recurrent Neural Networks

Introduction to RNN Model
Application use cases of RNN
Modelling sequences
Training RNNs with Backpropagation
Long Short-Term memory (LSTM)
Recursive Neural Tensor Network Theory
Recurrent Neural Network Model

Application of Deep Learning in image recognition, NLP and more

Real world projects in recommender systems and others

Got a question for us? Please mention it in the comments section and we will get back to you.

733