21CSC206T
ARTIFICIAL INTELLIGENCE
UNIT – 2
Dr J Faritha Banu
Department of CSE
Basic introduction to stacks, queues,
trees and graphs
• Primitive Data Structures
• These are the predefined way of storing data in the system.
• All sets of operations are pre-defined.
• Ex: Char, int, float, double are examples of primitive data
structures.
• Non-Primitive Data Structures
• The data structures which are designed using primitive data
structures are called non-primitive data structures.
• They are used to store a collection of data. It can be
categorized into two parts:
1. Linear data structure
2. Non-Linear data structure
Basic introduction to stacks, queues,
trees and graphs
• Linear Data Structure
• Data structures in which elements are
arranged sequentially or linearly and
linked one after another are called linear
data structures.
• Stacks
• The stack is a data structure following the
LIFO(Last In, First Out) principle.
Basic introduction to stacks, queues,
trees and graphs
• Queues
• The queue is a data structure following the FIFO(First In, First
Out) principle.
Basic introduction to stacks, queues,
trees and graphs
• Non-Linear Data Structure
Data structures in which elements are not arranged
sequentially are called non-linear data structures.
• Trees
• A tree is a hierarchical data structure that stores the
information naturally in a hierarchical style.
Basic introduction to stacks, queues,
trees and graphs
• Graphs
• A graph is a set of objects where some pairs of objects are
connected by links. The interconnected objects are represented
by points termed as vertices, and the links that connect the
vertices are called edges.
Search
• Searching is the universal technique of problem solving in
Artificial Intelligence
• A search problem consists of:
– A State Space. Set of all possible states where you can be.
– A Start State. The state from where the search begins.
– A Goal Test. A function that looks at the current state
returns whether or not it is the goal state.
– The Solution to a search problem is a sequence of actions,
called the plan that transforms the start state to the goal
state.
7
Search Problem Components
• Search tree: A tree representation of search problem is called
Search tree. The root of the search tree is the root node which is
corresponding to the initial state.
• Actions: It gives the description of all the available actions to the
agent.
• Transition model: A description of what each action do, can be
represented as a transition model.
• Path Cost: It is a function which assigns a numeric cost to each
path.
• Solution: It is an action sequence which leads from the start
node to the goal node.
• Optimal Solution: If a solution has the lowest cost among all
solutions.
8
General Search Strategies
•Blind search → traversing the •Heuristic search → search
search space until the goal process takes place by
nodes is found (might be doing traversing search space with
exhaustive search). applied rules (information).
•Techniques: Greedy Best First
•Techniques : Breadth First,
Search, A* Algorithm
Depth first, Depth Limited,
Iterative Deepening search, •There is no guarantee that
Uninform Cost search. solution is found.
•Guarantees solution.
General Search Algorithm
10
Examples of Search Algorithm
• TSP
• 8 Puzzle problem
• Tic Tac Toe
• N-queen problem
• Tower of Hanoi
• Water Jug Problem
• Blocks World
• Vacuum Cleaner
11
Vacuum Cleaner
12
8 Puzzle Problem
13
Parameters for Search Evaluation
• Completeness: Is the algorithm guaranteed to find a solution if
there exist one?
• Optimality: Does the algorithm find the optimal solution?
• Time complexity: How long does it take for the algorithm to
find a solution?
• Space complexity: How much memory is consumed in finding
the solution?
14
Uninformed and Heuristic Search Strategies
• Based on the information about the problem available for the
search strategies, the search algorithms are classified into
uninformed (Blind) and informed (or heuristic) search algorithms.
• For the uninformed search algorithms, the strategies have no
additional information about the states beyond that provided by
the problem definition. Generate successors and differentiate
between goal and non-goal states.
• Strategies that know whether one non-goal state
is more promising than the other is called informed search
strategies or heuristic search strategies.
15
Uninformed Search
• The uninformed search does not contain any domain knowledge such
as closeness, the location of the goal.
• It operates in a brute-force way as it only includes information about
how to traverse the tree and how to identify leaf and goal nodes.
• Uninformed search applies a way in which search tree is searched
without any information about the search space like initial state
operators and test for the goal, so it is also called blind search.
• It examines each node of the tree until it achieves the goal node.
16
Uninformed Search methods
17
BFS
• Breadth-first search is the most common search strategy for
traversing a tree or graph. This algorithm searches
breadthwise in a tree or graph, so it is called breadth-first
search.
• BFS algorithm starts searching from the root node of the tree
and expands all successor node at the current level before
moving to nodes of next level.
• The breadth-first search algorithm is an example of a general-
graph search algorithm.
• Breadth-first search implemented using FIFO queue data
structure.
18
BFS - Example
19
pseudocode to implement the Breadth-First
Search Algorithm
1 Input: s as the source node
2
3 BFS (G, s)
4 let Q be queue.
5 [Link]( s )
6
7 mark s as visited
8 while ( Q is not empty)
9 v = [Link]( )
10
11 for all neighbors w of v in Graph G
12 if w is not visited
13 [Link]( w )
14 mark w as visited
In the previoius code, the following steps are
executed:
1.(G, s) is input, here G is the graph and s is the root node
2.A queue ‘Q’ is created and initialized with the source
node ‘s’
[Link] child nodes of ‘s’ are marked
[Link] ‘s’ from queue and visit the child nodes
[Link] all the child nodes of v
[Link] w (child nodes) in Q to further visit its child nodes
[Link] till ‘Q’ is empty
21
BFS - Working
22
BFS - Implementation
23
BFS - Implementation
24
BFS – Time and Space
• Time Complexity: Time Complexity of BFS algorithm can be
obtained by the number of nodes traversed in BFS until the
shallowest Node. Where the d= depth of shallowest solution
and b is a node at every state.
• T (b) = 1+b2+b3+.......+ bd= O (bd)
• Space Complexity: Space complexity of BFS algorithm is
given by the Memory size of frontier which is O(bd).
• Completeness: BFS is complete, which means if the
shallowest goal node is at some finite depth, then BFS will
find a solution.
• Optimality: BFS is optimal if path cost is a non-decreasing
function of the depth of the node.
25
BFS – Applications
• Crawlers in Search Engines: Breadth-First Search is one of
the main algorithms used for indexing web pages. The
algorithm starts traversing from the source page and follows all
the links associated with the page. Here each web page will be
considered as a node in a graph.
• GPS Navigation systems: Breadth-First Search is one of the
best algorithms used to find neighboring locations by using the
GPS system.
• Find the Shortest Path & Minimum Spanning Tree for an
unweighted graph: When it comes to an unweighted graph,
calculating the shortest path is quite simple since the idea
behind shortest path is to choose a path with the least number
of edges. Breadth-First Search can allow this by traversing a
minimum number of nodes starting from the source node.
26
Uniform Cost search
• Uniform-cost search is a searching algorithm used for traversing a
weighted tree or graph. It is Branch & Bound algorithm.
• This algorithm comes into play when a different cost is available for each
edge.
• The primary goal of the uniform-cost search is to find a path to the goal
node which has the lowest cumulative cost. Uniform-cost search expands
nodes according to their path costs form the root node.
• It can be used to solve any graph/tree where the optimal cost is in
demand.
• A uniform-cost search algorithm is implemented by the priority queue.
• It gives maximum priority to the lowest cumulative cost. Uniform cost
search is equivalent to BFS algorithm if the path cost of all edges is the
same.
27
Uniform Cost search - Example
28
Uniform Cost search - Algorithm
29
Uniform Cost search - Algorithm
1. Insert the root node into the priority queue { Frontier
queue}
2. Remove the element with the highest priority (initially
root, later need to decide with priority)
– add it in explored List
3. If the removed node is the goal node – print total cost
& stop the algorithm
else
enqueue all the children of the current node to the
priority queue with their cumulative cost from the root
as priority and the current node to the explored list.
30
Uniform Cost search- Working
31
Uniform Cost search - Implementation
32
Uniform Cost search - Implementation
33
Uniform Cost search
Frontier List Expand Explored
List List
{A,0} A NULL
{ (A-B, 5), (A-C,9) } B {A}
{ (A-B-D, 7) (A-C-,9), (A-B-E,13) } D {A,B}
{(A-C,9), (A-B-D-G,13), (A-B-E,13) (A- C {A,B,C}
B-D-E,14)}
{(A-B-D-G,13), ), (A-B-E,13), (A-B-D- G {S,B,A,D}
E,14), (A-C-G,21) }
A-B-D-G,13
{(A-B-D-G,13) Is the
Path to the Goal
state
34
Uniform Cost search- Time and space
35
Example
[Link]
Example
Uniform Cost search
Frontier List Expand Explored
List List
{S} S NULL
{(S-B, 1), (S-A,3) (S-C,8)} B {S}
{(S-A,3) (S-C,8), (S-B-G, 21) } A {S,B}
{(S-A-D,6), (S-C,8), (S-A-E,10), (S-A- D {S,B,A}
G,18), (S-B-G, 21) }
{(S-C,8), (S-A-E,10), (S-A-G,18), (S-B- C {S,B,A,D}
G, 21) }
{(S-A-E,10), (S-C-G,13), (S-A-G,18), E {S,B,A,D,C
{(S-C-G,13) Is the (S-B-G, 21) } }
Path to the Goal {(S-C-G,13), (S-A-G,18), (S-B-G, 21) } G {S,B,A,D,C
state ,E}
{(S-A-G,18), (S-B-G, 21) } All 7 {S,B,A,D,C
nodes ,E,G}
explored
38
DFS
• Depth-first search (DFS) is an algorithm for traversing or searching
tree or graph data structures.
• The algorithm starts at the root node (selecting some arbitrary
node as the root node in the case of a graph) and explores as far
as possible along each branch before backtracking.
39
DFS
• Depth first search (DFS) algorithm starts with the initial node
of the graph G, and then goes to deeper and deeper until the
goal node or the node which has no children.
• The algorithm, then backtracks from the dead end towards
the most recent node that is yet to be completely unexplored.
• The data structure which is being used in DFS is stack. In DFS,
the edges that leads to an unvisited node are called discovery
edges while the edges that leads to an already visited node are
called block edges.
• Explore left most child node first before exploring siblings.
40
DFS - Example
41
• DFS SEARCH example 2
Traversal DFS: S -> A -> B -> C -> G
DFS Path : S -> A -> B -> G
42
DFS – Working Principle
• Pick a starting node and push all its adjacent nodes into a
stack.
• Pop a node from stack to select the next node to visit and
push all its adjacent nodes into a stack.
Repeat this process until the stack is empty.
• Ensure that the nodes that are visited are marked. This will
prevent you from visiting the same node more than once.
• If you do not mark the nodes that are visited and you visit the
same node more than once, you may end up in an infinite
loop.
43
DFS - Iterative
44
DFS - Recursive
45
DFS
46
DFS - Graph
47
DFS
48
H→A→D→F→B→C→G→E
E49
DFS – Time and Space
• Completeness: DFS search algorithm is complete within
finite state space as it will expand every node within a
limited search tree.
• Time Complexity: Time complexity of DFS will be
equivalent to the node traversed by the algorithm. It is
given by:
• T(n)= 1+ n2+ n3 +.........+ nm=O(nm)
• Where, m= maximum depth of any node and this can be
much larger than d (Shallowest solution depth)
• Space Complexity: DFS algorithm needs to store only single
path from the root node, hence space complexity of DFS is
equivalent to the size of the fringe set, which is O(bm).
• Optimal: DFS search algorithm is non-optimal, as it may
generate a large number of steps or high cost to reach to
the goal node.
50
Depth Limited Search
• A depth-limited search algorithm is similar to depth-first search
with a predetermined limit.
• Depth-limited search can solve the drawback of the infinite path in
the Depth-first search.
• In this algorithm, the node at the depth limit will treat as it has no
successor nodes further.
51
DLS - Limitation
• Standard failure value: It indicates that problem does not have
any solution.
• Cutoff failure value: It defines no solution for the problem within
a given depth limit.
• Advantages:
– Depth-limited search is Memory efficient.
• Disadvantages:
– Depth-limited search also has a disadvantage of incompleteness.
– It may not be optimal if the problem has more than one solution
52
DLS
53
DLS - Algorithm
54
DLS - Working
55
DLS - Working
depth is limited to 2 56
DLS - Working
To reach O from A, DLS algorithm will return failure., because depth is
limited to 2, and the goal node is at depth 4.
57
DLS – Time and Space
• Completeness: DLS search algorithm is complete if the solution is
above the depth-limit.
• Time Complexity: Time complexity of DLS algorithm is O(bℓ).
• Space Complexity: Space complexity of DLS algorithm is O(b×ℓ).
• Optimal: Depth-limited search can be viewed as a special case of
DFS, and it is also not optimal even if ℓ>d.
58
Iterative Deepening Depth First Search(IDDFS)
• A search algorithm which suffers neither the drawbacks of
breadth-first nor depth-first search on trees is iterative-
deepening depth-first.
• IDDFS combines depth-first search’s space-efficiency and
breadth-first search’s fast search (for nodes closer to root).
• Iterative deepening depth first search (IDDFS) is a hybrid of BFS
and DFS. In IDDFS, we perform DFS up to a certain “limited
depth,” and keep increasing this “limited depth” after every
iteration
• The idea is to perform depth-limited DFS repeatedly, with an
increasing depth limit, until a solution is found
59
IDDFS
60
IDDFS
61
IDDFS
62
IDDFS – Time and Space
63
Informed Search
• Informed Search algorithms have information on the goal
state which helps in more efficient searching.
• This information is obtained by a function that estimates how
close a state is to the goal state.
• Informed search algorithm uses the idea of heuristic, so it is
also called Heuristic search.
64
Heuristic function
• Heuristic is a function which is used in Informed Search, and it
finds the most promising path.
• It takes the current state of the agent as its input and produces
the estimation of how close agent is from the goal.
• The heuristic method, however, might not always give the best
solution, but it guaranteed to find a good solution in reasonable
time.
• Heuristic function estimates how close a state is to the goal. It is
represented by h(n), and it calculates the cost of an optimal path
between the pair of states.
• The value of the heuristic function is always positive
• heuristic value can be calculated as
• 1. Euclidian distance- used to calculate straight line distance.
• [Link] distance-If we want to calculate vertical or
horizontal distance 65
Generate and Test
• Generate-and-test search algorithm is a very simple algorithm
that guarantees to find a solution if done systematically and
there exists a solution.
• The generate and Test algorithm is a depth first search
procedure because complete possible solutions are generated
before test.
• This can be implemented states are likely to appear often in a
tree
• It can be implemented on a search graph rather than a tree
66
Generate and Test
67
Generate and Test
• Generate-and-test search algorithm is a very simple algorithm
that guarantees to find a solution if done systematically and
there exists a solution.
• Algorithm: Generate-And-Test
[Link] a possible solution.
[Link] to see if this is the expected solution.
[Link] the solution has been found quit else go to step 1.
Potential solutions that need to be generated vary depending on
the kinds of problems.
Example
Consider a pin made up of three 2 digit numbers i.e. the numbers are
of the form,
In this case, one way to find the required pin is to generate all the
solutions in a brute force manner for example,
The total number of solutions in this case is (100)power3 which is
approximately 1M. So if we do not make use of any informed search
technique then it results in exponential time complexity. Now let’s
say if we generate 5 solutions every minute. Then the total numbers
generated in 1 hour are 5*60=300 and the total number of solutions
to be generated are 1M.
Example
• Let us consider the brute force search technique for example
linear search whose average time complexity is N/2.
• Then on an average, the total number of the solutions to be
generated are approximately 5 lakhs.
• Using this technique even if you work for about 24 hrs a day then
also you will need 10 weeks to complete the task.
• Now consider using heuristic function where we have domain
knowledge that every number is a prime number between 0-
99 then the possible number of solutions are (25)power 3
which is approximately 15,000.
• Now consider the same case that you are generating 5 solutions
every minute and working for 24 hrs then you can find the
solution in less than 2 days which was being done in 10 weeks in
the case of uninformed search.
Best First Search
• Best First Search uses an evaluation function (Heuristic) to
decide which adjacent node is most promising and then it
explore.
• Best first search (Greedy Search) is an instance of graph search
algorithm in which a node is selected for expansion based on
evaluation function f (n)
• Best first search can be implemented a priority queue, a data
structure that will maintain the fringe in ascending order of f
values.
71
Best first search algorithm
• Step 1: Place the starting node into the OPEN list.
• Step 2: If the OPEN list is empty, Stop and return failure.
• Step 3: Remove the node n, from the OPEN list which has
the lowest value of h(n), and places it in the CLOSED list.
• Step 4: Expand the node n, and generate the successors of
node n.
• Step 5: Check each successor of node n, and find whether
any node is a goal node or not. If any successor node is goal
node, then return success and terminate the search, else
proceed to Step 6.
• Step 6: For each successor node, algorithm checks for
evaluation function f(n), and then check if the node has
been in either OPEN or CLOSED list. If the node has not
been in both list, then add it to the OPEN list.
• Step 7: Return to Step 2.
Best First Search - Algorithm
73
BFS - Example
74
BFS - Working
75
BFS - Working
76
BFS - Working
77
BFS - Working
78
BFS - Working
S --> B --> H --> G --> E
79
Example 2
Answer Example 2
BFS
• 1. It is not optimal.
• 2. It is incomplete because it can start down an infinite path
and never return to try other possibilities.
• 3. The worst-case time complexity for greedy search is O
(bm), where m is the maximum depth of the search space.
• 4. Because greedy search retains all nodes in memory, its
space complexity is the same as its time complexity
A* Search
• It is an informed search algorithm, as it uses information
about path cost and also uses heuristics to find the solution.
• To find the shortest path between nodes or graphs
• A * algorithm is a searching algorithm that searches for the
shortest path between the initial and the final state
• It is an advanced BFS that searches for shorter paths first
rather than the longer paths.
• A* is optimal as well as a complete algorithm
• It has combined features of UCS and greedy best-first search,
by which it solve the problem efficiently
83
A* Search
• The value f (n) is calculated with the following formula:
f(n)=g(n)+h(n)
• g(n) being the value of the shortest path from the start node to node n,
and h(n) being a heuristic approximation of the node's value.
84
A* Search Algorithm
85
A* Search Algorithm
86
A* Search - Example
Open Best Closed
node to
expand
{A ,0} A NULL
{(A-B, 6), (A-C,8)} B {A}
{(A-B -C,7) (A-B-D,7), (A-C,8)} C {A,B}
{(A-B –C-E,11) (A-B-D,7), (A- D {A,B,C}
C,8)}
{(A-B –C-E,11) (A-B-D-F,7), (A-B- F {A,B,C,D
D-G,8)} }
{(A-B –C-E,11) (A-B-D-F -G,7), G {A,B,C,D,
(A-B-D-G,8)} F}
{(A-B –C-E,11) (A-B-D-F -G,7), Goal {A,B,C,D,
(A-B-D-G,8)} node F, G}
(A-B-D-F -G,7),
Example 2
Example 2
Homework
• A* algorithm to solve 8 puzzle problem
• A star Search Algorithm to Move from
start state to final state 8 Puzzle
• [Link]
Hijs
• What is the difference between the A* and AO* algorithm?
• An A* is an OR graph algorithm used to find a single solution, while AO*
Algorithm is an AND-OR graph algorithm used to find many solutions by
ANDing over more than one branch.
• Why is the A* algorithm popular?
• A* Algorithm is popular because it is a technique that is used for finding path
and graph traversals. Many web-based maps and games use this algorithm.
• Is A* better than Dijkstra?
• A* is usually considered better than Dijkstra as it performs informed search. It
expands more promising vertices.
• Does Google Maps use the A* algorithm?
• No. Google Maps uses the Dijkstra algorithm.
• Why is A* optimal?
• A* Algorithms are optimal. It relies on an open and closed list to find a path
that is optimal and complete towards the goal.
• How overestimation is handled in the A* algorithm?
• Overestimation happens when the estimate of the heuristic is more than the
actual cost of the final path.
Memory Bounded Heuristic Search
• Iterative Deepening A* (IDA*)
– Similar to Iterative Deepening Search, but cut off at
(g(n)+h(n)) > max instead of depth > max
– At each iteration, cutoff is the first f-cost that
exceeds the cost of the node at the previous
iteration
• Simple Memory Bounded A* (SMA*)
– Set max to some memory bound
– If the memory is full, to add a node drop the worst
(g+h) node that is already stored
– Expands newest best leaf, deletes oldest worst leaf
93
References
• 1. Parag Kulkarni, Prachi Joshi, “Artificial Intelligence –Building
Intelligent Systems ”PHI learning private Ltd, 2015
• [Link] Night and Elaine Rich, Nair B., “Artificial Intelligence (SIE)”,
Mc Graw Hill- 2008.
• [Link] Russel and Peter Norvig “AI – A Modern Approach”, 2nd
Edition, Pearson Education 2007
• 4. [Link]
• 5. [Link]
• [Link]
• 7. [Link]
94