ARTIFICIAL

INTELLIGENCE
Problem solving by search
 SEARCHING
 In general, finding a solution
 In a website, finding answer for a question
 In a city, finding a correct path
 In Chess, finding the next best step to move

and many more …

2
PROBLEM SOLVING USING SEARCH
 Search is an important problem-solving tool
 Search is about exploring alternatives
 It is a major approach to capitalize knowledge

3
 SEARCH VS AI
 Search is the process of considering various possible sequences of
operators applied to the initial state, and finding out a sequence
which achieves the goal state
 Search methods are ubiquitous in AI systems
 They often are the backbones of both core and peripheral modules
 An autonomous robot uses search methods:
 to decide which actions to take and which sensing operations to perform
 to quickly anticipate collision
 to plan trajectories
 to interpret large numerical datasets provided by sensors into compact
symbolic representations
 to diagnose why something did not happen as expected, etc…

 Many searches may occur concurrently and sequentially

4
 APPLICATIONS OF SEARCH

 Search plays a key role in many applications, e.g.:

 Route finding: airline travel, networks
 Package/mail distribution
 Pipe routing, VLSI routing
 Comparison and classification of protein folds
 Pharmaceutical drug design
 Design of protein-like molecules
 Video games

5
 SEARCH FRAMEWORKS

 State space search

 Uninformed / blind search
 Informed / heuristic search

 Problem reduction search

 Game tree search

6
SEARCH APPROACHES

7
UNINFORMED SEARCH
 Does not contain domain knowledge
 Brute force search – operates in a brute force way
 Blind search

8
INFORMED SEARCH
 Guided with domain knowledge
 Efficient compared to uninformed search
 Heuristic search

9
STATE SPACE REPRESENTATION
 Search: Step-by-step procedure to solve a search-problem in a given
search space. A search problem has three main factors
 Search space: represents a set of possible solutions, which a system
may have
 Start state: a state from where agent begins the search
 Goal state: a function which observe the current state and returns
whether the goal state is achieved or not
 Search tree: a tree representation of search problem. The root of the
search tree is the root node which is corresponding to the initial state.

10
 STATE SPACE SEARCH
 Basic Search Problem:
 Given: [S, s, O, G] where
 S is the (implicitly specified) set of states
 s is the start state
 O is the set of state transition operators
 G is the set of goal states

 To find a sequence of state transitions leading from s to a goal

state

11
8-PUZZLE PROBLEM -
EXAMPLE

12
 8-PUZZLE PROBLEM
 State description (S)
 Location of each of the eight tiles (and the blank)
 Start state (s)
 The starting configuration (given)
 Operators (O)
 Four operators, for moving the blank left, right, up or down
 Goals (G)
 One or more goal configurations (given)

13
14
8-PUZZLE PROBLEM–
SEARCH TREE

15
 8-QUEENS PROBLEM
 Placing 8 queens on a chess board, so that none attacks the other
 A queen can move horizontally, vertically and diagonally
 Formulation – I
 A state is any arrangement of 0 to 8 queens on board
 Operators add a queen to any square
 Formulation – II
 A state is any arrangement of 0-8 queens with none attacked
 Operators place a queen in the left-most empty column
 Formulation – III
 A state is any arrangement of 8 queens, one in each column
 Operators move an attacked queen to another square in the same column

16
4-QUEENS PROBLEM

17
FORMULATION – I
 Operators add a queen
 States: all arrangements of 0, 1, 2, ..., 8 queens on the board
 Initial state: 0 queens on the board
 Successor function: each of the successors is obtained by adding one
queen in an empty square
 Goal test: 8 queens are on the board, with no queens attacking each other
~ 64x63x...x57 ~ 3x1014 states

18
FORMULATION – II
 Operators place a queen in the left-most empty column
 States: all arrangements of k = 0, 1, 2, ..., 8 queens in the k leftmost
columns with no two queens attacking each other
 Initial state: 0 queens on the board
 Successor function: each successor is obtained by adding one queen in any
square that is not attacked by any queen already in the board, in the
leftmost empty column
 Goal test: 8 queens are on the board
 2,057 states

8-queens 2,057
100-queens 1052
19
FORMULATION – III
 Any arrangement of queens – one in each column
 Operators move an attacked queen to another square in the same column
 iterative refinement or iterative corrective procedure
 start with any formulation or any arrangement of the queens, and try to
correct them based on the constraints

Kind of formulation is very important. For a good formulation,

search effort will be less. For a bad formulation, search effort
will be more

20
 MISSIONARIES AND

CANNIBALS
Three missionaries and three cannibals are on one side of a river, along
with a boat that can hold one or two people. Find a way to get everyone
to the other side, without ever leaving a group of missionaries
outnumbered by cannibals

 State: (#m, #c, 1/0)

 #m: number of missionaries in the first bank
 #c: number of cannibals in the first bank
 The last bit indicates whether the boat is in
the first bank.
 Start state: (3, 3, 0) Goal state: (0, 0, 1)
 Operators: Boat carries (1, 0) or (0, 1) or (1, 1)
or (2, 0) or (0, 2)

21
22
 MISSIONARIES AND
CANNIBALS SOLUTION

23
 CRYPTARITHMETIC
 Find an assignment of digits (0,…,9) to
letters so that a given arithmetic
expression is true.
 Examples: SEND + MORE = MONEY

24
 REMOVE 5 STICKS
 Given the following configuration of
sticks, remove exactly 5 sticks in such
a way that the remaining configuration
forms exactly 3 squares.

25
 WATER JUG PROBLEM
 Given a full 5-gallon jug and a full 2-
gallon jug, fill the 2-gallon jug with
exactly one gallon of water

26
 PROPERTIES OF SEARCH
ALGORITHMS
 Completeness: A search algorithm is said to be complete if it guarantees
to return a solution if at least any solution exists for any random input
(Does it always find a solution if one exists?)
 Optimality: If a solution found for an algorithm is guaranteed to be the
best solution (lowest path cost) (Does it always find a least-cost solution?)
 Time complexity: Time for an algorithm to complete its task (Number of
nodes generated/expanded)
 Space complexity: The maximum storage space required at any point
during the search (Maximum number of nodes in memory)

27
 OUTLINE OF A SEARCH
ALGORITHM
1. Initialize: Set OPEN = {s}
2. Fail: If OPEN = { }, Terminate with failure
3. Select: Select a state, n, from OPEN
4. Terminate: If n ∈ G, terminate with success
5. Expand: Generate the successors of n using O and insert them in OPEN
6. Loop: Go To Step 2.

OPEN: queue (FIFO) vs stack (LIFO)

28
29
 SAVE EXPLICIT SPACE
1. Initialize: Set OPEN = {s}, CLOSED = { }
2. Fail: If OPEN = { }, Terminate with failure
3. Select: Select a state, n, from OPEN and save n in CLOSED
4. Terminate: If n ∈ G, terminate with success
5. Expand: Generate the successors of n using O.
For each successor, m, insert m in OPEN
only if m ∉[OPEN ∪ CLOSED]
6. Loop: Go To Step 2.

30
 SEARCH STRATEGIES
 Picking the order of node expansion
 Strategies are evaluated based on:
 Completeness: does it always find a solution if one exists?
 Optimality: does it always find a least cost solution?
 Time complexity: number of nodes generated or expanded
 Space complexity: maximum number of nodes in memory

 Time and space complexity are measured in terms of

 b – maximum branching factor of the search tree
 d – depth of the least cost solution
 m – maximum depth of the state space (may be ∞)

31
 DFS
 starts from the root node and follows each path to its greatest depth
node before moving to the next path.
 uses a stack data structure for its implementation.

 Advantages:
 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.
 takes less time to reach to the goal node than BFS algorithm (if it
traverses in the right path).
 Disadvantage:
 goes for deep down searching and sometimes it may go to the infinite
loop.

32
 DFS
 Completeness: complete within finite state space as it will expand every
node within a limited search tree.
 Time Complexity: O(bm) (node traversed by the algorithm)
 Space Complexity: O(b×m) (needs to store only single path from the
root node)
 Optimal: non-optimal as it may generate a large number of steps or high
cost to reach to the goal node.

33
 BFS
 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.
 implemented using FIFO queue data structure.

 Advantages:
 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.
 needs lots of time if the solution is far away from the root node.

34
 BFS
 Completeness: complete, if the goal node is at some finite depth.
 Time Complexity: O(bd) (d: depth of solution; b: node at every state)
 Space Complexity: O(bd)
 Optimal: optimal if stepcost is 1. for multiple stepcost it may not be
optimal

35
 DEPTH LIMITED SEARCH
 similar to depth-first search with a predetermined limit.
 solve the drawback of the infinite path in the Depth-first search.
 the node at the depth limit will treat as it has no successor nodes further.
 DLS can be terminated with two conditions:
 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.
 Advantage: memory efficient
 Disadvantages:
 Incompleteness
 It may not be optimal if the problem has more than one solution.

36
 DEPTH LIMITED SEARCH
 If we fix the depth limit to 2, DLS  Completeness: complete if the solution
can be carried out similarly to the is within the depth-limit.
DFS until the goal node is found to  Time Complexity: O(bℓ)
exist in the search domain of the
tree.  Space Complexity: O(b×ℓ)
 Optimal: Depth-limited search can be
viewed as a special case of DFS, and it is
also not optimal even if ℓ>d.

37
ITERATIVE DEEPENING DFS
 Iterative deepening depth first search (IDDFS) is a hybrid of BFS and DFS.
 finds out the best depth limit by gradually increasing the limit until a goal is found.
 perform DFS up to a certain “limited depth,” and keep increasing this “limited depth”
after every iteration.
 do DFS in a BFS fashion.
 Iterative search algorithm is useful uninformed search when search space is large, and
depth of goal node is unknown.
DEPTH DLS traversal
0 A
1 ABCD
2 ABEFCGDH
3 ABEIFJKCGLDHMN
ABEIFJKOPCGLRDHM
4
NS
38
ITERATIVE DEEPENING DFS
 Advantage: It combines the benefits of BFS and DFS search algorithm in terms of fast
search and memory efficiency.
 Disadvantage: It repeats all the work of the previous phase.
 Completeness: complete if the branching factor is finite.
 Time Complexity: O(bd)
 Space Complexity: O(bd)
 Optimal: is optimal if path cost is a non- decreasing function of the depth of the
node.

39
 BIDIRECTIONAL SEARCH
 Search start from both direction simultaneously. one starting from initial
vertex and other starting from goal vertex. The search terminates when
two graphs intersect.
 Forward search form source/initial vertex toward goal vertex
 Backward search form goal/target vertex toward source vertex

40
 BIDIRECTIONAL SEARCH
When to use bidirectional approach?
1.Both initial and goal states are unique and completely defined.
2.The branching factor is exactly the same in both directions.

Performance measures
• Completeness : Bidirectional search is complete if BFS is used in both
searches.
• Optimality : It is optimal if BFS is used for search and paths have uniform
cost.
• Time and space complexity: O(bd/2)

41
BIDIRECTIONAL SEARCH
Advantages
 One of the main advantages of bidirectional searches is the speed at which
we get the desired results.
 It drastically reduces the time taken by the search by having simultaneous
searches.
 It also saves resources for users as it requires less memory capacity to store all the
searches.
Disadvantages
 The fundamental issue with bidirectional search is that the user should be aware of
goal state to use bidirectional search and thereby decreasing its use cases
drastically.
 The implementation is another challenge as additional code and instructions are
needed to implement this algorithm and also care has to be taken as each node
and step to implement such searches.
 The algorithm must be robust enough to understand the intersection when the 42
search should come to an end or else there’s a possibility of an infinite loop.
 SEARCH AND OPTIMIZATION
 Given: [S, s, O, G]
 To find:
 A minimum cost sequence of transitions to a goal state
 A sequence of transitions to the minimum cost goal
 A minimum cost sequence of transitions to a min cost goal

43
 UNIFORM COST SEARCH
1. Initialize: Set OPEN = {s}, CLOSED = { } , set C(s)=0
2. Fail: If OPEN = { }, Terminate with failure
3. Select: Select the minimum cost state, n, from OPEN and save n in CLOSED
4. Terminate: If n ∈ G, terminate with success
5. Expand: Generate the successors of n using O.
For each successor, m:
if m ∉[OPEN ∪ CLOSED]
Set C(m) = C(n) + C(n,m) and insert m in OPEN
if m ∈ [OPEN ∪ CLOSED]
Set C(m) = min {C(m), C(n) + C(n,m)}
if C(m) has decreased and m ∈ CLOSED, move it to OPEN
6. Loop: Go To Step 2.

44
45
 SEARCHING WITH COSTS
 If all operator costs are positive, then the algorithm finds the minimum
cost sequence of transitions to a goal.
 No state comes back to OPEN from CLOSED
 If operators have unit cost, then this is same as BFS
 What happens if negative operator costs are allowed?

46
47
 BRANCH-AND-BOUND
1. Initialize: Set OPEN = {s}, CLOSED = { }. Set C(s) = 0, C* = ∞
2. Terminate: If OPEN = { }, then return C*
3. Select: Select a state, n, from OPEN and save in CLOSED
4. Terminate: If n ∈ G and C(n) < C*, then
Set C* = C(n) and Go To Step 2.
5. Expand:
If C(n) < C* generate the successors of n
For each successor, m:
If m ∉[OPEN ∪ CLOSED]
Set C(m) = C(n) + C(n,m) and insert m in OPEN
If m ∈ [OPEN ∪ CLOSED]
Set C(m) = min {C(m), C(n) + C(n,m)}
If C(m) has decreased and m ∈ CLOSED, move it to OPEN
48
6. Loop: Go To Step 2.
INFORMED STATE SPACE SEARCH /
HEURISTIC SEARCH
 Heuristics use domain specific knowledge to estimate the
quality or potential of partial solutions
 Examples:
 Manhattan distance heuristic for 8 puzzle
 Minimum Spanning Tree heuristic for TSP
 Heuristics are fundamental to chess

h(n) = estimated cost of the cheapest path from the state at

node n to a goal state. (for goal state: h(n)=0)

49
 Manhattan distance heuristic for 8 puzzle

 Minimum Spanning Tree heuristic for TSP

h(n): distance to the nearest unvisited city from the current city +
estimated distance to travel all the unvisited cities (MST heuristic) +
nearest distance from an unvisited city to the start city.

50
INFORMED SEARCH PROBLEM
 Given: [S, s, O, G, h]
 S is the (implicitly specified) set of states
 s is the start state
 O is the set of state transition operators each having some cost
 G is the set of goal states
 h( ) is a heuristic function estimating the distance to a goal

 To find:
 A min cost seq. of transitions to a goal state

51
BEST FIRST SEARCH
 Idea: use an evaluation function f(n) for each node
 Estimate of “desirability”
 Expand most desirable unexpanded node

 Picking the order of node expansion in decreasing order of desirability

52
 BEST FIRST SEARCH
 Breadth first search is like best first search
 What is the function f? (f is the depth of the node. If some of them at lower depth
and some of them at higher depth; pick the node from lower depth)
 Uniform cost search is like best first search
 What is the function f? = sum of edge costs from start to n

g(n)

53
GREEDY BEST FIRST SEARCH
 Evaluation function f(n) = h(n) = estimate of cost from n to goal
 Greedy best-first search expands the node that appears to be closest to
goal
 Greedy best-first search algorithm 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.
 With the help of best-first search, at each step, we can choose the most
promising node.
 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.
f(n)= h(n). h(n)= estimated cost from node n to the goal. 54
55
 BEST FIRST SEARCH
 Complete?
 No – Can get stuck in loops

 Time?
 O(bm) – but a good heuristic can give dramatic improvement

 Space?
 O(bm) – keeps all nodes in memory

 Optimal?
 Not complete so not optimal

56
BEST FIRST SEARCH
Advantages
 It is more efficient than that of BFS and DFS.
 Time complexity of Best first search is much less than Breadth first search.
 The Best first search allows us to switch between paths by gaining the benefits of
both breadth first and depth first search. Because, depth first is good because a
solution can be found without computing all nodes and Breadth first search is
good because it does not get trapped in dead ends.

Disadvantages:
 Sometimes, it covers more distance than our consideration.

57
 A* SEARCH
 Idea: Avoid expanding paths that are already expensive
 Evaluation function f(n) = g(n) + h(n)

 g(n) = cost so far to reach n

 h(n) = estimated cost from n to goal
 f(n) = estimated total cost of path through n to goal

58
 A* ALGORITHM
1. Initialize: Set OPEN = {s}, CLOSED = { }, g(s) = 0, f(s) = h(s)
2. Fail: If OPEN = { }, Terminate & fail
3. Select: Select the minimum cost state, n, from OPEN. Save n in
CLOSED
4. Terminate: If n ∈ G, terminate with success, and return f(n)
5. Expand:
For each successor, m, of n
If m ∉[OPEN ∪ CLOSED]
Set g(m) = g(n) + C(n,m)
Set f(m) = g(m) + h(m)
Insert m in OPEN
If m ∈ [OPEN ∪ CLOSED]
Set g(m) = min { g(m), g(n) + C(n,m) }
Set f(m) = g(m) + h(m)
If f(m) has decreased and m ∈ CLOSED
move m to OPEN 59
6. Loop: Go To Step 2.
60
61
 A* 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.
 The time complexity is O(b^d), where b is the branching factor.
 The space complexity of A* search algorithm is O(b^d)

62
NOTION OF GOODNESS OF
HEURISTIC FUNCTION
Admissibility:
 A heuristic function h(n) is admissible if for every node n, h(n)<=f*(n)
where f*(n) is the true cost to reach the goal state from n.
 An admissible heuristic never overestimates the cost to reach the goal

63
NOTION OF GOODNESS OF
HEURISTIC FUNCTION
Consistent heuristics:
 h(n) is consistent if
 For every node n
 For every successor n’ due to some action a
 h(n) <= c(n,a,n’) + h(n’)

64
RESULTS ON A* ALGORITHM
 A heuristic is called admissible if it always under-estimates, that is, we
always have h(n) ≤ f*(n), where f*(n) denotes the minimum distance to a
goal state from state n.
 For finite state spaces, A* always terminates
 At any time before A* terminates, there exists in OPEN a state n that is on
an optimal path from s to a goal state, with f(n) ≤ f*(s)
 If there is a path from s to a goal state, A* terminates (even when the state
space is infinite)
 Algorithm A* is admissible, that is, if there is a path from s to a goal state,
A* terminates by finding an optimal path

65
HILL CLIMBING SEARCH
 Like “climbing Everest in thick fog with amnesia”
 ‘Heuristic search’ means that this search algorithm may not find the optimal
solution to the problem. However, it will give a good solution in reasonable
time.
 Hill climbing algorithm is a local search algorithm which continuously moves in
the direction of increasing elevation/value to find the peak of the mountain or
best solution to the problem. It terminates when it reaches a peak value where
no neighbor has a higher value.
 Hill climbing is a technique which is used for optimizing the mathematical
problems.
 Given a large set of inputs and a good heuristic function, the algorithm tries to
find the best possible solution to the problem in the most reasonable time
period.
 This solution may not be the absolute best (global optimal maximum) but it is
sufficiently good considering the time allotted.
66
FEATURES OF HILL CLIMBING
 Variant of generate and test algorithm: It is a variant of generate and
test algorithm. The generate and test algorithm is as follows :
1. Generate possible solutions.
2. Test to see if this is the expected solution.
3. If the solution has been found quit else go to step 1.
Hill climbing as a variant of generate and test algorithm as it takes the feedback
from the test procedure. Then this feedback is utilized by the generator in deciding
the next move in search space.
 Uses greedy approach: At any point in state space, the search moves in
that direction only which optimizes the cost of function with the hope of
finding the optimal solution at the end.
 No backtracking: It does not backtrack the search space, as it does not
remember the previous states.

67
STATE SPACE DIAGRAM FOR HILL
CLIMBING
 Local maximum: It is a state which is better than
its neighboring state however there exists a state
which is better than it(global maximum). This
state is better because here the value of the
objective function is higher than its neighbors.
 Global maximum : It is the best possible state in
the state space diagram. This because at this
state, objective function has highest value.
 Plateau/flat local maximum : It is a flat region
of state space where neighboring states have the
same value.
 Ridge : It is a region which is higher than its
The aim is to find the highest peak - a global
neighbor’s but itself has a slope. It is a special kind
maximum.
of local maximum.
 Current state : The region of state space
diagram where we are currently present during
the search.
 Shoulder : It is a plateau that has an uphill edge. 68
STATE SPACE DIAGRAM FOR HILL
CLIMBING
 A local maximum is a peak that is higher than
each of its neighboring states but lower than the

global maximum.
 Hill-climbing algorithms that reach the vicinity of
a local maximum will be drawn upward toward
the peak but will then be stuck with nowhere
else to go.
 A plateau is a flat area of the state-space
landscape. It can be a flat local maximum, from
which no
uphill exit exists, or a shoulder, from which
progress is possible.
 A hill-climbing search might get lost on the
plateau.
 Random sideways moves can escape from
shoulders but they loop forever on flat maxima.

69
TYPES OF HILL CLIMBING
 Simple Hill Climbing: 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 since it needs low computation power
 The algorithm results in sub-optimal solutions
 The solution is not guaranteed

Algorithm
Step 1 : Evaluate the initial state. If it is a goal state then stop and return success. Otherwise,
make initial state as current state.
Step 2 : Loop until the solution state is found or there are no new operators present which
can be applied to the current state.
a) Select a state that has not been yet applied to the current state and apply it to
produce a new state.
b) Perform these to evaluate new state
i. If the current state is a goal state, then stop and return success.
ii. If it is better than the current state, then make it current state and proceed
further. 70
iii. If it is not better than the current state, then continue in the loop until a solution
TYPES OF HILL CLIMBING
 Steepest-Ascent Hill Climbing: variation of simple hill climbing algorithm. It
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 for multiple
Algorithm
Step 1 : Evaluate the initial state. If it is a goal state then stop and return success.
Otherwise, make initial state as current state.
Step 2 : Repeat these steps until a solution is found or current state does not change
a) Select a state that has not been yet applied to the current state.
b) Initialize a new ‘best state’ equal to current state and apply it to produce a
new state.
c) Perform these to evaluate new state
i. If the current state is a goal state, then stop and return success.
ii. If it is better than best state, then make it best state else continue loop
with another new state.
d) Make best state as current state and go to Step 2: b) part.
Step 3 : Exit
71
TYPES OF HILL CLIMBING
 Stochastic hill climbing: does not examine for all its neighbours before
moving. Rather, this search algorithm selects one neighbour node at random
and evaluate it as a current state or examine another state.
 Algorithm
Step 1: Evaluate the initial state. If it is a goal state then stop and return
success. Otherwise, make the initial state the current state.
Step 2: Repeat these steps until a solution is found or the current state does
not change.
a) Select a state that has not been yet applied to the current state.
b) Apply successor function to the current state and generate all the
neighbor states.
c) Among the generated neighbor states which are better than the
current state choose a state randomly (or based on some probability
function).
d) If the chosen state is the goal state, then return success, else make it
the current state and repeat step 2: b) part.
Step 3: Exit. 72
PROBLEMS IN HILL CLIMBING
 Hill climbing cannot reach the optimal/best state(global maximum) if it enters any
of the following regions:
1. Local maximum : At a local maximum all neighboring states have a values which
is worse than the current state. Since hill-climbing uses a greedy approach, it will
not move to the worse state and terminate itself. The process will end even though
a better solution may exist.
Solution: Utilize backtracking technique. Maintain a list of visited states. If the
search reaches an undesirable state, it can backtrack to the previous configuration
and explore a new path.
2. Plateau : On plateau all neighbors have same value. Hence, it is not possible to
select the best direction.
Solution: Make a big jump. Randomly select a state far away
from the current state. Chances are that we will land at a non-plateau region
3. Ridge : Any point on a ridge can look like peak because movement in all possible
directions is downward. Hence the algorithm stops when it reaches this state.
Solution: In this kind of obstacle, use two or more rules before testing. It implies
moving in several directions at once.
73
APPLICATIONS OF HILL CLIMBING
 Network-Flow, Travelling Salesman problem, 8-Queens problem, Integrated
Circuit design, etc.
 Hill Climbing is used in robotics for coordination among multiple robots in a
team.

74
8-PUZZLE PROBLEM USING HILL
CLIMBING
H=no. of
misplaced tiles
Local maxima or
approximate solution

75
8-PUZZLE PROBLEM USING HILL
CLIMBING 8-puzzle: a solution case

76
8-PUZZLE PROBLEM USING HILL
CLIMBING 8-puzzle: stuck at local maximum

77
8-QUEENS PROBLEM USING HILL
CLIMBING
Put n queens on an n ×n board with no two queens on the same row, column, or
diagonal
• Move a queen to reduce number of conflicts.
Objective function: number of conflicts (no conflicts is global minimum)

 The successors of a state are all possible states generated by moving a single queen
to another square in the same column (so each state has n*(n-1) successors).
 The heuristic cost function h is the number of pairs of queens that are attacking each
other, either directly or indirectly.
 The global minimum of this function is zero, which occurs only at perfect solutions.
78
8-QUEENS PROBLEM USING HILL
CLIMBING
 h = ? for the following state Local minimum

five steps to reach this state

The value of h for each possible successor h=?

obtained by moving a queen within its If you move any queen, can you escape
column. from local minima? 79
HILL CLIMBING
 Hill Climbing is NOT complete.
 Hill Climbing is NOT optimal.

 Why use local search?

• Low memory requirements – usually constant
• Effective – Can often find good solutions in extremely large state spaces
• Randomized variants of hill climbing can solve many of the drawbacks in practice.

80
SIMULATED ANNEALING
 Simulated Annealing is an algorithm which yields both efficiency and
completeness.
 In mechanical term Annealing is a process of hardening a metal or glass
to a high temperature then cooling gradually, so this allows the metal to
reach a low-energy crystalline state.
 The same process is used in simulated annealing in which the algorithm
picks a random move, instead of picking the best move. If the random
move improves the state, then it follows the same path. Otherwise, the
algorithm follows the path which has a probability of less than 1 or it moves
downhill and chooses another path.

81
SIMULATED ANNEALING
 A hill-climbing algorithm that never makes “downhill” moves toward states with
lower value (or higher cost) is guaranteed to be incomplete, because it can get stuck
on a local maximum.
 In contrast, a purely random walk—that is, moving to a successor chosen uniformly
at random from the set of successors—is complete but extremely inefficient.
 Therefore, it seems reasonable to combine hill climbing with a random walk in some
way that yields both efficiency and completeness.
 Idea: escape local maxima by allowing some “bad” moves but gradually decrease
their size and frequency.
 The simulated annealing algorithm, a version of stochastic hill climbing where some
downhill moves are allowed.
 Annealing: the process of gradually cooling metal to allow it to form stronger
crystalline structures
 Simulated annealing algorithm: gradually “cool” search algorithm from Random Walk
to First-Choice Hill Climbing (First-choice hill climbing implements stochastic hill
climbing by generating successors randomly until one is generated that is better
than the current state. This is a good strategy when a state has many of successors)
82
SIMULATED ANNEALING -
APPLICATIONS
 Traveling Salesman Problem
 Graph partitioning
 Matching problem
 Quadratic Assignment
 Linear Arrangement
 Scheduling
 etc.

83
SIMULATED ANNEALING
ALGORITHM

84
SIMULATED ANNEALING

85
SIMULATED ANNEALING –
EXAMPLE
 Let us maximize the continuous function

f (x) = x3 - 60x2 + 900x + 100

 A solution x is represented as a string of 5 bits.
 The neighborhood consists in flipping randomly a bit.
 The initial solution is 10011 (x = 19, f (x) = 2399)
 Testing two sceneries:
 First scenario: initial temperature T0 equal to 500.
 Second scenario: initial temperature T0 equal to 100.

 Cooling: T = 0.9 . T

86
SIMULATED ANNEALING –
EXAMPLE
 First Scenario T = 500 and Initial Solution (10011)

87
STIMULATED ANNEALING –
EXAMPLE
 Second Scenario: T = 100 and Initial Solution (10011)

 When Temperature is not High Enough, Algorithm Gets Stuck

88
GENETIC ALGORITHM
 A genetic algorithm is a search heuristic that is
inspired by Charles Darwin’s theory of natural evolution.
 The fittest individuals are selected for reproduction in
order to produce offspring of the next generation.
 If parents have better fitness, their offspring will be
better than parents and have a better chance at
surviving.
 This process keeps on iterating and at the end, a
generation with the fittest individuals will be found.
 Principles of GA based on two fundamental biological
processes:
 Genetics
 Evolution
89
GENETICS
GENETICS
GENETICS
GENETICS – CROSSOVER
EVOLUTION – SELECTION
EVOLUTION
WORKING OF GA
SOLVING OPTIMIZATION
PROBLEM USING GA
GENETIC ALGORITHM
 Search based optimization technique
 Uses the concept of evolutionary biology
 Pool or a population of possible solutions to the given
problem
 John Holland introduced in 1975
MOTIVATION
 GA has the ability to deliver a “good-enough”
solution “fast-enough”
 Solving difficult problems
 GAs prove to be an efficient tool to provide usable
near-optimal solutions in a short amount of time
 Getting a good solution fast
BASIC STRUCTURE OF GA
101
KNAPSACK PROBLEM USING GA
7 24

2
1

1
1
Selected in 1st
spin
GENETIC ALGORITHM
 Five phases are considered in a genetic algorithm:
 Initial population
 Fitness function
 Selection
 Crossover
 Mutation

114
GENETIC ALGORITHM
 GA begins with a set of k randomly generated states, called population.
 Each state, or individual, is represented as a string over a finite alphabet—most
commonly, a string of 0s and 1s.
 An 8-queens state must specify the positions of 8 queens, each in a column of 8
squares, and so it requires 8×log28=24 bits.
 Alternatively, the state could be represented as 8 digits, each in the range from
1 to 8.
 Each state is rated by an objective function, or (in GA terminology) the fitness
function.
 Pairs of individuals are randomly selected for reproduction.
 From each pair new offsprings (children) are generated using crossover
operation.
 A crossover point is chosen randomly from the positions in the string.
 The offsprings are created by crossing over the parent strings at the crossover
point.
 Each child is subject to random mutation with a small independent probability. 115
GENETIC ALGORITHM
 A state can be represented using a 8 digit string.
 Each digit in the range from 1 to 8 to indicate the position of
the queen in that column.

116
GENETIC ALGORITHM

117
GENETIC ALGORITHM

118
GENETIC ALGORITHM

119
GENETIC ALGORITHM

120
GENETIC ALGORITHM

121
GENETIC ALGORITHM

122
PROBLEM REDUCTION SEARCH
 Planning how best to solve a problem that can be recursively
decomposed into sub-problems in multiple ways
 Matrix multiplication problem
 Tower of Hanoi
 Blocks World problems

123
 FORMULATIONS
 AND/OR Graphs - Useful for representing the
solution of problems that can be solved by
decomposing them into a set of smaller
problems, all which must be solved.
 An OR node represents a choice between possible
decompositions
 An AND node represents a given decomposition

124
 AND/OR GRAPH SEARCH
PROBLEM
 Problem definition:
 Given: [G, s, T] where
 G: implicitly specified AND/OR graph
 S: start node of the AND/OR graph
 T: set of terminal nodes
 h(n) heuristic function estimating the cost of solving
the sub-problem at n

 To find:
 A minimum cost solution tree

125
126
127
 ALGORITHM AO*
1. Initialize: Set G* = {s}, f(s) = h(s)
If s ∈T, label s as SOLVED
2. Terminate: If s is SOLVED, then Terminate
3. Select: Select a non-terminal leaf node n from the marked
sub-tree
4. Expand: Make explicit the successors of n
For each new successor, m:
Set f(m) = h(m)
If m is terminal, label m SOLVED
5. Cost Revision: Call cost-revise(n)
6. Loop: Go To Step 2.
128
 COST REVISION IN AO*
cost-revise(n):
1. Create Z = {n}
2. If Z = { } return
3. Select a node x from Z such that x has no descendants in Z
//descendants are not in
Z
4. If x is an AND node with successors r1, r2, … rk:

Set f(x) = Σ[ f(ri) + c(x, ri) ]

Mark the edge to each successor of x
If each successor is labeled SOLVED, then label x as SOLVED

129
 COST REVISION IN AO*
5. If x is an OR node with successors r1, r2, … rk :
Set f(x) = min {f(ri)+c(x, ri)}
Mark the edge to the best successor of x
If the marked successor is labelled SOLVED, label x as SOLVED
6. If the cost or label of x has changed, then insert those parents of x
into Z for which x is a marked successor
7. Goto Step2.

130
 ADVERSARIAL SEARCH
 Adversarial search is a search, where we examine the
problem which arises when we try to plan ahead of the
world and other agents are planning against us.
 More than one agent is searching for the solution in the
same search space, and this situation usually occurs in
game playing.
 The environment with more than one agent is termed as
multi-agent environment, in which each agent is an
opponent of other agent and playing against each other.
Each agent needs to consider the action of other agent and
effect of that action on their performance.

131
 ADVERSARIAL SEARCH
 Searches in which two or more players with conflicting goals
are trying to explore the same search space for the
solution, are called adversarial searches, often known as
Games.
 Games are modeled as a Search problem and heuristic
evaluation function, and these are the two main factors
which help to model and solve games in AI.

132
 GAME PLAYING
 Games with the following characteristics:
 Sequence of moves to play
 Rules that specify possible moves
 Rules that specify a payment for each move
 Objective is to maximize the payment

133
 GAMES VS SEARCH PROBLEMS
 Unpredictable opponent: specify a move for every possible
opponent reply
 Time limits: unlikely to find a goal, must approximate

134
 SEARCHING GAME TREES
 Consider an OR tree with two types of OR nodes,
namely Min nodes and Max nodes
 In Min nodes, select the min cost successor
 In Max nodes, select the max cost successor

 Terminal nodes are winning or loosing states

 It is often infeasible to search up to the terminal nodes
 We use heuristic costs to compare non-terminal nodes

135
136
 GAMES AS ADVERSARIAL
 States:
SEARCH
 board configurations
 Initial state:
 the board position and which player will move
 Successor function:
 Returns list of (move,state) pairs, each indicating a legal
move and the resulting state
 Terminal test:
 determines when the game is over
 Utility function:
 gives a numeric value in terminal states

137
GAME TREE

138
 MINI MAX TERMINOLOGY
 Move: move by both players
 Ply: a half-move
 Utility function: the function applied to leaf nodes
 Backed-up value:
 Of a max-position: the value of its largest successor
 Of a min-position: the value of its smallest successor
 Minimax procedure: search down several levels; at
the bottom level apply the utility function, back-up
values all the way upto the root node, and that
node selects the move.
139
140
SHALLOW AND DEEP PRUNING

141
142
 ALPHA-BETA PRUNING
 Proposed by Donald Knuth
 Alpha Bound of J:
 The max current val of all MAX ancestors of J
 Exploration of a min node, J, is stopped when its value equals or falls
below alpha.
 In a min node, update beta

 Beta Bound of J:
 The min current val of all MIN ancestors of J
 Exploration of a max node, J, is stopped when its value equals or exceeds
beta
 In a max node, update alpha

 In both min and max nodes, we return when α≥β

143
 ALPHA-BETA PRUNING
V(J; α, β) PROCEDURE
1. If J is a terminal, return V(J) = h(J)
2. If J is a max node:
For each successor Jk of J in succession:
Set α= max { α, V(Jk; α, β) }
If α≥β then return β, else continue
Return α
3. If J is a min node:
For each successor Jk of J in succession:
Set β= min { β, V(Jk; α, β) }
If α≥β then return α, else continue
144
Return β