{"id":5880,"date":"2018-01-24T08:50:51","date_gmt":"2018-01-24T08:50:51","guid":{"rendered":"https:\/\/data-flair.training\/blogs\/?p=5880"},"modified":"2025-07-25T16:07:10","modified_gmt":"2025-07-25T10:37:10","slug":"popular-search-algorithms","status":"publish","type":"post","link":"https:\/\/data-flair.training\/blogs\/popular-search-algorithms\/","title":{"rendered":"Popular Search Algorithms in Artificial Intelligence"},"content":{"rendered":"
\n
\n

In this blog, we will study Popular Search Algorithms in Artificial Intelligence. Also, we will lesrn all most popular techniques, methods, algorithms and searching techniques. We will use Popular Search Algorithms examples and images for the better understanding.<\/p>\n<\/div>\n

\n

Introduction to Popular Search Algorithms in AI<\/h3>\n<\/div>\n
\n
In the artificial algorithm, to solve the problem we use the searching technique. The search algorithms help you to search for a particular position in such games.<\/div>\n<\/div>\n
\n

Single Agent Pathfinding Problems<\/h3>\n<\/div>\n
\n
There are different types of games. Such as 3X3 eight-tile, 4X4 fifteen-tilepuzzles are single-agent-path-finding challenges. As they are consisting of a matrix of tiles with a blank tile.<\/div>\n
<\/div>\n
Thus, to arrange the tiles by sliding a tile either vertically<\/span> or horizontally<\/span> into a blank space. Also, with the aim of accomplishing some objective<\/span>.<\/div>\n<\/div>\n
\n
\u00a0<\/strong><\/div>\n<\/div>\n
\n
For example:<\/strong><\/div>\n<\/div>\n
\n
Travelling Salesman Problem, Rubik\u2019s Cube, and Theorem Proving<\/div>\n<\/div>\n
\n

Search Algorithms Terminology<\/h3>\n<\/div>\n
a. Problem Space<\/strong><\/div>\n
\n
Basically<\/span>, it is the environment in which the search takes place. (A set of states and set of operators to change those states)<\/div>\n<\/div>\n
<\/div>\n
\n
b. Problem Instance<\/strong><\/div>\n
It is a result of Initial state + Goal state.<\/div>\n<\/div>\n
<\/div>\n
\n
c. Problem Space Graph<\/strong><\/div>\n
We use it to represent problem state. Also, we use nodes to show states and operators are shown by<\/span> edges.<\/div>\n<\/div>\n
<\/div>\n
\n
d. The depth of a problem<\/strong><\/div>\n
We can define a length of the shortest path.<\/div>\n<\/div>\n
<\/div>\n
\n
e. Space Complexity<\/strong><\/div>\n
We can calculate it as the maximum<\/span> number of nodes that are stored<\/span> in memory.<\/div>\n<\/div>\n
<\/div>\n
\n
f. Time Complexity\u00a0<\/strong><\/div>\n
It is defined<\/span> as the maximum<\/span> number of nodes that are created<\/span>.<\/div>\n<\/div>\n
<\/div>\n
\n
g. Admissibility<\/strong><\/div>\n
We can say it as a property of an algorithm that is used<\/span> to find always an optimal solution.<\/div>\n<\/div>\n
<\/div>\n
\n
h. Branching Factor\u00a0<\/strong><\/div>\n
We can calculate it as the average number of child nodes in the problem space graph.<\/div>\n<\/div>\n
<\/div>\n
\n
i. Depth<\/strong><\/div>\n
Length of the shortest path from an initial state to the goal state.<\/div>\n<\/div>\n
\n

Brute-Force Search Strategies<\/h3>\n<\/div>\n
This strategy doesn\u2019t require<\/span> any domain-specific knowledge. Thus it\u2019s so simple strategy. Hence, it works very smoothly<\/span> and fine with a small number of possible states.<\/div>\n
<\/div>\n
\n
Requirements for Brute Force Algorithms<\/strong><\/div>\n
<\/div>\n<\/div>\n
\n
a. State description<\/div>\n<\/div>\n
\n
b. A set of valid operators<\/div>\n<\/div>\n
\n
c. Initial state<\/div>\n<\/div>\n
\n
d. Goal state description<\/div>\n<\/div>\n
\n

Breadth-First Search Algorithm in AI<\/h3>\n<\/div>\n
\n
Basically<\/span>, we have to start searching for the root node. And continue through neighboring nodes first. Further, moves towards next level of nodes. Moreover, till the solution is found<\/span>, generates one tree at a time.<\/div>\n<\/div>\n
<\/div>\n
\n
As this search can be implemented<\/span> using FIFO queue data structure. This method provides the shortest path to the solution.<\/div>\n
<\/div>\n<\/div>\n
\n
FIFO(First in First Out).<\/div>\n<\/div>\n
<\/div>\n
\n
If branching factor (average number of child nodes for a given node) = b and depth = d, the number of nodes at level d = bd.<\/div>\n<\/div>\n
\n
The total no of nodes created in worst case is b + b2 + b3 + \u2026 + bd.<\/div>\n<\/div>\n
<\/div>\n
\n
Disadvantage<\/strong><\/div>\n<\/div>\n
\n