INT4204 Searching
INT4204 Searching
INT4204 Searching
INTELLIGENT SYSTEMS
SEARCHING
INTRODUCTION
Questions for designing search
algorithms
Is the problem solver guaranteed to find a
solution?
Will the problem solver always terminate?
When a solution is found, is it guaranteed to
be optimal?
What is the complexity of the search process?
How can the interpreter most effectively
reduce search complexity?
How can the interpreter effectively utilize a
representation language?
State space search is the tool for
answering these questions. 2
STATE SPACE SEARCH
Before an AI problem can be solved it must be
represented as a state space.
The state space is then searched to find a
solution to the problem.
A state space essentially consists of a set of
nodes representing each state of the problem,
arcs between nodes representing the legal moves
from one state to another, an initial state and a
goal state.
Each state space takes the form of a tree or a
graph.
PROBLEM FORMULATION
A problem is defined by :
1. A set of states
2. A start state
3. A goal state or goal test
4. A boolean function which tells us whether a given state is
a goal state
5. A successor function
6. Line a mapping from a state to a set of new states
2
SEARCH AND PROBLEM
SOLVING
5
SEARCH AND PROBLEM
SOLVING
6
SEARCH AND PROBLEM
SOLVING
7
SEARCH AND PROBLEM
SOLVING
8
SIMPLE EXAMPLE
Easiest to first look at simple examples based on
searching for route on a map.
School Factory
Hospital Newsagent
Library church
Park University
9
SEARCH SPACE
The set of all possible states reachable from the initial state defines
the search space.
We can represent the search space as a tree.
library
school hospital
park newsagent
factory
university church
11
SEARCH STRATEGIES
Two main categories of searching:
1. uninformed search – no information about
the number of steps or the path cost from
the current state to the goal. It is also called
blind search
Breadth-First Search (BFS)
Depth-First Search (DFS)
12
BREADTH-FIRST SEARCH (BFS)
It starts from the root node, explores the
neighboring nodes first and moves towards the
next level neighbors.
It generates one tree at a time until the solution
is found. It can be implemented using FIFO
queue data structure.
This method provides shortest path to the
solution.
EXAMPLE :BFS
DEPTH-FIRST SEARCH
(DFS)
It is implemented in recursion with LIFO stack
data structure.
It creates the same set of nodes as Breadth-
First method, only in the different order.
Explores a path all the way to a leaf before
backtracking and exploring another path
As the nodes on the single path are stored in
each iteration from root to leaf node, the space
requirement to store nodes is linear.
DEPTH-FIRST SEARCH (DFS) :
EXAMPLE
DFS AND BFS
ALGORITHMS
COMPARE DFS AND BFS
DFS BFS
Depth-first vs. Breadth-
Advantages of depth- first
Advantages of breadth-
first: first:
• Simple to implement; • Guaranteed to find a
• Needs relatively small solution (if one exists);
memory for storing the • Depending on the problem,
state-space. can be guaranteed to find
an optimal solution.
Disadvantages of Disadvantages of
depth-first: breadth-first:
• Can sometimes fail to find • More complex to
a solution; implement;
• Not guaranteed to find an • Needs a lot of memory for
optimal solution; storing the state space if
• Can take a lot longer to the search space has a high
find a solution. branching factor.
TUTORIAL
TUTORIAL