Bachelor of Science (Honours) in Data Science and Artificial Intelligence
DA109: AI Basics
Module 4
Problem Solving by Uninformed Strategies
Learning objective of Module 4
➢ To grasp the fundamentals of problem-solving by various uninformed
strategies with the advantages and limitations in artificial intelligence .
2
Parts
➢ Basic things for Searching a Solutions
➢ Significance of Domain and Non-domain specific knowledge
➢ Breadth-first search
➢ Depth-first search
➢ Depth-limited search
➢ Iterative deepening depth-first search
➢ Bidirectional search
➢ Uniform-cost search
4
Part - I
Basic things for Searching a Solutions
5
Basic things for Searching a Solutions
➢ Having formulated some problems, we now need to solve them.
➢ A solution is an action sequence, so search algorithms work by considering various possible action
sequences.
➢ The possible action sequences starting at the initial state form a search tree with the initial state at the root.
➢ The branches are actions and the nodes correspond to states in the state space of the problem.
6
Basic things for Searching a Solutions
➢ First few steps in growing the search tree for finding a route from initial state.
➢ Consider a example for route planning form Arad to Bucharest.
➢ The root node of the tree corresponds to the initial state, In(Arad).
➢ Then we need to consider taking various actions. We do this by expanding the current state; that is, applying
each legal action to the current state, thereby generating a new set of states.
➢ In this case, we add three branches from the parent node In(Arad) leading to three new child nodes:
In(Sibiu), In(Timisoara), and In(Zerind). Now we must choose which of these three possibilities to consider
further.
7
Basic things for Searching a Solutions
➢ This is the essence of search—following up one option now and putting the others aside for later, in case the
first choice does not lead to a solution.
➢ Suppose we choose Sibiu first. We check to see whether it is a goal state (it is not) and then expand it to get
In(Arad), In(Fagaras), In(Oradea), and In(RimnicuVilcea).
8
Basic things for Searching a Solutions
9
Basic things for Searching a Solutions
➢ We can then choose any of these four or go back and choose Timisoara or Zerind. Each of these six nodes
is a leaf node, that is, a node with no children in the tree.
➢ The set of all leaf nodes available for expansion at any given point is called the frontier.
➢ The process of expanding nodes on the frontier continues until either a solution is found or there are no more
states to expand.
➢ Tree-search and graph-search algorithms are both used to traverse a search tree or graph in order to find a
solution to a problem.
➢ However, they differ in how they handle repeated states and explore the search space.
10
Tree-search and Graph-search
Item Tree-search Graph-search
11
Tree-search and Graph-search
Item Tree-search Graph-search
Definition Explore a search tree without Explore a search graph and keep track of
considering repeated states previously visited states to avoid revisiting them.
12
Tree-search and Graph-search
Item Tree-search Graph-search
Definition Explore a search tree without Explore a search graph and keep track of
considering repeated states previously visited states to avoid revisiting them.
Memory Typically use less memory compared May use more memory compared to tree-search
Usage to graph-search algorithms since they algorithms since they store visited states in a data
do not store previously visited states structure like a hash table or visited set.
13
Tree-search and Graph-search
Item Tree-search Graph-search
Definition Explore a search tree without Explore a search graph and keep track of
considering repeated states previously visited states to avoid revisiting them.
Memory Typically use less memory compared May use more memory compared to tree-search
Usage to graph-search algorithms since they algorithms since they store visited states in a data
do not store previously visited states structure like a hash table or visited set.
Completeness May not be complete if the search Typically complete, ensuring that they find a
space contains cycles or loops solution if one exists.
14
Tree-search and Graph-search
Item Tree-search Graph-search
Definition Explore a search tree without Explore a search graph and keep track of
considering repeated states previously visited states to avoid revisiting them.
Memory Typically use less memory compared May use more memory compared to tree-search
Usage to graph-search algorithms since they algorithms since they store visited states in a data
do not store previously visited states structure like a hash table or visited set.
Completeness May not be complete if the search Typically complete, ensuring that they find a
space contains cycles or loops solution if one exists.
Efficiency They can be more efficient in terms of They may be less efficient in terms of memory
memory usage and time complexity usage and time complexity compared to tree-
for certain problems. search algorithms due to the overhead of
maintaining visited states.
15
Tree-search and Graph-search
Item Tree-search Graph-search
Definition Explore a search tree without Explore a search graph and keep track of
considering repeated states previously visited states to avoid revisiting them.
Memory Typically use less memory compared May use more memory compared to tree-search
Usage to graph-search algorithms since they algorithms since they store visited states in a data
do not store previously visited states structure like a hash table or visited set.
Completeness May not be complete if the search Typically complete, ensuring that they find a
space contains cycles or loops solution if one exists.
Efficiency They can be more efficient in terms of They may be less efficient in terms of memory
memory usage and time complexity usage and time complexity compared to tree-
for certain problems. search algorithms due to the overhead of
maintaining visited states.
Example Depth-First Search and Breadth-First A* Search and Uniform Cost Search (UCS)
Search
16
Infrastructure for search algorithms
➢ Search algorithms require a data structure to keep track of the search tree that is being constructed.
➢ For each node n of the tree, we have a structure that contains four components:
❑ [Link]: the state in the state space to which the node corresponds;
❑ [Link]: the node in the search tree that generated this node;
❑ [Link]: the action that was applied to the parent to generate the node;
❑ [Link]-COST: the cost, traditionally denoted by g(n), of the path from the initial state to
the node, as indicated by the parent pointers.
17
18
Part - II
Significance of Domain and Non-domain specific knowledge
19
Search Strategies
➢ Informed strategies
❑ Typically involve use of domain-specific knowledge to guide the search process i.e. require knowledge
about the problem domain for effective evaluation.
➢ Uninformed strategies
❑ Do not use domain-specific knowledge to guide the search process. Instead, they explore the search
space systematically without considering the specific characteristics of the problem domain.
20
Domain specific and non-domain specific knowledge
➢ Domain specific
❑ Informed strategies
❑ Pros
❖ Efficiency
❖ Accuracy
❖ Customization
❖ Interpretability
❖ Resource Efficiency
❑ Cons
❖ Limited Scope
❖ Dependency
❖ Data Availability
❖ Generalization
❖ Expertise Requirement:
21
Domain specific and non-domain specific knowledge
➢ Domain specific examples
❑ Medical Diagnosis System
❑ Automated Trading Algorithms
❑ Chatbots for Customer Support
22
Domain specific and non-domain specific knowledge
➢ Non-domain specific
❑ Uninformed strategies
❑ Pros
❖ Versatility
❖ Flexibility
❖ Scalability
❖ Data Availability
❖ Innovation
❑ Cons
❖ Accuracy
❖ Interpretability
❖ Resource Intensity
❖ Overfitting
❖ Lack of Customization
23
Domain specific and non-domain specific knowledge
➢ Non-domain specific examples
❑ Image Recognition
❑ Natural Language Processing (NLP)
❑ Autonomous Vehicles
24
25
Part - III
Breadth-first search
26
Breadth-first search
➢ It is a simple strategy in which the root node is expanded first, then all the successors of the root node are
expanded next, then their successors, and so on.
➢ In general, all the nodes are expanded at a given depth in the search tree before any nodes at the next level
are expanded.
➢ It is an instance of the general graph-search algorithm in which the shallowest unexpanded node is chosen
for expansion. This is achieved very simply by using a FIFO queue for the frontier.
➢ Thus, new nodes (which are always deeper than their parents) go to the back of the queue, and old nodes,
which are shallower than the new nodes, get expanded first
27
Breadth-first search
➢ Breadth-first search on a graph
28
Breadth-first search
➢ Breadth-first search on a simple binary tree
29
Breadth-first search
➢ So far, the news about breadth-first search has been good. The news about time and space is not so good.
➢ Imagine searching a uniform tree where every state has b successors.
➢ The root of the search tree generates b nodes at the first level, each of which generates b more nodes, for a
total of b2 at the second level.
➢ Each of these generates b more nodes, yielding b3 nodes at the third level, and so on.
➢ Now suppose that the solution is at depth d. Then the total number of nodes generated is
𝑏 + 𝑏 2 + 𝑏 3 + 𝑏 4 + ⋯ … + 𝑏 𝑑+1 + 𝑏 𝑑 = 𝑂(𝑏 𝑑 )
30
Breadth-first search
➢ For any kind of graph search, which stores every expanded node in the explored set, the space complexity is
always within a factor of b of the time complexity.
➢ For breadth-first graph search in particular, every node generated remains in memory.
➢ There will be O(bd−1) nodes in the explored set and O(bd) nodes in the frontier, so the space complexity is
O(bd), i.e., it is dominated by the size of the frontier
31
Breadth-first search
➢ Time and memory requirements for breadth-first search
➢ The table assumes that 1 million nodes can be generated per second and that a node requires 1000 bytes
of storage.
➢ The memory requirements are a bigger problem for breadth-first search than is the execution time.
➢ Time is still a major factor. If your problem has a solution at depth 16, then it will take about 350 years for
breadth-first search to find it.
32
33
Part - IV
Depth-first search
34
Depth-first search
➢ Depth-first search always expands DEPTH-FIRST the deepest node in the current frontier of the search tree.
➢ The search proceeds immediately to the deepest level of the search tree, where the nodes have no
successors.
➢ As those nodes are expanded, they are dropped from the frontier, so then the search “backs up” to the next
deepest node that still has unexplored successors.
➢ Depth-first search uses a LIFO queue. A LIFO queue means that the most recently generated node is
chosen for expansion
➢ This must be the deepest unexpanded node because it is one deeper than its parent—which, in turn, was
the deepest unexpanded node when it was selected.
35
Depth-first search
➢ Depth-first search on a binary tree.
36
Depth-first search
➢ Depth-first search on a binary tree.
37
Depth-first search
➢ Depth-first search on a binary tree.
38
Depth-first search
➢ Depth-first search on a binary tree.
➢ Depth-first search will explore the entire left subtree even if node C is a goal node.
➢ If node J were also a goal node, then depth-first search would return it as a solution instead of C, which would
be a better solution; hence, depth-first search is not optimal.
39
40
Part - V
Depth-limited search
41
Depth-limited search
➢ Depth-Limited Search (DLS), an important variant of Depth-First Search (DFS) used to address some of the
limitations of standard DFS.
➢ The embarrassing failure of depth-first search in infinite state spaces can be alleviated by supplying depth-
first search with a predetermined depth limit l.
➢ Nodes at depth l are treated as if they have no successors. This approach is called depth-limited search.
➢ The depth limit solves the infinite-path problem. Unfortunately, it also introduces an additional source of
incompleteness if we choose l < d, that is, the shallowest goal is beyond the depth limit (this is likely when d
is unknown.)
➢ Depth-limited search will also be nonoptimal if we choose l > d. Its time complexity is O(bl) and its space
complexity is O(bl).
42
Depth-limited search
➢ How to define depth-limit?
➢ Depth limits can be based on knowledge of the problem
➢ For example, on the map of Romania there are 20 cities. Therefore, we know that if there is a solution, it
must be of length 19 at the longest, so l = 19 is a possible choice.
➢ But in fact if we studied the map carefully, we would discover that any city can be reached from any other
city in at most 9 steps.
➢ This number, known as the diameter of the state space, gives us a better depth limit, which leads to a more
efficient depth-limited search.
➢ For most problems, however, we will not know a good depth limit until we have solved the problem.
43
Depth-limited search
➢ This can be implemented as a simple modification to the general tree or graph-search algorithm.
44
Depth-limited search
➢ Depth-limited search can terminate with two kinds of failure.
❑ the standard failure value indicates no solution;
❑ the cutoff value indicates no solution within the depth limit.
45
46
Part - VI
Iterative deepening depth-first search
47
Iterative deepening depth-first search
➢ Iterative deepening search (or iterative deepening depth-first search) is a general strategy, often used in
combination with depth-first tree search, that finds the best depth limit
➢ It does this by gradually increasing the limit—first 0, then 1, then 2, and so on—until a goal is found. This
will occur when the depth limit reaches d, the depth of the shallowest goal node.
➢ Iterative deepening combines the benefits of depth-first and breadth-first search. Like depth-first search, its
memory requirements are modest: O(bd) to be precise.
➢ Like breadth-first search, it is complete when the branching factor is finite and optimal when the path cost is
a nondecreasing function of the depth of the node
48
Iterative deepening depth-first search
➢ The iterative deepening search algorithm, which repeatedly applies depth-limited search with increasing
limits.
➢ It terminates when a solution is found or if the depth-limited search returns failure, meaning that no solution
exists.
49
Iterative deepening depth-first search
➢ Four iterations of iterative deepening search on a binary tree
50
Iterative deepening depth-first search
➢ Four iterations of iterative deepening search on a binary tree
51
Iterative deepening depth-first search
➢ Iterative deepening search may seem wasteful because states are generated multiple times. It turns out
this is not too costly.
➢ The reason is that in a search tree with the same (or nearly the same) branching factor at each level, most
of the nodes are in the bottom level, so it does not matter much that the upper levels are generated multiple
times.
➢ In an iterative deepening search, the nodes on the bottom level (depth d) are generated once, those on the
next-to-bottom level are generated twice, and so on, up to the children of the root, which are generated d
times.
➢ So the total number of nodes generated in the worst case is:
𝑁 𝐼𝐷𝑆 = (𝑑)𝑏 + 𝑑 − 1 𝑏2 + ⋯ + (1)𝑏𝑑
52
Iterative deepening depth-first search
➢ Iterative deepening search gives a time complexity of O(bd)—asymptotically the same as breadth-first
search. There is some extra cost for generating the upper levels multiple times, but it is not large.
➢ For example, if b = 10 and d = 5, the numbers are
𝑁 𝐼𝐷𝑆 = 50 + 400 + 3000 + 20000 + 100000 = 123450
𝑁 𝐵𝐷𝑆 = 10 + 100 + 1000 + 10000 + 100000 = 111110
➢ If you are really concerned about repeating the repetition, you can use a hybrid approach that runs breadth-
first search until almost all the available memory is consumed, and then runs iterative deepening from all
the nodes in the frontier.
➢ In general, iterative deepening is the preferred uninformed search method when the search space is large
and the depth of the solution is not known
53
54
Part - VII
Bidirectional search
55
Bidirectional search
➢ The idea behind bidirectional search is to run two simultaneous searches—one forward from the initial state
and the other backward from the goal—hoping that the two searches meet in the middle
➢ The motivation is that bd/2 + bd/2 is much less than bd, or in the figure, the area of the two small circles is
less than the area of one big circle centered on the start and reaching to the goal.
➢ Bidirectional search is implemented by replacing the goal test with a check to see whether the frontiers of
the two searches intersect; if they do, a solution has been found.
➢ It is important to realize that the first such solution found may not be optimal, even if the two searches are
both breadth-first; some additional search is required to make sure there isn’t another short-cut across the
gap.
56
Bidirectional search
➢ The check can be done when each node is generated or selected for expansion and, with a hash table, will
take constant time.
➢ For example, if a problem has solution depth d=6, and each direction runs breadth-first search one node at
a time, then in the worst case the two searches meet when they have generated all of the nodes at depth 3.
➢ For b=10, this means a total of 2,220 node generations, compared with 1,111,110 for a standard breadth-
first search.
➢ Thus, the time complexity of bidirectional search using breadth-first searches in both directions is O(bd/2).
The space complexity is also O(bd/2).
➢ We can reduce this by roughly half if one of the two searches is done by iterative deepening, but at least
one of the frontiers must be kept in memory so that the intersection check can be done. This space
requirement is the most significant weakness of bidirectional search.
57
Bidirectional search
➢ A schematic view of a bidirectional search that is about to succeed when a branch from the start node
meets a branch from the goal node.
58
59
Part - VIII
Uniform-cost search
60
Uniform-cost search
➢ When all step costs are equal, breadth-first search is optimal because it always expands the shallowest
unexpanded node.
➢ By a simple extension, we can find an algorithm that is optimal with any step-cost function. Instead of
expanding the shallowest node, uniform-cost search expands the node n with the lowest path cost g(n).
➢ In addition to the ordering of the queue by path cost, there are two other significant differences from breadth-
first search:
❑ Goal test is applied to a node when it is selected for expansion rather than when it is first generated.
❑ Test is added in case a better path is found to a node currently on the frontier
61
Uniform-cost search
➢ Both of these modifications we will see with examples.
➢ The successors of Sibiu are Rimnicu Vilcea and Fagaras,
with costs 80 and 99, respectively
➢ The least-cost node, Rimnicu Vilcea, is expanded next, adding
Pitesti with cost 80 + 97=177
➢ The least-cost node is now Fagaras, so it is expanded, adding
Bucharest with cost 99+211=310.
➢ Now a goal node has been generated, but uniform-cost search keeps going, choosing Pitesti
for expansion and adding a second path to Bucharest with cost 80+97+101= 278.
➢ Now the algorithm checks to see if this new path is better than the old one; it is, so the old one is discarded.
Bucharest, now with g-cost 278, is selected for expansion and the solution is returned.
62
Uniform-cost search
➢ Uniform-cost search is guided by path costs rather than depths, so its complexity is not easily characterized
in terms of b and d.
➢ Instead, let C∗ be the cost of the optimal solution, and assume that every action costs at least ϵ.
➢ Then the algorithm’s worst-case time and space complexity is O(b1+C∗/ϵ ), which can be much greater than bd.
➢ This is because uniform-cost search can explore large trees of small steps before exploring paths involving
large and perhaps useful steps.
➢ When all step costs are the same, uniform-cost search is similar to breadth-first search, except that the
latter stops as soon as it generates a goal, whereas uniform-cost search examines all the nodes at the
goal’s depth to see if one has a lower cost
➢ Thus uniform-cost search does strictly more work by expanding nodes at depth d unnecessarily.
63
64
Comparing uninformed search strategies
➢ Compares search strategies in terms of the four evaluation criteria set forth.
➢ b is the branching factor; d is the depth of the shallowest solution; m is the maximum depth of the search tree;
l is the depth limit, a complete if b is finite; b complete if step costs ≥ ϵ for positive ϵ; c optimal if step costs are
all identical; d if both directions use breadth-first search
➢ This comparison is for tree-search versions. For graph searches, the main differences are that depth-first
search is complete for finite state spaces and that the space and time complexities are bounded by the size
of the state space
65
66
Summary
➢ The major points to recall are as follows:
❑ Basic things for Searching a Solutions
❑ Significance of Domain and Non-domain specific knowledge
❑ Breadth-first search
❑ Depth-first search
❑ Depth-limited search
❑ Iterative deepening depth-first search
❑ Bidirectional search
❑ Uniform-cost search
67