See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/333262471

Comparative Analysis of Search Algorithms

Conference Paper · June 2018

CITATIONS READS

9 21,508

2 authors:

Ronit Patel Maharshi Pathak

Charotar University of Science and Technology Lakehead University Thunder Bay Campus
2 PUBLICATIONS 19 CITATIONS 1 PUBLICATION 9 CITATIONS

SEE PROFILE SEE PROFILE

All content following this page was uploaded by Ronit Patel on 22 May 2019.

The user has requested enhancement of the downloaded file.

 International Journal of Computer Applications (0975 – 8887)
Volume 179 – No.50, June 2018

Comparative Analysis of Search Algorithms

Maharshi J. Pathak Ronit L. Patel Sonal P. Rami

Student, B.Tech (IT) Student, B.Tech (IT) Assistant Professor (IT)
CSPIT, CHARUSAT CSPIT, CHARUSAT CSPIT, CHARUSAT
Anand, Gujarat, India Anand, Gujarat, India Anand, Gujarat, India

ABSTRACT 2. SEARCH ALGORITHM

Nowadays many artificial intelligence search algorithms are APPROACHES
available to figure out the problem of shortest path finding.
The paper presents the detailed study of informed search and 2.1 Uninformed search
uninformed search techniques. The paper focuses more Uninformed Search is a blind search or brute force search
towards uninformed search strategies such as BFS, DFS, and which includes search techniques such as Breadth First
UCS and informed search strategies like A*, and Best First Search, Depth First Search, Uniform Cost Search, Iterative
Search. The paper includes working of search techniques, Deepening, and Bidirectional Search. Uninformed search does
their merits, and demerits, where these algorithms are not contain any information about the number of steps to
applicable, also open and closed list for each algorithm are reach from current state to goal state. The uniformed search
shown. At last comparison of search techniques based on will consider the path which is most promising at that
complexity, optimality and completeness are presented in moment, it will not consider the optimum path to reach the
tabular form. goal.

Keywords 2.2 Informed search

Artificial intelligence, informed search, search algorithms, Informed search is Heuristic search which uses heuristic
shortest path algorithms, uninformed search. function (To estimate how close a given state is from goal
state) to solve a problem. Informed search uses generate and
1. INTRODUCTION test approach. It includes hill climbing, steepest hill climbing,
Artificial Intelligence is a study of "How to make computer to A*, AO*, and Best First Search algorithms. Informed search
think like a human". Artificial Intelligence is a broad area of is more efficient than uninformed search. In informed search
research. As shown in Figure 1 Artificial Intelligence has sub heuristic function is used as a model that will lead us to the
areas like Machine learning and Deep learning. The fields goal state. The informed search will not traverse search tree
such as Artificial intelligence, Machine Learning, Deep blindly. It will consider the next node to traverse based on
Learning, and Data Science are inter-related with each other. some evaluation function (Heuristic Function) to reach the
goal state from current state.

3. WORKING OF SEARCH
TECHNIQUES
3.1 BFS (Breadth first search)
In Breadth First Search all nodes are expanded level by level.
It first expands all the nodes at first level in the search tree,
then expands all the nodes of the second level and this way it
reaches the goal. In Breadth First Search the frontier is
actualized as a queue which works as First In First Out
(FIFO). It is a poor strategy when all solution has a long way
length or then again there is some heuristic information
accessible [1]. It is not utilized when memory requirement is
high. Time complexity is O(bd) and space complexity is
O(bd), where b is branching factor and d is solution depth. For
Fig 1: Co-relation of artificial intelligence with other fields example, consider a graph (Figure 2). Table 1 shows open list
Artificial intelligence includes Problem Solving (Search and closed list for BFS. The open list is set of nodes yet to
techniques), Knowledge and Reasoning (Resolution, explore and closed list is set of nodes already been explored.
Knowledge Representation, Fuzzy Logic), Adversarial At level 0 node 1 is expanded first. Children of node 1-2, 3,
Search: Game Playing (Minimax Algorithm, Alpha-Beta and 4 are added to the queue. Then according to First In First
Pruning), Uncertain Knowledge and Reasoning (Uncertainty, Out approach node 2 is expanded and child of node 2-6 is
Probabilities, Bayesian Networks), and Expert system. The added to the queue. This way search reaches the goal state.
following paper presents more about problem-solving
techniques in artificial intelligence. There are two problem-
solving techniques in artificial intelligence, uninformed
search, and informed search. The paper focuses more on BFS,
DFS, UCS, A*, and Best First Search.

40
 International Journal of Computer Applications (0975 – 8887)
Volume 179 – No.50, June 2018

and child of node 2-6 is added to the stack. Then node 6 is

expanded. As it does not have any child it will backtrack to
node 3 and node 3 will be expanded. These way nodes in the
depth are expanded and search reaches the goal state.
Table 2. Open and closed list for DFS
OPEN LIST CLOSED LIST
1 1
4, 3, 2 2
4, 3, 6 6
4, 3 3
4, 5 5
4, 7 7
4, 8-Goal state -

3.2.1 Depth First Search is applicable when:

Fig 2: Graph for BFS and DFS  Memory is limited.
Table 1. Open and closed list for BFS  The order of the neighbours of a node are added to
OPEN LIST CLOSED LIST the stack can be tuned so that solutions are found on
the first attempt [1].
1 1
 It is a poor technique when it is conceivable to get
2, 3, 4 2
captured in endless ways, this happens when the
3, 4, 6 3 graph is endless or at the point when there are
cycles in the graph.
4, 6, 5 4
3.2.2 Applications:
6, 5, 7 6  Identifying loops in a graph.
5, 7 5  Identifying components which are strongly
connected in a graph.
7 7  Finding the solution of the puzzle in which only one
8–Goal state - solution exists.

3.3 UCS (Uniform Cost Search)

3.1.1 Breadth First Search is applicable when: Uniform Cost Search expand the node with low-cost path. It is
 You need to discover the solution of problem implemented using the priority queue. To calculate cost of
containing the least curves. every node, consider this equation, c(m) = c(n) + c(n, m).
 Few solutions may exist, and at least one has a short where c(m) is the cost of the current node, c(n) is the cost of
path length [1]. the previous node, and C (n, m) is the weight of the edge. The
successor can be removed which are already in a queue with
 Memory is not an issue.
higher cost. Time complexity is O(b└1+C*/e┘) and space
3.1.2 Applications: complexity is O(b└1+C*/e┘), where C is the optimal solution
cost and each activity costs at least ε. For example, consider
 For unweighted graph minimum spanning tree and
graph (Figure 3). Open list and closed list for UCS are shown
shortest path.
in Table 3.
 Shared network.
 Social Networking Websites.
 Global Positioning System Navigation systems.
 For testing whether the graph is bipartite or not.

3.2 DFS (Depth First Search)

In Depth First Search expansion starts from the source node
and goes up to the deepest unexpanded node in a search of
goal node. In Depth First Search the frontier is actualized as a
stack which works as Last In First Out (LIFO). It is also
known as recursive algorithm because it is implemented using
the stack. Time complexity is O(bm) and space complexity is
O(bm), where b is branching factor and m is maximum depth.
For example, consider a graph (Figure 2). Table 2 shows open
list and closed list for DFS. At level 0 node 1 is expanded
first. Children of node 1-4, 3, 2 are added to the stack. Then Fig 3: Graph for UCS
according to Last In First Out approach node 2 is expanded

41
 International Journal of Computer Applications (0975 – 8887)
Volume 179 – No.50, June 2018

Table 3. Open and Closed list for UCS 6. Repeat step 2 to 5, if the current working node is not
OPEN LIST CLOSED LIST goal state.
7. The closed list gives the shortest path and the value
1(0) 1(0) of last cost function obtained gives the optimal cost.
2(2), 5(1) 5(1)
2(2), 9(2) 2(2)
9(2), 6(5), 3(3) 9(2)
6(5), 3(3), 10(10) 3(3)
6(5), 10(10), 4(5) 6(5)
10(10), 4(5), 7(6), 10(9) 4(5)
7(6), 10(9), 8(6) 7(6)
10(9), 8(6), 11(16) 8(6)
10(9), 11(16), 12(21) 10(9)
11(16), 12(21), 11(12) 11(12)
Fig 4: Graph for A*
12(21), 12(13)-Goal state -
Table 4. Open and Closed list for A*
OPEN LIST CLOSED LIST
3.3.1 Uniform Cost Search is applicable when: 1(12) 1(12)
 Space requirement is less.
 Intelligence is not required or when evaluation 2(12), 5(13) 2(12)
function (Heuristic function) is not required.
5(13), 3(19), 6(12) 6(12)
3.3.2 Applications: 5(13), 3(19) 5(13)
 Solving Maze problem.
3(19), 7(17), 10(13), 9(14) 10(13)
 Path finding.
3(19), 7(17), 9(14), 11(13) 11(13)
3.4 A*
A* algorithm joins highlight of Uniform Cost Search and pure 3(19), 7(17), 9(14), 12(13)-Goal -
heuristic search to productively calculate optimal solution [1]. state
For computing cost of every node, consider this equation,
f(m) = c(m) + h(m), where c(m) = c(n) + c(n, m), h(m) is
heuristic function. f(m) compute the most reduced aggregate 3.4.1 Applications:
cost. Most reduced value of f is chosen at each node for  Traffic navigation system [4].
expansion. Euclidean distance (used when allowed to move in
 Games.
any direction), Manhattan distance (used when allowed to
move in only four directions-right, left, top, and bottom) or  Finding shortest path.
Diagonal distance (used when allowed to move in eight
directions, same as the movement of king in chess) are used as  Real-time path re-planning of an unmanned surface
vehicle avoiding underwater obstacles [5].
Heuristic function. If the value of f of two nodes is same then
the node having lowest h value is chosen for expansion. The
calculation ends when an objective is decided for expansion.
3.5 Best First Search (Greedy search)
Best First Search is a merger of Breadth First Search and
Admissible heuristic function (h(n) ≤ h*(n)) brings visited
Depth First Search. Best First Search is implemented using
node back from the closed list to open list to get an optimal
the priority queue. The advantage of Depth First Search is that
solution. Time complexity is O(bd) and space complexity is
it gives a solution without calculating all node. while Breadth
O(bd), where b is branching factor and d is solution depth [2].
First Search arrives at a solution without search guaranteed
For example, consider graph (Figure 4). Open and closed list
that the procedure does not get caught. Best First Search,
associated with the example is shown in table 4.
being a mixer of these two, licenses exchanging between
Steps to reach goal state from source [3]: paths. At each stage the nodes among the created ones, the
best appropriate node is chosen for facilitating expansion,
1. Start from the source node, add it open list. might be this node have a place to a similar level or different,
2. Explore all the nodes which are adjacent to the node hence can flip between Depth First and Breadth First Search
which is in open list. [3]. It is also known as greedy search. Time complexity is
3. Calculate the cost for all the nodes discovered in O(bd) and space complexity is O(bd), where b is branching
step 2, and place them in open list in increasing factor and d is solution depth [2].
order based on cost.
4. Move current working node, from the open list to
closed list.
5. The first node in open list will become the current
working node.

42
 International Journal of Computer Applications (0975 – 8887)
Volume 179 – No.50, June 2018

5. CONCLUSION
We conclude that heuristic search is more efficient and
acceptable than blind search. From the example explained
above (open and closed list for UCS and A*), it is clear that in
UCS 11 nodes are required to expand to reach the goal state.
While in A* only 6 nodes are required to expand to reach the
goal state. Also, UCS is more time consuming then A*. So A*
is more efficient and optimal than UCS. Also when all means
costs are similar, instead of UCS, BFS is optimal because it
always expands the shallowest unexpanded node. Hence
heuristic search finds an optimal solution then blind search.

6. REFERENCES
[1] Deepika Garg, COMPARATIVE STUDY OF
VARIOUS SEARCHING ALGORITHMS, National
Fig 5: Example of Best First Search Conference on Innovative Trends in Computer Science
Engineering (ITCSE-2015) held at BRCMCET, Bahal on
3.5.1 Applications: 4th April 2015.
 Games. [2] Chandel, and Manu Sood, Searching and Optimization
 Web crawlers. Techniques in Artificial Intelligence: A Comparative
Study & Complexity Analysis, International Journal of
4. COMPARISON OF VARIOUS Advanced Research in Computer Engineering &
Technology (IJARCET) Volume 3 Issue 3, March 2014.
SEARCH ALGORITHMS
The performance of the algorithm is evaluated based on four [3] Mr. Girish P Potdar, and Dr.R C Thool, COMPARISON
parameters as follows: OF VARIOUS HEURISTIC SEARCH TECHNIQUES
FOR FINDING SHORTEST PATH, International
1. Time complexity: Time taken by the algorithm to
Journal of Artificial Intelligence & Applications (IJAIA),
find a solution.
Vol. 5, No. 4, July 2014.
2. Space complexity: Memory required by the
[4] LIU Jingang, and LIU Yujun, Application of A*
algorithm to perform the search.
algorithm in Traffic Navigational System, Information
3. Optimality: Solution provided by the algorithm will Engineering and Electronic Commerce (IEEC), 2010 2nd
always be optimal or not. International Symposium on. IEEE, 2010.
4. Completeness: Is that calculation ensured to [5] Phanthong, Thanapong, et al. Application of A*
discover an answer when there would one say one algorithm for real-time path re-planning of an unmanned
is? This section is a Boolean marker regardless of surface vehicle avoiding underwater obstacles. Journal of
whether the search algorithm is thorough. Marine Science and Application 13.1 (2014): 105-116.
Table 5. Comparison of search algorithm [6] R.E. Korf, Scientific Paper on Artificial Intelligence
Algorithm BFS DFS UCS A* BFS Search Algorithms, University of California Los
(greed Angeles, June 1999.
y [7] Eric A Hansen, and Rong Zhou, Anytime Heuristic
search Search, Journal of Artificial Intelligence Research 28, pp
) 267-287, 2007.
Time O(bd O(bm O(b└1+C*/e O(bd O(bd) [8] Anne L. Gardner, Search: An Overview, AI magazine,
Complexity ) ) ┘) ) Vol. 2, Number 1. Sept. 1980.
Space O(bd O(bm O(b└1+C*/e O(bd O(bd)
[9] A.Martelli, On the search complexity of admissible
Complexity ) ) ┘) )
search algorithms, Al, Vol. 8, pp 1-13, 1977.
Optimality Yes No Yes Yes No
[10] R.K.Ahuja, K. Mehlhorn, J.B.Orlin and R.E.Tarjan,
Completene Yes No Yes Yes Yes Faster algorithms for shortest path algorithms, Journal of
ss the Association for Computing Machinery,Vol. 37, No.
2, pp 213-223, April 1990.

43
IJCATM : www.ijcaonline.org

View publication stats