CS计算机代考程序代写 AI algorithm PowerPoint Presentation

PowerPoint Presentation

CSE 3521: Search
[Many slides are adapted from the UC Berkeley. CS188 Intro to AI at UC Berkeley and previous CSE 3521 course at OSU.]

Today
State Space Graphs and Search Trees

Uninformed Search Methods

Depth-First Search

Breadth-First Search

Uniform-Cost Search

General theme in the class:

A goal we have in mind.

A mathematical abstraction to formalize this

Algorithms that operate on these abstractions
2

State space graphs and search trees

To “systematically” find the solution rather than brute-force

State space graphs
State space graph: a mathematical representation of a search problem
Nodes are states (i.e., abstracted world configurations)
Arcs represent successors (action and results)
The goal test is a set of goal nodes (maybe only one)

In a state space graph, each unique state occurs only once!

We can rarely build this full graph in memory (it’s too big), but it’s a useful idea

State space graphs
State space graph: a mathematical representation of a search problem
Nodes are states (i.e., abstracted world configurations)
Arcs represent successors (action and results)
The goal test is a set of goal nodes (maybe only one)

In a state space graph, each unique state occurs only once!

We can rarely build this full graph in memory (it’s too big), but it’s a useful idea

S
G
d
b
p
q
c
e
h
a
f
r
Tiny state space graph graph for a tiny search problem

Uninformed vs. informed search
Uninformed search
Given no information about the problem (other than its definition)
Find solutions by systematically visiting new states and testing for goal

Informed search
Given some ideas of where to look for solutions
Use problem-specific knowledge

Uninformed vs. informed search
Uninformed search
Given no information about the problem (other than its definition)
Find solutions by systematically visiting new states and testing for goal

Informed search
Given some ideas of where to look for solutions
Use problem-specific knowledge

Search trees (moves in state space graphs)
A search tree:
A “what if” tree of plans and their outcomes
The start state is the root node
Children correspond to successors
Nodes show states, but correspond to/record PLANS that achieve those states
For most problems, we can never actually build the whole tree

“E”, 1.0
“N”, 1.0

This is now / start

Possible futures

Different plans that achieve the same state, will be different nodes in the tree.
8

Search trees: nodes are not states but partial plans
G
b
a
c

a
b
c
a
G
(a-b)
(a-b-c)
(a-b-c-a)
(a-b-c-G)
Can we have “a” again? Or should it go back the root (then not a tree anymore)?
Yes! The node is actually (a-b-c-a), different from (a).
(a)
Different plans that achieve the same state, will be different nodes in the tree!
State space graph
Search tree

Different plans that achieve the same state, will be different nodes in the tree.
9

State space graphs vs. search trees

S
a
b
d
p
a
c
e
p
h
f
r
q
q
c
G
a
q
e
p
h
f
r
q
q
c
G
a
S
G
d
b
p
q
c
e
h
a
f
r
Each NODE in in the search tree is an entire PATH in the state space graph.
Search Tree
State Space Graph

State space graphs vs. search trees

S
a
b
d
p
a
c
e
p
h
f
r
q
q
c
G
a
q
e
p
h
f
r
q
q
c
G
a
S
G
d
b
p
q
c
e
h
a
f
r
Each NODE in in the search tree is an entire PATH in the state space graph.
Search Tree
State Space Graph
A unique STATE can show up at multiple NODES in a search tree; each NODE in the search tree is a unique plan.

State space graphs vs. search trees

S
a
b
d
p
a
c
e
p
h
f
r
q
q
c
G
a
q
e
p
h
f
r
q
q
c
G
a
S
G
d
b
p
q
c
e
h
a
f
r
We construct both on demand – and we construct as little as possible.
Each NODE in in the search tree is an entire PATH in the state space graph.
Search Tree
State Space Graph
A unique STATE can show up at multiple NODES in a search tree; each NODE in the search tree is a unique plan.

Exercise: State space graphs vs. search trees
S
G
b
a
Consider this 4-state graph:
How big/deep is its search tree (from S)?

Exercise: State space graphs vs. search trees
S
G
b
a
Consider this 4-state graph:
Important: Lots of repeated structure in the search tree!
How big/deep is its search tree (from S)?

Tree search

How to systematically build/explore a search tree to find the solution!

Search example: Romania

Searching with a search tree
Search:
Expand out potential plans (tree nodes)
Maintain a fringe of partial plans under consideration
Try to expand as few tree nodes as possible

Searching with a search tree
Search:
Expand out potential plans (tree nodes)
Maintain a fringe of partial plans under consideration
Try to expand as few tree nodes as possible

Searching with a search tree
Search:
Expand out potential plans (tree nodes)
Maintain a fringe of partial plans under consideration
Try to expand as few tree nodes as possible
When to stop?

General tree search

Search problem

General tree search
Important components:
(1) Fringe (2) Expansion (3) Exploration strategy

Main question: which fringe nodes to explore?

Search problem (state space, successor function, start state, and goal test)

Tree Search
Search:
Expand out potential plans (tree nodes)
Maintain a fringe of partial plans under consideration
Try to expand as few tree nodes as possible

Tree Search
Search:
Expand out potential plans (tree nodes)
Maintain a fringe of partial plans under consideration
Try to expand as few tree nodes as possible

Tree Search
Search:
Expand out potential plans (tree nodes)
Maintain a fringe of partial plans under consideration
Try to expand as few tree nodes as possible
When to stop?

General Search
enqueue(queue, start_node)
loop do {
if empty(queue) return failure
leaf = getNext(queue)
if isGoal(leaf)
return solution(leaf)
else
enqueue(queue, expand(leaf))
}

Start State

Fail!

Goal Check

Successor Function

General Search: Textbook Pseudocode
Priority queue (assume a MIN priority queue)
DFS: LIFO
Priority = -1 * search tree depth
BFS: FIFO
Priority = search tree depth
UCS
Priority = Accumulated cost path

Depth-First Search (DFS)

Depth-First Search (DFS)
S
a
b
d
p
a
c
e
p
h
f
r
q
q
c
G
a
q
e
p
h
f
r
q
q
c
G
a

S
G
d
b
p
q
c
e
h
a
f
r

q
p
h
f

d
b
a
c
e
r

Strategy: expand a deepest node first
Implementation: Fringe is a LIFO stack

Search algorithm properties

Search algorithm properties
Complete: Guaranteed to find a solution if one exists?
Optimal: Guaranteed to find the least cost path?
Time complexity?
Space complexity (fringe)?

Cartoon of search tree:
b is the branching factor
m is the maximum depth
solutions at various depths

Number of nodes in entire tree?
1 + b + b2 + …. bm = O(bm)

b
1 node
b nodes
b2 nodes
bm nodes

m tiers

Depth-First Search (DFS) properties

b
1 node
b nodes
b2 nodes
bm nodes

m tiers
What nodes DFS expand?
Assume: Expand left first
Relax assumption: Could process the whole tree!
If m is finite, takes time O(bm)

How much space does the fringe take?
Only has siblings on the current path to root, so O(bm)

Is it complete?
m could be infinite, so only if we prevent cycles

Is it optimal?
Assume: Expand left first
No, it finds the “leftmost” solution, regardless of depth or cost

Breadth-First Search (BFS)

Breadth-First Search (BFS)
S
a
b
d
p
a
c
e
p
h
f
r
q
q
c
G
a
q
e
p
h
f
r
q
q
c
G
a
S
G
d
b
p
q
c
e
h
a
f
r

Search
Tiers

Strategy: expand a shallowest node first
Implementation: Fringe is a FIFO queue

Breadth-First Search (BFS) properties
What nodes does BFS expand?
Processes all nodes above the shallowest solution
Let the depth of the shallowest solution be s
Search takes time O(bs)

How much space does the fringe take?
Has roughly the last tier, so O(bs)

Is it complete?
s must be finite if a solution exists, so yes!

Is it optimal?
Only if costs are all unit cost (every action has the same cost)

b
1 node
b nodes
b2 nodes
bm nodes

s tiers
bs nodes

DFS vs. BFS
DFS BFS
Time to find a solution O(bm) O(bs)
Fringe space O(bm) O(bs)
Complete No Yes
Optimal No Yes, if unit costs

Time to find a solution IS NOT the cost of the solution (action sequence)

Example: The time to find a traveling plan between City A and City B IS NOT the time to travel from City A to City B

Iterative deepening

b

Idea: get DFS’s space advantage with BFS’s time/shallow-solution advantages
Run a DFS with depth limit 1. If no solution…
Run a DFS with depth limit 2. If no solution…
Run a DFS with depth limit 3. …..

Isn’t that wastefully redundant?
Generally, most of the work is in the deepest level searched, so not so bad!

A preferred method with a large search space and the depth of solution not known

Cost-sensitive search
BFS finds the shortest path (plan; solution) in terms of the number of actions.
It does not find the least-cost path.
We will now study a similar algorithm which does find the least-cost path.
START
GOAL
d
b
p
q
c
e
h
a
f
r
2
9
2
8
1
8
2
3
2

4
4
15
1
3
2
2

Uniform Cost Search (UCS)

Uniform Cost Search (UCS)

S
a
b
d
p
a
c
e
p
h
f
r
q
q
c
G
a
q
e
p
h
f
r
q
q
c
G
a

Strategy: expand the cheapest node first
Implementation: Fringe is a priority queue (priority: cumulative cost)
S
G
d
b
p
q
c
e
h
a
f
r
3
9
1

16

4
11
5

7
13

8

10
11

17
11

0
6
3
9
1
1
2
8
8
2
15
1
2

Cost contours
2


Uniform Cost Search (UCS) properties
What nodes does UCS expand?
Processes all nodes with cost less than the cheapest solution!
If the cheapest solution costs C* and the arcs cost at least  , then the “effective depth” is roughly C*/
Takes time O(bC*/) (exponential in effective depth)
Additional cost of the priority queue

How much space does the fringe take?
Has roughly the last tier, so O(bC*/)

Is it complete?
Assuming the least-cost solution has a finite cost and the minimum arc cost is positive, yes!

Is it optimal?
Yes!

b

C*/ “tiers”

c  3
c  2
c  1

The one queue
All the search algorithms are the same except for fringe/exploration strategies
Conceptually, all fringes are priority queues (i.e. collections of nodes with attached priorities)
Practically, for DFS and BFS, you can avoid the log(n) overhead from an actual priority queue, by using stacks and queues
Can even code one implementation that takes a variable queuing object

Search and models
Search operates over the models of the world
The agent doesn’t actually try all the plans out in the real world!
Planning is all “in simulation”
Your search is only as good as your models …

Search gone wrong?

Summary: Search algorithms

Search tree:
Nodes: represent plans for reaching states
Plans have costs (sum of action costs)

Search algorithm:
Systematically builds/explores a search tree
Chooses an ordering of the fringe (unexplored nodes)
Optimal: finds least-cost plans

Missionaries and Cannibals Problem
3 missionaries and 3 cannibals on one side of the river, with a single boat to cross
http://www.novelgames.com/en/spgames/missionaries/

Boat can hold 1 or 2 people

Can never have more cannibals than missionaries on a side

How do you get them over to the other side?
States? Initial State?
Transition Model?
Goal Test? Path Cost?
Search?

46

/docProps/thumbnail.jpeg