Problem-Solving

Search Techniques

1
Introduction

† Some problems are defined in terms of

states and solutions correspond to goal
states. Thus, search techniques are needed.

2
Introduction (cont.)
† Example: playing a chess game
„ Each board configuration can be thought of
representing a different state of the game.
„ A change of state occurs when one of the
player moves a piece.
„ A goal state is any of the possible board
configurations corresponding to a
checkmate.

3
Introduction (cont.)

† Chess game has more than 10120 possible states.

† Winning a game amounts to finding a sequence
of states through many possible states that
leads to one of goal states.
† An intelligent chess playing program would not
play the game by exploring all possible moves.
† Potential hypotheses must be considered before
a good one is chosen.

4
Introduction (cont.)
† Other examples using search techniques
„ To understand a natural language, a program
must search to find matching words from a
dictionary, sentence constructions, and matching
contexts.
„ To perceive an image, program searches must be
performed to find model patterns that match input
scenes.
„ etc

5
Preliminary Concepts
† Programs can be characterized as a space
consisting of a set of states, and a set of
operators that map from one state to other
states.
† Three types of states:
„ one or more initial states
„ a number of intermediate states
„ one or more goal states

6
Preliminary Concepts (cont.)
† A solution to a problem is a sequence of
operations that map an initial state to a goal
state.
† A good solution is one that requires the
fewest operations or the least cost to map
from an initial state to a goal state.
† The performance of a particular method is
judged by the amount of time and memory
required to complete the mapping.

7
Preliminary Concepts (cont.)
† A solution based on some algorithm A1 is
considered better than one using algorithm A2 if
the time and space complexity of A1 is less than
that of A2.

8
Preliminary Concepts:
Time and space complexity
† Time and space complexities of an algorithms
may be defined in terms of their best, their
average, or their worst-case performance in
completing some task.

9
Preliminary Concepts:
Graph and Tree representation
† Traditionally a search space is represented as a
diagram of a directed graph or a tree.
„ Each node or vertex in the graph
corresponds to a problem state.

„ Arcs between nodes correspond to

transformations or mappings between the
states.

10
Preliminary Concepts:
Graph and Tree representation (cont.)
† The immediate successors of a node are
referred to as children, sibling or offspring.

† The predecessor nodes are ancestors.

† An immediate ancestor to a node is a

parent.

11
Preliminary Concepts:
Graph and Tree representation (cont.)
† A tree is a graph which each node has at most
one parent.

† The root or starting node has no parent.

† Leaf or terminal nodes are nodes without

children.

12
Preliminary Concepts:
Graph and Tree representation (cont.)
† The number of successors emanating from a
node is called the branching degree of that
node (denoted as b)

† A path is a sequence of nodes n1, …, nk where

each ni is a successor of ni-1 for i =1, …, k.

† It is possible to convert a graph into a tree.

13
Preliminary Concepts:
Graph and Search Tree
† A Search Procedure is a strategy for selecting
the order in which nodes are generated and a
given path selected.

† Search problems may be classified by the

information used to carry out a given strategy:
„ Blind Search (Uninformed Search)
„ Directed Search (Informed Search)

14
Preliminary Concepts:
Graph and Search Tree (cont.)

† Blind Search:
„ No preference is given to the order of
successor node generation and selection.

„ The path selected is blindly followed.

15
Preliminary Concepts:
Graph and Search Tree (cont.)
† Informed Search:
„ Some information about the problem
space is used to compute a preference
among the children for exploration and
expansion.

16
Examples of Search Problems

† Eight Puzzle

† Traveling Salesman Problem

17
Examples of Search Problems:
Eight Puzzle

† The eight puzzle consists of 3-by-3 square

frame which hold eight movable square
tiles which are numbered from 1 to 8.
† One square is empty, permitting tiles to be
shifted.
† The objective is to find a sequence of tile
movement that leads from a starting
configuration to a goal configuration.
18
Examples of Search Problems:
Eight Puzzle (cont.)

3 8 1 1 2 3
6 2 5 8 4
4 7 7 6 5

Start configuration Goal configuration

19
Examples of Search Problems:
Eight Puzzle (cont.)

† The states of the eight puzzle are the

different permutations of the tiles within
the frame…… ?

† The operations are the permissible moves

„ up, down, left, right.

20
Examples of Search Problems:
Eight Puzzle (cont.)

† An optimal or good solution is one that

maps an initial arrangement of tiles to the
goal configuration with the smallest
number of moves.

† The search space for the eight puzzle

problem is depicted as the tree structure.

21
Examples of Search Problems:
Eight Puzzle (cont.)

† In the tree structure,

„ the nodes are depicted as puzzle
configurations,
„ the root node represents a randomly chosen
starting configuration,
„ its successor nodes correspond to the
movements that are possible.
„ A path is a sequence of nodes starting from
the root and progressing downward to the goal
node.
22
Examples of Search Problems:
Traveling Salesman Problem

† Traveling Salesman problem involves n

cities with paths connecting the cities.

† A tour is any path which begins with some

starting city, visits each of the other cities
exactly once, and returns to the starting
city.

23
Examples of Search Problems:
Traveling Salesman Problem (cont.)

Start

24
Examples of Search Problems:
Traveling Salesman Problem (cont.)

† The objective of a traveling salesman

problem is to find a minimal distance tour.

† To explore all such tour requires an

exponential amount of time, for example, a
minimal solution with only 10 cities is 10!
(3,628,800 tours).

25
Uninformed or Blind Search

† Breadth-First Search

† Depth-First Search

† Depth-First Iterative Deepening

Search

26
Informed or Direct Search

† Hill Climbing Method

† Best-First Search

† Branch-and-Bound Search

† A* Search

27
 Blind Search

† A blind search algorithm is one that uses

no information other than the initial state,
the search operators, and a test for a
solution.

† A blind search should proceed in

systematic way by exploring nodes in
some predetermined order.

28
Blind Search:
Breadth-First Search

† Breadth-First Search are performed by

exploring all nodes at a given depth before
proceeding to the next level.

† Advantage: Always finding a minimum path

length solution when one exists.

† Disadvantage: A great many nodes may

need to be explored before a solution is
29
found.
Blind Search:
Depth-First Search

† Depth-first searches are performed by diving

downward into a tree.

† It generates a child node from the most

recently expand node, then generating that
child’s children, and so on until a goal is
found, or some cutoff depth point d is
reached.

30
Blind Search:
Depth-First Search (cont.)

† If a goal is not found when a leaf node is

reached or at the cutoff point, the program
backtracks to the most recently expanded
node and generates another of its children.

† This process continues until a goal is

found or failure occur.

31
Blind Search:
Depth-First Search (cont.)

† The depth-first is preferred over the

breadth-first when the search tree is
known to have a plentiful number of goals.

† The depth cutoff introduces some

problems. If it is set too shallow, goals may
be missed. If set too deep, extra
computation may be performed.

32
Blind Search:
Depth-First Iterative Deepening Search

† Depth-First Iterative Deepening Searches

are performed as a form of repetitive
depth-first search moving to a
successively deeper depth with each
iteration.

† It begins by performing a depth-first

search to depth of one.

33
Blind Search:
Depth-First Iterative Deepening Search (cont.)

† Then, it discards all nodes generated and

starts over doing a search of depth two.

† If no goal has been found, it discards all

nodes generated and does a depth-first
search to a depth of three.

34
Blind Search:
Depth-First Iterative Deepening Search (cont.)

† This process continues until a goal node is

found, or some maximum depth is reached.

† Advantage: It is guaranteed to find a shortest-

path solution.

† Disadvantage: It performs wasted

computations before reaching a goal depth.
35
 Informed Search

† Heuristic Information
„ Information about the problem such as
† the nature of the states,
† the cost of transforming from one state to
another,
† the promise of taking a certain path,
† etc.
„ It can be used to help guide the search more
efficiently.
36
Informed Search (cont.)

† Heuristic Information
„ This information can be expressed in the form
of a heuristic evaluation function f(n,g), a
function of the nodes n and/or the goals g.

37
Informed Search (cont.)

† Heuristic Information
„ A heuristic is a rule of thumb or judgmental
technique that leads to a solution some of the
time, but provides no guarantee of
success.

38
Informed Search (cont.)

† Heuristic Information
„ Heuristics play an important role in search
strategies because they help to reduce the
number of alternatives from an exponential
number to a polynomial number to obtain a
solution in a tolerable amount of time.

39
Informed Search:
Hill Climbing Method

† Hill climbing is named from the way the

nodes are selected for expansion.
† At each point in the search path, a successor
node that appears to lead most quickly to the
top of the hill (the goal) is selected for
exploration.
† This method requires information to evaluate
and order the most promising choices.

40
Informed Search:
Hill Climbing Method (cont.)

† Hill climbing is like depth-first searching

where the most promising child is selected
for expansion.

† When the children have been generated,

alternative choices are evaluated using some
type of heuristic function.

41
Informed Search:
Hill Climbing Method (cont.)

† The path that appears most promising is then

chosen and no further reference to the
parent or other children is retained.

† This process continues from node-to-node

with previously expanded nodes being
discarded.

42
Informed Search:
Hill Climbing Method (cont.)

† Hill climbing can produce substantial saving

over blind searches.

† Potential problems: foothill, ridge, and plateau

traps.

43
Informed Search:
Best-First Search

† Best-first search also depends on the use of

a heuristic to select most promising paths to
the goal node.

† This algorithm retains all estimates computed

for previously generated nodes and makes its
selection based on the best among them all.

44
Informed Search:
Best-First Search (cont.)

† At any point in the search process, best-first

search moves forward from the most
promising of all the nodes generated so far.

† Therefore, it avoids the potential traps

encountered in hill climbing.

45
Informed Search:
Best-First Search (cont.)

† Best-first search will always find good paths

to a goal, even when local anomalies are
encountered.

† It requires a good measure of goal distance.

46
Informed Search:
Branch-and-Bound Search

† Branch-and-Bound search strategy applies to

problems having a graph search space.

† It saves all path lengths or costs from a node

to all generated nodes and chooses the
shortest path for further expansion.

47
Informed Search:
Branch-and-Bound Search (cont.)

† Then, it compares the new path lengths with

all old ones and again chooses the shortest
path for expansion.

† Therefore, any path to a goal node is certain

to be a minimal length path.

48
Informed Search:
Branch-and-Bound Search (cont.)

† Branch-and-bound search insures that a

lowest-cost path will be found since it
always extends the lowest-cost path.

† It is at the expense of computing and

remembering all competing paths.

49
Informed Search:
*
A search

*
† A algorithm is a specialization of best-first
search.
† At each node, the A* algorithm generates all
successor nodes and computes an estimate
of distance (cost) from the start node to a
goal node through each of successors.
† Then, it chooses the successor with the
shortest estimated distance for expansion.

50
Informed Search:
A* search (cont.)

*
† Heuristic estimation function for A is
* * *
f (n) = g (n) + h (n),
where the two components are as follows:
*
„ g (n) is the estimate of cost or distance from
the start node to node n,
*
„ h (n) is the estimate of cost or distance from
node n to a goal node.

51