CS 611: ARTIFICIAL

INTELLIGENCE

B. I. Ya’u, August 26, 2021

Problem Solving through
Searching
 Introduction
• Searching forms the most universal
way of solving problems in AI.

• Both problem-solving and rational

agents use search algorithms and
strategies to solve a particular
problem and give the best result.

• Problem-solving agents are goal-

based agents and they rely on the
atomic representation.
 Properties of Search Algorithms
• Completeness- we say a search algorithm is complete if it can return a solution if
there is at least a single solution for any single input in the search space. 


• Optimality- a solution is said to be optimal if it is guaranteed the best solution

(lowest path cost) found among all the other solutions. 


• Time Complexity- this is a measure of the amount of time taken to complete a

task. 


• Space Complexity- this denotes the maximum amount of space that is required at
any particular point during the search. 

 Types of Search Algorithms

(1) Informed search algorithms

(2) Uninformed (Blind) search

algorithms
 Uninformed Search
• An uninformed search is a type of search that lacks domain knowledge like
location and closeness of the goal.

• Its operation is based on a brute-force way since it only has information on

how to traverse the tree and how to identify the leaf and the goal nodes.

• In uninformed search, the search tree is searched without information

about the search space such as the initial state operators and the test for
the goal, hence, it is referred to as a blind search.

• Each node of the tree is examined until the goal node is found.
 Types of Uninformed Search Strategies

• Breadth-first Search

• Uniform Cost Search

• Depth-first Search

• Iterative Deepening Depth-first

Search

• Bidirectional Search
 Breadth-first Search
• This is a common strategy used for traversing trees and graphs. The search in
this algorithm follows a breadth-wise approach, hence, it is known as the
breadth-first search.

• The algorithm begins the search process from the root node of the tree and
then expands the successor node at the current level before it can move to
the nodes at the next level.

• The breadth-first algorithm is a good example of a general-graph search

algorithm.

• To implement this algorithm, we use the FIFO (First In First Out) queue data
structure.
Advantages and Disadvantages of BFS
Advantages:
Disadvantages:

• It guarantees to find a solution if • A huge amount of memory is

it exists.
required for the algorithm to run.
This is because every tree level
• If the problem has many must be saved into the memory
solutions, the algorithm will before expansion to the next
return the solution that can be level.

achieved via a minimum number

of steps.
• The algorithm takes a very long
time if the solution is located far
from the root node of the tree. 

 BFS Algorithm
• A standard BFS implementation puts each vertex of the graph into one of two categories:

1. Visited

2. Not Visited

• The purpose of the algorithm is to mark each vertex as visited while avoiding cycles.

• The algorithm works as follows:

1. Start by putting any one of the graph's vertices at the back of a queue.

2. Take the front item of the queue and add it to the visited list.

3. Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to the back of
the queue.

4. Keep repeating steps 2 and 3 until the queue is empty.

• The graph might have two different disconnected parts so to make sure that we cover every vertex, we can also run
the BFS algorithm on every node
 BFS Example
• Let's see how the Breadth First
Search algorithm works with an
example. We use an undirected
graph with 5 vertices.

• We start from vertex 0, the BFS

algorithm starts by putting it in
the Visited list and putting all its
adjacent vertices in the stack.
BFS Example Cont.

• Next, we visit the element at the

front of queue i.e. 1 and go to its
adjacent nodes. Since 0 has
already been visited, we visit 2
instead.

• Vertex 2 has an unvisited

adjacent vertex in 4, so we add
that to the back of the queue
and visit 3, which is at the front
of the queue.
BFS Example Cont.

• Only 4 remains in the queue

since the only adjacent node of 3
i.e. 0 is already visited. We visit
it.

• Since the queue is empty, we

have completed the Breadth
First Traversal of the graph.
 # BFS algorithm in Python

BFS Pseudocode import collections

# BFS algorithm
def bfs(graph, root):

visited, queue = set(), collections.deque([root])

visited.add(root)

while queue:

# Dequeue a vertex from queue

vertex = queue.popleft()
print(str(vertex) + " ", end="")

# If not visited, mark it as visited, and

# enqueue it
for neighbour in graph[vertex]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)

if __name__ == '__main__':
graph = {0: [1, 2], 1: [2], 2: [3], 3: [1, 2]}
print("Following is Breadth First Traversal: ")
bfs(graph, 0)
 BFS Algorithm Complexity BFS Algorithm Applications

• The time complexity of the BFS 1.To build index by search index

algorithm is represented in the

form of O(V + E), where V is the 2. For GPS navigation

number of nodes and E is the

number of edges.
3. Path finding algorithms

• The space complexity of the 4. In Ford-Fulkerson algorithm to

algorithm is O(V).
find maximum flow in a network

5.Cycle detection in an undirected

graph

6. In minimum spanning tree

 Uniform-cost Search Algorithm
• This is a search algorithm used to traverse a weighted tree or a graph. The algorithm is suitable
when there is a different cost for every edge.

• The major goal of this type of search is to find that leads from the root node to the goal node with
the lowest cumulative cost.

• The uniform-cost search expands the nodes based on the path cost from the root node. This type
of search can be used to solve any tree/graph where there is a demand for optimal cost.

• The uniform-cost search algorithm is implemented using the priority queue data structure. The
lowest cumulative cost is given a priority. If all edges have similar path costs, the uniform-cost
search becomes the same as BFS.

• The major advantage associated with the uniform-cost search algorithm is that it is optimal as the
least cost path is chosen at every state.

• The major disadvantage associated with this type of search is that it doesn’t care about the number
of steps involved in the search, but it is only interested in the path costs. This may lead the
algorithm to an infinite path.
Example of Uniform Cost Search
• Consider the below example, where we
need to reach any one of the destination
node{G1, G2, G3} starting from node S.
Node{A, B, C, D, E and F} are the
intermediate nodes. Our motive is to find
the path from S to any of the destination
state with the least cumulative cost.
Each directed edge represents the
direction of movement allowed through
that path, and its labelling represents the
cost is one travels through that path.
Thus Overall cost of the path is a sum of
all the paths.

• For e.g. – a path from S to G1- {S->A ->

G1} whose cost is SA +AG1 = 5 + 9 = 14
 Example UCS
• Step 1-
• We will start with start node and check
if we have reached any of the
destination nodes, i.e. No thus
continue.

• Step 2– We reach all the nodes that

can be reached from S I .eA, B, D. And
Since node S has been visited thus
added to the visited List. Now we
select the cheapest path first for further
expansion, i.e. A
Example UCS Cont.
• Step 3 – Node B and G1 can be S,A
reached from A and since node A is
visited thus move to the visited list.

• Since G1 is reached but for the

optimal solution, we need to consider
every possible case; thus, we will
expand the next cheapest path, i.e. S-
>D.

• Step 4– Now node D has been visited

thus it goes to visited list and now
since we have three paths with the
same cost, we will choose
alphabetically thus will expand node B
S,A,D
Example UCS Cont.
• Step 5-: From B, we can only reach S,A,D,B
node C. Now the path with minimum
weight is S->D->C, i.e. 8. Thus expand
C. And B has now visited node.

• Step 6:- From C we can reach G2 and

F node with 5 and 7 weights
respectively.

• Since S is present in the visited list

thus, we are not considering the C->S
path.

• Now C will enter the visited list. Now

the next node with the minimum total
path is S->D->E, i.e. 8. Thus we will
expand E.
S,A,D,B,C
 S,A,D,B,C,E
Example UCS Cont.
• Step 7:- From E we can reach only G3. E will move to the
visited list.

• Step 8 – In the last, we have 6 active paths

• . S->B – B is in the visited list; thus will be marked as a dead

end.

• Same for S->A->B->C – C has already been visited thus is

considered a dead end.

• Out of the remaining

S->A->G1

S->D->C->G2

S->D->C->F

S->D->E->G3

• Minimum is S->D->C->G2

• And also, G2 is one of the destination nodes. Thus, we found

our path.
In this way we can find the path with the minimum cumulative cost from a start node to ending node – S->D->C->G2 with cost total cost as 13(marked with green
colour).
Advantages and Disadvantages of Uniform Cost Search
Advantages Disadvantage

• It helps to find the path with the • The open list is required to be
lowest cumulative cost inside a kept sorted as priorities in priority
weighted graph having a different queue needs to be maintained.

cost associated with each of its

edge from the root node to the • The storage required is
destination node.
exponentially large.

• It is considered to be an optimal • The algorithm may be stuck in an

solution since, at each state, the infinite loop as it considers every
least path is considered to be possible path going from the root
followed.
node to the destination node.
 Informed Search
• Informed search algorithms rely on domain knowledge during the search. The
algorithms have information about the problem, hence, they use it during the
search.

• This means that informed search strategies are able to find the solution more
efficiently compared to the uninformed search strategies.

• The informed search is also known as heuristic search.

• A heuristic refers to a way that may not always guarantee to find the best
solutions but it guarantees to find a good solution within a good time.

• With an informed search, one can solve a complex problem that cannot be solved
in any other way.

• The travelling salesman problem is an example of an informed search strategy.

Best-first Search Algorithm (Greedy Search)
• The greedy best-first search algorithm works by selecting the path that seems
to be the best at that particular moment.

• It combines both the BFS and DFS algorithms.

• It relies on the search and a heuristic function.

• The best-first search helps us combine the benefits of BFS and DFS
algorithms.

• The BFS helps us choose the most promising node at every step. We expand
the node that is very close to the goal node and the heuristic function is used
to estimate the closest cost.

• To implement the greedy best first search, we use the priority queue.
Advantages and Disadvantages of Greedy Search Algorithm

Advantages Disadvantages

• The algorithm can enjoy the • In the worst case scenario, this
benefits of both BFS and DFS algorithm may act line an
algorithms.
unguided depth-first search.

• It is a more efficient algorithm • It is not an optimal algorithm.

compared to the DFS and BFS

algorithms.
• It may create an infinite loop just
like the DFS algorithm.
 A* Search
• The A* search is the most popular form of best-first search.

• It relies on the cost and a heuristic function h(n) to reach the goal node n from the
start state g(n).

• It combines the features of a greedy best- first search and UCS, making it
possible to solve problems more efficiently.

• The A* search uses a heuristic function to find the shortest path through the
search space.

• The algorithm is known to expand a less search tree and it provides an optimal
solution faster.

• In A*, we use both the search heuristic and the cost in order to reach the goal
node.
Advantages and Disadvantages of A* Search Algorithm
Advantages Disadvantages

• It is an optimal and complete • The algorithm has some issues

algorithm.
related to complexity.

• It is the best search algorithm of • It works based on heuristics and

all search algorithms.
approximations, and it does not
always generate the shortest path.

• The algorithm is applicable to

complex problems.
• It requires a huge amount of
memory becomes it keeps all the
nodes in the memory. This makes
it impractical for a number of
large-scale problems.
End of the Slides