2.

Search Methods
 Search Overview
• Solving a problem means looking for a solution,
which is best among others. Finding a solution to a
problem in Computer Science and Artificial
Intelligence (AI), is often thought as a process of
search through some space of possible solutions

• Search is inherent to the problems and methods of

AI. Efforts to solve problems with computers which
humans can routinely solve by employing innate
cognitive abilities, pattern recognition, perception
and experience, invariably must turn to
considerations of search.
 Search Overview (2)
• Many analytical problems can be solved by
searching through a space of possible states.
• Starting from an initial state, we try to reach a
goal state
• The sequence of actions leading from initial to
goal state is the solution to the problem
• The purpose of searching is thus to find the
path to desired Goal State from all future states
possible.
 Search Overview (3)
• In many problems, the sequence of steps
required to solve is not known in advance but
must be determined by systematic
trial-and-error exploration of alternatives
• The larger the number of states, the many the
choices to make in each state, the more
complicated the search can get.
 Search Overview (4)
• Searching is the universal technique of
problem solving in AI. There are some
single-player games such as tile games,
Sudoku, crossword, etc. The search
algorithms help you to search for a particular
position in such games.
Search Overview (5)
 Search Overview (6)
• In fact, most search problems are models of the
real world
 Real-World Search Problems
1. Route Finding (computer networks, airline travel
planning system, . . . )
2. Travelling Salesman Optimization Problem
(package delivery, automatic drills, . . . )
3. Layout Problems (VLSI layout, furniture layout,
packaging, . . . )
4. Assembly Sequencing (assembly of electric
motors, . . . )
5. Task Scheduling (manufacturing, timetables, . )
A. Search used in Route Planning
B. Search used in Robot Navigation
C. Search used for Planning
in the Blocks World
D. Search in the 8 Queens Problem

The above is almost a solution, but not quite . . .

E. Search in the
Eight-Puzzle Problem
 Search and Optimisation Problems
• All these problems have got a common structure:
– We are faced with an initial situation and we would like to
achieve a certain goal.
– At any point in time we have different simple actions
available to us (e.g. “turn left” vs. “turn right”). Executing a
particular sequence of such actions may or may not achieve
the goal.
– Search is the process of inspecting several such
sequences and choosing one that achieves the goal.
– For some applications, each sequence of actions may be
associated with a certain cost. A search problem where we
aim not only at reaching our goal but also at doing so at
minimal cost is an optimisation problem.
 The State-Space Representation
1. State space: What are the possible states?
▪ E.g. In Route planning: various cities
▪ E.g. In Blocks World: configuration of blocks
▪ A concrete problem must also specify the initial state.
2. Operations/ Moves: What are legal moves
between states?
▪ E.g.: Turning 45◦ to the right could be a legal move
for a robot.
▪ Putting block A on top of block B is not a legal
move if block C is currently on top of A.
 The State-Space Representation (2)
3. Goal state: When have we found a solution?
– E.g.: – Route planning: position = “Plantage
Muidergracht 24”

4. Cost function: How costly is a given move?

– E.g.: – Route planning: The cost of moving from
position X to position Y could be the distance
between the two.
 The 4 Puzzle Problem
– Identify and list operators applicable to this game
– An identification of all possible moves of the blank
cell e.g. BL-up, BL-down and BL-right, BL-left
where (BL represents a BLANK CELL)
• Draw the state space for the problem below
The 4 Puzzle Problem (2)
 Searching the State Space

• The set of all possible sequences of legal moves

form a tree:
– The nodes of the tree are labelled with states (the
same state could label many different nodes)
– The initial state is the root of the tree.
– For each of the legal follow-up moves of a given state,
any node labelled with that state will have a child
labelled with the follow-up state.
– Each branch corresponds to a sequence of states (and
thereby also a sequence of moves).
– For most problems, we can never actually build the
whole tree
 Evaluating Search’s Performance
1. Completeness: - Is that algorithm guaranteed
to find a solution when there is one? An
algorithm is complete iff it finds a solution
whenever the solution exists

2. Optimality: - Does that strategy find the

optimal solution? always be the optimal
solution. an algorithm is optimal iff the
solution it finds is optimal (has the smallest
cost)
Evaluating Search’s Performance (2)
3. Time Complexity: - How long does it take to
find a solution? In other words how many
NODES ARE GENERATED to find the
solution?

4. Space Complexity: - How much memory is

needed to perform the search? In other words,
how many NODES ARE STORED, to find
the solution
 Evaluating Search’s Performance (3)
1. Branching factor of the search space (b):
▪ how many operators (at most) can be applied at any time?
▪ E.g. For the eight-puzzle problem, the branching factor is
considered 4, although most of the time we can apply only
2 or 3 operators.

2. Solution depth (d):

▪ how long is the path to the closest (shallowest) solution?

3. Maximum length (m): of any path in the search

space
Evaluating Search’s Performance (4)
• We may be interested in both a worst-case and
an average-case complexity analysis.
– Worst-case analysis: How much time/memory
will the algorithm require in the worst case?

– Average-case analysis: How much time/memory

will the algorithm require on average?
 Classifying Search Algorithms
• Search problems can be classified by the amount of
information that is available to the search process.

• Such information might relate to the problem space as a

whole or to only some states. It may be available a priori or
only after a node has been expanded. On such basis we can
categorize different search techniques as uninformed or
informed searches.

• Uninformed search methods are also called blind/ brute

force methods, whereas informed search methods are also
called heuristic methods. We will focus on these more in our
next meetings.