Problem Solving by

Search
2
3
Problem Solving
An autonomous agent
in some world
has a goal to achieve
and
a set of actions to choose from
to strive for the goal

4
Goal of AI
• To develop universal intelligence system to match
the intelligence capabilities of human beings
• Many AI systems developed are of problem specific
domain
• Application of AI is to develop intelligent systems to
solve the real world problems

5
Building AI Computational System
• Define the problem precisely – initial and goal
• Analyze the problem
• Isolate and represent the task knowledge that is
necessary to solve the problem
• Choose the best problem solving techniques and
apply it to the particular problem

6
Intelligent Agent
• An intelligent agent is a rational agent which has clear preference,
models uncertainty, and acts in a way to maximize its performance
measure with all possible actions.
• Learns from environment to achieve its goal.
• A rational agent is said to perform the right things.
• Abstractly, an agent is a function from percept histories to actions:
f : P*  A
• Agents have inherent goals that they want to achieve

7
Production System
• Set of Production rules – P  Q ; P – Current Problem State,
Q - result or generated output state
• One or more knowledge databases
• A control strategy – order in which the rule will be compared to the
database
• Rule Applier - Check the applicability of the rule by matching the
current state with the left hand side of the rule and finds the
appropriate rule from the database

8
Algorithm of Problem Solving

9
 Problem solving using search
• Search is an important problem-solving tool

• Search is about exploring alternatives

• It is a major approach to exploit knowledge

10
 Searching
• In general, finding a solution
• In a website finding answer for a question
• In a city finding a correct path
• In a chess finding the next best step to move
and many more …

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

11
 Properties of search
algorithms
• Completeness: A search algorithm 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)

12
 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: 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.

13
 Problem Definition and
Solution
• Given: [S, si, O, G], where
• S is the (implicitly specified) full set of states
• si ɛ S is the start state
• O: SS is the set of state transition operators
• G is the set of goal states
• A path in the state space is a sequence of state connected by a sequence of
actions
• Solution : A sequence of state transitions(path) leading from Start State(si) to
a Goal state (G)

14
Search Problem

15
8-puzzle problem

16
 8-Puzzle problem
• State description (S)
• Location of each of the eight tiles (and the blank)
• Start state (si)
• 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)

17
8-puzzle problem–search tree

18
 8-queens problem
• Placing 8 queens on a chess board, so that none attacks the other
• A queen can move horizontally, vertically and diagonally

19
4-Queens problem
• Goal State

20
Water Jug Problem
• You are given two jugs, a 4-gallon one and a 3-gallon one. Neither has
any measuring markers on it. There is a pump that can be used to fill
the jugs with water. How can you get exactly 2 gallons of water into
the 4-gallon jug.
• State space : set of ordered pairs of integers (x,y),
where x=0, 1, 2, 3 or 4 and y=0, 1, 2, or 3
• Start State : (0, 0)
• Goal State : (2, n)

21
 (0,0)

(4,0) (0,3)

(4,3) (0,0) (1,3) (4,3) (0,0) (3,0)

A search Tree for the Water Jug Problem

22
Operator Rules
• (x,y)  (4,y) , if x<4 • (x,y)(x+y,0) if x+y < 4 and y>0
• (x,y)  (x,3) , if y<3 • (x,y)(0,x+y) if x+y < 3 and x>0
• (x,y)  (x-d,y), if x>0 • (0,2)  (2,0)
• (x,y)  (x,y-d), if y>0 • (2,y) (0,y
• (x,y)  (0,y) , if x>0
• (x,y)  (x,0) , if y>0
• (x,y)(4,y-(4-x)) if x+y > 4 and y>0
• (x,y)(x-(3-y),3) if x+y > 3 and x>0

23
One Solution
4-Gallons Jug 3-Gallons Jug Rule Applied
0 0
0 3 2
3 0 9
3 3 7
4 2 5 or 12
0 2 9 or 11
2 0

24
 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
• Boat position in the near(0) or far(1) 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)

25
Missionaries and cannibals
solution

26
Route Finding Problem

Total Cost =Path Cost + Search Cost

27
Search Approaches
Search Algorithms

Uninformed/Blind Informed Search

Hill Climbing
Breadth First
Best First

Depth First
A* Search
Uniform Cost

Bidirectional

28
Uninformed search
• Does not contain domain knowledge
• Brute force search – operates in a brute force way
• Blind search

29
Informed search
• Guided with domain knowledge
• Efficient compare to uninformed search
• Heuristic search

30
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)

31
Search Algorithm – Traversal in a
Tree
OPEN – Queue Structure (FIFO)

32
 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.

33
 Depth First Search
• 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.

34
Depth First Search-Algorithm
1. If the initial state is the goal state, quit and return Success
2. Otherwise do the following until the success or failure is
signaled:
a) Generate a successor, E, of the initial state. If there are no more
successor, signal failure.
b) Call depth first search with E as the initial state
c) If the success is returned, signal success. Otherwise continue in
this loop.

35
Example

36
 Depth First Search
• 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(bm) (needs to store only single path from the
root node)
• Optimality: Non-optimal as it may generate a large number of
steps or high cost to reach to the goal node.
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 ∞)

37
Example Start State 1
Goal State 8

38
Solve using DFS

39
 Breadth First Search
• 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:
• Require 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

40
Breadth First Search

41
Example

42
Solve using BFS

43
 Breadth First Search
• 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 step cost is 1. For multiple step cost it
may not be optimal

44
 Informed state space search /
Heuristic search
• Heuristics use domain specific knowledge to estimate the quality
or potential of partial solutions
• A problem solving agent finds a path in a state-space graph from
start state to goal state, using heuristics
• A quick way to estimate how close we are to the goal from the
current state
•Heuristics are fundamental to chess:
• h(n) – estimated cost of the cheapest path from state ‘n’ to goal
state [ For goal state, h(n) = 0]

45
46
HEURISTICS FOR 8 PUZZLE

47
48
 Informed Search Problem

• Given: [S, si, O, G, h]

• S - set of states
• si - start state
• O - set of state transition operators each having some cost
• G - set of goal states
• h( ) - heuristic function estimating the distance to a goal

• To find:
• A min cost sequence of transitions to a goal state

49
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
• Always selects the path which appears best at that moment.
• Combination of depth-first search and breadth-first search
algorithms.
• Uses the heuristic function and search.

50
51
Greedy Best first search
Advantages
 Greedy best-first search is more efficient compared with breadth-first search
and depth-first search.
Disadvantages
 In the worst-case scenario, the greedy best-first search algorithm may behave
like an unguided DFS.
 There are some possibilities for greedy best-first to get trapped in an infinite
loop.
 The algorithm is not an optimal one.
 Sometimes, it covers more distance than our consideration.

52
 A* SEARCH
 Idea:
 avoid expanding paths that are already expensive
 focus on paths that show promise

 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

53
 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 54
6. Loop: Go To Step 2.
55
56
8-PUZZLE PROBLEM USING A*

57
 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.
 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)

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

Consistent:

59
RESULTS ON A* ALGORITHM
 A heuristic is called admissible if it always under-estimates, that is, we
always have h(n) ≤ g(n), where g(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) ≤ g(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

60
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.
61
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.
62
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 neighbor’s The aim is to find the highest peak - a global
but itself has a slope. It is a special kind of local maximum.
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.
63
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. 64
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.
iii. If it is not better than the current state, then continue in the loop until a solution is found.
Step 3 : Exit.
65
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 66
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.
67
Step 3: Exit.
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.
68
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.

69
8-puzzle problem using Hill
climbing
H=no. of
misplaced tiles
Local maxima or
approximate solution

70
8-puzzle problem using Hill
climbing

71
8-puzzle problem using Hill
climbing 8-puzzle: stuck at local maximum

72