Transcript 323-670 ปัญญาประดิษฐ์ (Artificial Intelligence)

CS.462
Artificial Intelligence
SOMCHAI THANGSATHITYANGKUL
Lecture 02 : Search
Searching for Solutions
• The state space model provides a formal definition of a
problem and what constitutes a solution to a problem.
• State space is the set of all states reachable from the
initial state by any sequence of operators/actions.
• Operators -- generate new states from existing states
• A solution is
•
a state (called a goal state) whose attributes have
certain properties and maybe
•
a sequence of operators that will change the initial state
to a goal state
•
A solution is found by searching through the state space
until a (goal) state with “specific” properties is found
Artificial Intelligence
2
Chapter 1
What is a Solution in this type of Search?
• A solution to a search problem is a
sequence of operators that generate a
path from the initial state to a goal
state.
• An optimal solution is a minimal cost
solution.
• Solution cost versus search cost -which one to optimize?
Artificial Intelligence
3
Chapter 1
A directed graph in state space
4
Three coins problem
Given three coins arrange as in the
picture,
state I.
which is the initial
These are goal state G.
5
Three coins problem
Operation : Flipping the coin one at a time
Let A represent flipping the first coin
Let B represent flipping the middle coin
Let C represent flipping the last coin
• The search problem: find a path from a
state in I to a state in G.
• Draw the state space Graph
6
Three coins problem
State space graph
7
Three coins problem
Let put some rule into the problem
Rule : Use exactly 3 flips.
This means that 1flip cannot reach the goal
and
2 flips also cannot reach the goal.
For example: state I : HHTc HHH not goal
State I : HHT B HTT A TTT not goal
Let draw the state space
8
Three coins problem
State space tree
9
Search
• Many AI problems can be
formulated as search.
• Iterative deepening is good when
you don’t know much.
First Method of Search
• Uninformed Search
10
Depth First Search (DFS)
• Search
• Put start state in the agenda
• Loop
Get a state from the agenda
If goal, then return
Expand state (put children in agenda)
Avoiding loops
Don’t add a node to the agenda if it’s already in the
agenda
Don’t expand a node (or add it to the agenda) if it
has already been expanded.
11
DFS
Graph:
12
DFS
Agenda:
Expand node
s
Nodes list
{s}
{As ,Bs ,Cs }
– Expansion: put children at top of stack
– Get new nodes from top of stack
13
Try this
Find a path from node A to the goal nod
B. Use
O
S
F
DFS method.Z
A
R
P
T
D
M
L
14
C
B
Breadth First Search (BFS)
• Search
• Put start state in the agenda
• Loop
Get a state from the agenda
If goal, then return
Expand state (put children in agenda)
Avoiding loops
Don’t add a node to the agenda if it’s already
in the agenda
Don’t expand a node (or add it to the
agenda) if it has already
been expanded.
15
BFS
Graph:
16
BFS
Agenda:
Expand node
s
Nodes list
{s}
{As ,Bs ,Cs }
– Expansion: put children at end of queue
– Get new nodes from the front of queue
17
Try this
Find a path from node A to the goal nod
B. Use
O
S
F
BFS method. Z
A
R
P
T
D
M
L
18
C
B