Problem-solving agents

UNIT 2
 Search Algorithm Terminologies
• Search
• Search tree
• Actions
• Transition model
• Path Cost
• Solution
• Optimal Solution
Types of search algorithms
 Breadth-first Search

• 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.
• Breadth-first search implemented using FIFO queue data
structure.
Example
Example
Advantages:
• BFS will provide a solution if any solution exists.
• If there are more than one solutions 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.
 Depth-first Search

• Depth-first search is a recursive algorithm for

traversing a tree or graph data structure.
• It is called the depth-first search because it
starts from the root node and follows each
path to its greatest depth node before moving
to the next path.
• DFS uses a stack data structure for its
implementation.
Example
Example
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 the possibility that many states keep re-
occurring, and there is no guarantee of finding the
solution.
• DFS algorithm goes for deep down searching and
sometime it may go to the infinite loop.
 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:
• 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.
Example
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.
 Uniform-cost Search Algorithm
• 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 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.
 Example

5
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.
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.
Example

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
 Bidirectional Search Algorithm

• Bidirectional search algorithm runs two simultaneous

searches, one form initial state called as forward-
search and other from goal node called as backward-
search, to find the goal node.
• Bidirectional search replaces one single search graph
with two small subgraphs in which one starts the
search from an initial vertex and other starts from goal
vertex.
• The search stops when these two graphs intersect each
other.
• Bidirectional search can use search techniques such as
BFS, DFS, DLS, etc.
Example
Advantages:
• Bidirectional search is fast.
• Bidirectional search requires less memory
Disadvantages:
• Implementation of the bidirectional search
tree is difficult.
• In bidirectional search, one should know the
goal state in advance.
 Informed search algorithm
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.
 Heuristic search
• 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.
 Types Informed search
• Best First Search Algorithm(Greedy search)
• A* Search Algorithm
Example
Example
Path cost=SBFG=2+1+3=6
 Best first search
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.
• It can get stuck in a loop as DFS.
• This algorithm is not optimal.
 A* Search Algorithm

A* search is the most commonly known form of

best-first search. It uses heuristic function h(n), and
cost to reach the node n from the start state g(n). It
has combined features of UCS and greedy best-first
search, by which it solve the problem efficiently. A*
search algorithm finds the shortest path through the
search space using the heuristic function. This
search algorithm expands less search tree and
provides optimal result faster. A* algorithm is
similar to UCS except that it uses g(n)+h(n) instead
of g(n)
Example
SACG=6
 Examples

Eg.1 z is goal Eg.2 J is goal

 A* search algorithm
Advantages
• A* search algorithm is the best algorithm than other search
algorithms.
• A* search algorithm is optimal and complete.
• This algorithm can solve very complex problems.
Disadvantages
• It does not always produce the shortest path as it mostly
based on heuristics and approximation.
• A* search algorithm has some complexity issues.
• The main drawback of A* is memory requirement as it
keeps all generated nodes in the memory, so it is not
practical for various large-scale problems.
Local Search and Optimization

44
 Search Types
– Backtracking state-space search
– Local Search and Optimization

45
 Local Search and Optimization
• Previous searches: keep paths in memory,
and remember alternatives so search can
backtrack. Solution is a path to a goal.
• Path may be irrelevant, if only the final
configuration is needed (,8-Puzzle,8-queens,
Tic tac toe…)

46
 Local Search
• Use a single current state and move only to
neighbors.
• Use little space
• Can find reasonable solutions in large or
infinite (continuous) state spaces for which
the other algorithms are not suitable

47
 Optimization
• Local search is often suitable for optimization
problems. Search for best state by optimizing an
objective function.
• F(x) where often x is a vector of continuous or discrete
values
• Begin with a complete configuration
• A successor of state S is S with a single element
changed
• Move from the current state to a successor state
• Low memory requirements, because the search tree or
graph is not maintained in memory (paths are not
saved)
48
Tic-Tac-Toe game
8-Puzzle

50
8-Puzzle
 Example: n-queens
• Put n queens on an n × n board with no two
queens on the same row, column, or diagonal
•

52
 N-Queens problem
• 8 queens: find an arrangement of 8 queens on a
chess board such that no two queens are
attacking each other
• Start with some arrangement of the queens, one
per column
• X[j]: row of queen in column j
• Successors of a state: move one queen
• F: # pairs attacking each other

53
 Examples
• Traveling salesman problem: visit each city
exactly once
• Start with some ordering of the cities
• State representation – order of the cities
visited (for eg)
• Successor state: a change to the current
ordering
• F: length of the route
54
 Hillclimbing
(Greedy Local Search)
• Generate nearby successor states to the
current state
• Pick the best and replace the current state
with that one.
• Loop

55
 Hill-climbing search problems
• Local maximum: a peak that is lower than the
highest peak, so a suboptimal solution is
returned
• Plateau: the evaluation function is flat,
resulting in a random walk
• Ridges: slopes very gently toward a peak, so
the search may oscillate from side to side

Local maximum Plateau Ridge

56
State Space Landscape

57
58
 Types of Hill Climbing Algorithm
• Simple hill Climbing
• Steepest-Ascent hill-climbing
 1. Simple Hill Climbing
• Simple hill climbing is the simplest way to implement a
hill climbing algorithm. It only evaluates the neighbor
node state at a time and selects the first one which
optimizes current cost and set it as a current state.
• It only checks it's one successor state, and if it finds
better than the current state, then move else be in the
same state.
• This algorithm has the following features:
• Less time consuming
• Less optimal solution and the solution is not
guaranteed
 Algorithm for Simple Hill Climbing
• Step 1: Evaluate the initial state, if it is goal state then
return success and Stop.
• Step 2: Loop Until a solution is found or there is no
new operator left to apply.
• Step 3: Select and apply an operator to the current
state.
• Step 4: Check new state:
– If it is goal state, then return success and quit.
– Else if it is better than the current state then assign new
state as a current state.
– Else if not better than the current state, then return to step2.
• Step 5: Exit.
 2. Steepest-Ascent hill climbing

• The steepest-Ascent algorithm is a variation of

simple hill climbing algorithm. This algorithm
examines all the neighboring nodes of the
current state and selects one neighbor node
which is closest to the goal state. This
algorithm consumes more time as it searches
 Algorithm for Steepest-Ascent hill climbing
• Step 1: Evaluate the initial state, if it is goal state
then return success and stop, else make current
state as initial state.
• Step 2: Loop until a solution is found or the
current state does not change.
– Let SUCC be a state such that any successor of the
current state will be better than it.
– For each operator that applies to the current state:
• Apply the new operator and generate a new state.
• Evaluate the new state.
• If it is goal state, then return it and quit, else compare it to the
SUCC.
• If it is better than SUCC, then set new state as SUCC.
• If the SUCC is better than the current state, then set current
state to SUCC.
• Step 5: Exit.
 Constraint satisfaction Problems
Constraint satisfaction is a technique where a
problem is solved when its values satisfy certain
constraints or rules of the problem.
X: It is a set of variables.
D: It is a set of domains where the variables
reside. There is a specific domain for each
variable.
C: It is a set of constraints which are followed
by the set of variables.
Map coloring
Sudoku
 Cryptarithmetic Problem

Cryptarithmetic Problem is a type of constraint

satisfaction problem where the game is about digits
and its unique replacement either with alphabets or
other symbols.
In cryptarithmetic problem, the digits (0-9) get
substituted by some possible alphabets or symbols.
The task in cryptarithmetic problem is to substitute
each digit with an alphabet to get the result
arithmetically correct.
The rules or constraints on a cryptarithmetic problem are as
follows:

• There should be a unique digit to be replaced with

a unique alphabet.
• The result should satisfy the predefined arithmetic
rules, i.e., 2+2 =4, nothing else.
• Digits should be from 0-9 only.
• There should be only one carry forward, while
performing the addition operation on a problem.
• The problem can be solved from both sides,
i.e., lefthand side (L.H.S), or righthand side
(R.H.S)
 Backtracking
Backtracking is a general algorithm for finding
solutions to some computational problems,
notably constraint satisfaction problems, that
incrementally builds candidates to the solutions,
and leaves a candidate as soon as it determines
that the candidate cannot possibly be
completed to a valid solution.
 Game playing
• n video games, artificial intelligence (AI)
is used to generate responsive, adaptive or
intelligent behaviors primarily in non-player
characters (NPCs) similar to human-like
intelligence. ... It serves to improve the game-
player experience rather than machine
learning or decision making.
Maximizing and Minimizing Games
Example 2
Example 2(MinMax Game)