Module – 2 (Problem Solving)

Solving Problems by searching-Problem solving Agents, Example problems,

searching for solutions, Uninformed search strategies, informed search strategies,
Heuristic functions.
1. What are the terminologies used in search algorithm?
1. Search - Searching solves a search issue in a given space step by step. Three major
factors can influence a search issue.
• Search Space - A search space is a collection of potential solutions a system may
have.
• Start State - Where the agent starts the search.
• Goal test - A function that examines the current state and returns whether or not the
goal state has been attained.
2. Search tree – It is a tree representation of a search issue. The node at the root of the
search tree corresponds to the initial condition.
3. Actions - It describes all the steps, activities, or operations accessible to the agent.
4. Transition model - It gives a description all the available actions to the agent.
5. Path Cost - It is a function that gives a cost to each path.
6. Solution -An action sequence connects the start node to the target node.
7. Optimal Solution - If a solution has the lowest cost among all solutions, it is said to
be the optimal answer.
2. Discuss the Performance criteria of search algorithm?
• Completeness - A search algorithm is said to be complete if it guarantees to return a
solution for any random input if at least one solution exists.
• Optimality - A solution discovered for an algorithm is considered optimal if it is
assumed to be the best solution (lowest path cost) among all other solutions.
• Time complexity - It measures how long an algorithm takes to complete its job.
• Space Complexity - The maximum storage space required during the search, as
determined by the problem's complexity.
3) Search Algorithms in AI?

Uninformed Search Algorithms (Blind search):

• Uninformed search is a method of searching a search tree without knowledge of the
search space.
• It is also known as blind search.
• It goes through each tree node until it reaches the target node.
• These algorithms are limited to producing successors and distinguishing between
goal and non-goal states.
• The uninformed search needs domain information, such as goal location.
• It works by brute force because it only contains information on traversing the tree
and identifying leaf and goal nodes.
4) Discuss Breadth-First Search?
• Breadth-first search 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.
Example:

• In figure, the node to be expanded next is indicated by a marker. If „A‟ is the source
node and „G‟ is the goal node then the solution path in BFS is:
ABCDEFG
BFS Algorithm
Problem solving Performance-BFS
• Complete-if the shallowest goal node is at some finite depth d, breadth-first search
will eventually find it after generating all shallower nodes.
• Not optimal one-breadth-first search is optimal if the path cost is a non-decreasing
function of the depth of the node.
• Time Complexity-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. In the worst case, it is the last node generated
at that level. Then the total number of nodes generated is:
b + b2 + b3 + ··· + bd = O (bd)
• Space complexity-Space complexity of BFS algorithm is given by the Memory size
of frontier which is O(bd).

Advantages:
 BFS will provide a solution if any solution exists.

 If there is more than one solution for a given problem, then BFS will provide the
minimal solution which requires the least number of steps.
Disadvantages:
 It requires lots of memory since each level of the tree must be saved into memory to
expand the next level.
 BFS needs lots of time if the solution is far away from the root node.
5) Discuss Depth first Search (DFS)?
• Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data
structures. The algorithm starts at the root node and explores as far as possible along
each branch before backtracking.
• It uses Last In- First-Out strategy (LIFO) and hence it is implemented using a stack.
• Depth-first search always expands 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.

Example:

• In the below search tree, we have shown the flow of depth-first search, and it will
follow the order as: Root node--->Left node ----> right node.
• It will start searching from root node S, and traverse A, then B, then D and E, after
traversing E, it will backtrack the tree as E has no other successor and still goal node
is not found.
• After backtracking it will traverse node C and then G, and here it will terminate as it
found goal node.

DFS Performance
1. Completeness: DFS search algorithm is complete within finite state space as it will
expand every node within a limited search tree.
2. 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.
3. Time Complexity: Time complexity of DFS will be equivalent to the node traversed
by the algorithm. It is given by:

4. 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).
Advantage:
 DFS requires very less memory as it only needs to store a stack of the nodes on the
path from root node to the current node.
 It takes less time to reach to the goal node than BFS algorithm.
Disadvantage:
 There is no guarantee of finding the solution.
 DFS algorithm goes for deep down searching and sometime it may go to the infinite
loop.
6) Discuss Uniform cost Search?
• Uniform-cost search is a searching algorithm used for traversing a weighted tree or
graph. 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 from the root node.
• A uniform-cost search algorithm is implemented by the priority queue. It gives
maximum priority to the lowest cumulative cost.
Example
UCS Algorithm

UCS Performance
1. Completeness: Uniform-cost search is complete, such as if there is a solution, UCS
will find it.
2. Time Complexity: Let C* is Cost of the optimal solution, and ε is each step to get
closer to the goal node. Then the number of steps is = C*/ε+1. Hence, the worst-case
time complexity of Uniform-cost search is O (b1 + [C*/ε])/.
3. Space Complexity: The same logic is for space complexity so, the worst-case space
complexity of Uniform-cost search is O (b1 + [C*/ε]).
4. Optimal: Uniform-cost search is always optimal as it only selects a path with the
lowest path cost.
Advantages:
 Uniform cost search is optimal because at every state the path with the least cost is
chosen.
Disadvantages:
 It does not care about the number of steps involve in searching and only concerned
about path cost. Due to which this algorithm may be stuck in an infinite loop.

7) Discuss Depth-Limited Search Algorithm:

• 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.
• Depth-limited search can be terminated with two Conditions of failure:
1. Standard failure value: It indicates that problem does not have any solution.
2. Cutoff failure value: It defines no solution for the problem within a given
depth limit.

DLS Example
DLS Algorithm

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.
DLS Performance
1. Completeness: DLS search algorithm is complete if the solution is above the depth-
limit.
2. Time Complexity: Time complexity of DLS algorithm is O(bℓ).
3. Space Complexity: Space complexity of DLS algorithm is O(b×ℓ).
4. Optimal: Depth-limited search can be viewed as a special case of DFS, and it is also
not optimal even if ℓ>d.
8) Discuss Iterative deepening depth-first Search?
 The iterative deepening algorithm is a combination of DFS and BFS algorithms.
 This search algorithm finds out the best depth limit and does it by gradually
increasing the limit until a goal is found.
 This algorithm performs depth-first search up to a certain "depth limit", and it keeps
increasing the depth limit after each iteration until the goal node is found.
 This Search algorithm combines the benefits of Breadth-first search's fast search and
depth-first search's memory efficiency.
 The iterative search algorithm is useful uninformed search when search space is
large, and depth of goal node is unknown.
Advantages:
 It combines the benefits of BFS and DFS search algorithm in terms of fast search and
memory efficiency.
Disadvantages:
 The main drawback of IDDFS is that it repeats all the work of the previous phase.

Example:

 Following tree structure is showing the iterative deepening depth-first search.

 IDDFS algorithm performs various iterations until it does not find the goal node. The
iteration performed by the algorithm is given as:
1'st Iteration-----> A
2'nd Iteration----> A, B, C
3'rd Iteration------>A, B, D, E, C, F, G
4'th Iteration------>A, B, D, H, I, E, C, F, K, G
In the fourth iteration, the algorithm will find the goal node.
IDDFS performance
1. Completeness: This algorithm is complete is ifthe branching factor is finite.
2. Time Complexity: Let's suppose b is the branching factor and depth is d then the
worst-case time complexity is O(bd).
3. Space Complexity: The space complexity of IDDFS will be O(bd).
4. Optimal: IDDFS algorithm is optimal if path cost is a non- decreasing function of
the depth of the node.
9) Explain informed Search (Heuristic Search)?
• Informed Search Algorithm contains an array of knowledge such as how far we are
from the goal, path cost, how to reach to goal node, etc.
• This knowledge helps agents to explore less to the search space and find more
efficiently the goal node.
• The informed search algorithm is more useful for large search space.
• Informed search algorithm uses the idea of heuristic, so it is also called Heuristic
search.
Heuristics 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 might not always give the best solution, but it guaranteed to
find a good solution in reasonable time.
• It is represented by h(n), and it calculates the cost of an optimal path between the pair
of states.
 • Examples of heuristic search are greedy search and A* search.
The heuristic function formula
• f(n)= g(n) + h(n), where
• f(n)= estimated cost of the cheapest solution
• g(n)= cost to reach node n from the start state
• h(n)= cost to reach from node n to goal node
• The value of the heuristic function is always positive.
Admissibility of the heuristic function
 It is given as: h(n) <= h*(n)
 Here h (n) is heuristic cost, and h*(n) is the estimated cost. Hence heuristic cost
should be less than or equal to the estimated cost.
Consistent heuristic function
 A heuristic is consistent if for every node n, every successor n‟ of n generated by
any action „a‟ is:

 If „h‟ is consistent, we have:

 i.e., f (n) is non-decreasing along any path.

10) Discuss Best First Search Algorithm (Greedy search)?
• It always selects the path which appears best at that moment.
 • It is the combination of depth-first search and breadth-first search algorithms.
• It uses the heuristic function and search. Best-first search allows us to take the
advantages of both algorithms.
• In the best first search algorithm, we expand the node which is closest to the goal
node and the closest cost is estimated by heuristic function. i.e. h(n)= g(n).
• Were, h(n)= estimated cost from node n to the goal.
• The greedy best first algorithm is implemented by the priority queue.
Best First Search Algorithm

Example
• Consider the below search problem, and we will traverse it using greedy best-first
search. At each iteration, each node is expanded using evaluation function f(n)=h(n) ,
which is given in the below table.
 • In this search example, we are using two lists which are OPEN and CLOSED Lists.
Following are the iteration for traversing the above example.
• Expand the nodes of „S‟ and put in the CLOSED list.
Initialization: Open[A,B],closed[S]
Iteration1: Open[A],closed[S,B]
Iteration2: Open[E,F,A],closed[S,B]
Open[E,A],closed[S,B,F]
Iteration3: Open[I,G,E,A],closed[S,B,F]
Open[I,E,A],closed[S,B,F,G]
 Hence the final solution path will be SBFG
Advantages:
 Best first search can switch between BFS and DFS by gaining the advantages of both
the algorithms. This algorithm is more efficient than BFS and DFS algorithms.
Disadvantages:
 It can behave as an unguided depth-first search in the worst case scenario. c It can get
stuck in a loop as DFS.
 This algorithm is not optimal.
Best First Search performance
1. Time Complexity: The worst case time complexity of Greedy best first search is
0(bm).
2. Space Complexity: The worst case space complexity of Greedy best first search is
0(bm). Where, m is the maximum depth of the search space.
3. Complete: Greedy best-first search is also incomplete, even if the given state space
is finite.
4. Optimal: Greedy best first search algorithm is not optimal.
11) Discuss A* algorithm?
 A* Algorithm is one of the best and popular techniques used for path finding and
graph traversals.
  A lot of games and web-based maps use this algorithm for finding the shortest path
efficiently.
 It is essentially a best first search algorithm.
Working-
A* Algorithm works as-
 It maintains a tree of paths originating at the start node.
 It extends those paths one edge at a time.
 It continues until its termination criterion is satisfied.
A* Algorithm extends the path that minimizes the following function-
f(n) = g(n) + h(n)
Here,
 „n‟ is the last node on the path
 g(n) is the cost of the path from start node to node „n‟
 h(n) is a heuristic function that estimates cost of the cheapest path from node „n‟ to
the goal node
Optimality of A* algorithm
• A* is only optimal if two conditions are met:
1. The heuristic is admissible, as it will never overestimate the cost.
2. The heuristic is monotonic, that is,
if h(ni) < h(ni + 1), then real-cost(ni) < real-cost(ni + 1).
Algorithm-
The implementation of A* Algorithm involves maintaining two lists- OPEN and CLOSED.
 OPEN contains those nodes that have been evaluated by the heuristic function but
have not been expanded into successors yet.
 CLOSED contains those nodes that have already been visited.
The algorithm is as follows-
Step1: Define a list OPEN. Initially, OPEN consists solely of a single node, the start nodeS.
Step-02: If the list is empty, return failure and exit.
Step-03:
  Remove node n with the smallest value of f(n) from OPEN and move it to list
CLOSED.
 If node n is a goal state, return success and exit.
Step-04: Expand node n.
Step-05:
 If any successor to n is the goal node, return success and the solution by tracing the
path from goal node to S.
 Otherwise, go to Step-06.
Step-06:
 For each successor node, apply the evaluation function f to the node.
 If the node has not been in either list, add it to OPEN.
Step-07: Go back to Step-02.
A* Example
Consider the following graph-

 The numbers written on edges represent the distance between the nodes.
 The numbers written on nodes represent the heuristic value.
 Find the most cost-effective path to reach from start state A to final state J using A*
Algorithm.
(Refer notebook for solution)
12) Compare informed and uninformed search?

Water Jug problem

13) In Water Jug problem, we can use two jugs called FOUR and THREE. FOUR
holds a maximum of 4L water. THREE holds a maximum of 3L water. How can we get
2L water in the FOUR jug?

State Space Representation:

 We will represent a state of the problem as a tuple (x, y) where x represents the
amount of water in the 4-gallon jug and y represents the amount of water in the 3-
gallon jug.
 Note that 0 ≤ x ≤ 4, and 0 ≤ y ≤ 3.
  To solve this we have to make some assumptions not mentioned in the problem.
They are:
1) We can fill a jug from the pump.
2) We can pour water out of a jug to the ground.
3) We can pour water from one jug to another.
4) There is no measuring device available.
 The operations to be used to solve the problem can be described below,
1 (x,y)= (4,y) Fill the FOUR liter jug.

2 (x,y)= (x,3) Fill the THREE liter jug.

3 (x,y)=(x-d,y) if x>0 Pour some water out of the FOUR liter jug.

4 (x,y)=(x,y-d) if y>0 Pour some water out of the THREE liter jug.

5 (x,y)=(0,y) Empty the FOUR liter jug.

6 (x,y)=(x,0) Empty the THREE liter jug.

7 (x,y)=(4,y-(4-x)) if y>0 Pour water from THREE liter jug into the FOUR
liter jug until the FOUR liter jug full
8 (x,y)=(x-(3-y),y) if x>0 Pour water from FOUR liter jug into the THREE
liter jug until the THREE liter jug full
9 (x,y)=(x+y, 0) if x+y <=4 ,y>0 Pour all the water from THREE liter jug into the
FOUR liter jug.

14) Explain the 5 components of a problem?

1. Initial State: This state requires an initial state for the problem which starts the AI
agent towards a specified goal.
2. Action: This stage of problem formulation works with function with a specific class
taken from the initial state and all possible actions done in this stage.
3. Transition: This stage of problem formulation integrates the actual action done by
the previous action stage and collects the final stage to forward it to their next stage.
 4. Goal test: This stage determines that the specified goal achieved by the integrated
transition model or not, whenever the goal achieves stop the action and forward into
the next stage to determine the cost to achieve the goal.
5. Path costing: This component of problem-solving numerical assigned what will be
the cost to achieve the goal. It requires all hardware software and human working
cost.
15) Discuss 8-puzzle problem in AI?
• The 8-puzzle is a well-known problem in the field of artificial intelligence and
puzzle-solving.
Rules and constraints
• The 8-puzzle is typically played on a 3x3 grid, which provides a 3x3 square
arrangement for tiles. This grid structure is fundamental to the problem's
organization.
• The puzzle comprises 8 numbered tiles (usually from 1 to 8) and one blank tile.
These numbered tiles can be slid into adjacent positions (horizontally or vertically)
when there's an available space, which is occupied by the blank tile.
• The objective of the 8-puzzle is to transform an initial state, defined by the
arrangement of the tiles on the grid, into a specified goal state. The goal state is often
a predefined configuration, such as having the tiles arranged in ascending order from
left to right and top to bottom, with the blank tile in the bottom-right corner.
Example
Solution of the above example

16) Write standard formulization of 8-puzzle problem?

1. States: A state description specifies the location of each of the eight tiles and the
blank in one of the nine squares.
2. Initial state: Any state can be designated as the initial state. Note that any given goal
can be reached from exactly half of the possible initial states.
3. Actions: The simplest formulation defines the actions as movements of the blank
space Left, Right, Up, or Down. Different subsets of these are possible depending on
where the “blank-tile” is.
4. Transition model: Given a state and action, this returns the resulting state.
5. Goal test: This checks whether the state matches the goal configuration.
6. Path cost: Each step costs 1, so the path cost is the number of steps in the path.
16) Discuss 8 queens problem?
The Problem Statement
 Assume an 8x8 chess board and eight queens. Our task is to place all of the eight
queens such that none of the queens threaten each other.
 That is there is no other queen in the same row, column, rising diagonal, and falling
diagonal.
 The task is to find all such configurations of queens on the 8x8 board. There are 92
possible configurations. One of the possible solutions is shown below.

Standard formulization of 8-Queens problem

1. States: any arrangement of 0 to 8 Queens on the board.
2. Initial State : Empty board • Successor function : Add a Queen to an empty space
3. Goal Test: 8 queens are on the board but none of them should attack each other.
4. Path cost: for each action cost will be 1. So default is 8.