代价一致搜索(Uniform Cost Search)
代价一致搜索
2 Strategy: expand a cheapest node first: Fringe is a priority queue (priority: cumulative cost) S 1
p b
a
G
1
d
8
9
q
c
3
2
h
e
G
b d c a p q
Search Tree
S
e e h r
p q
S
q
r
We construct both on demand – and we construct as little as possible.
a
h
q c a
r
f G
p
q
q
c a
f
G
Quiz: 状态空间图 vs. 搜索树
Consider this 4-state graph:
搜索
中国科学院自动化研究所 吴高巍 gaowei.wu@ 2016-9-13
内容
搜索问题
无信息搜索 Uninformed Search 启发式搜索 Informed Search 局部搜索 Local Search
搜索问题
搜索问题
搜索问题 构成:
状态空间 A state space 后继函数 A successor function (with actions, costs)
b
…
c1 c2 c3
内存需求?
Has roughly the last tier, so O(bC*/ɛ)
完备性?
Assuming best solution has a finite cost and minimum arc cost is positive, yes!
最优性?
状态空间图 State Space Graphs 搜索树 Search Trees
状态空间图
状态空间图: 搜索问题的数学表示
Nodes are (abstracted) world configurations Arcs represent successors (action results) The goal test is a set of goal nodes (maybe only one)
Quiz: 安全通行
Problem: eat all dots while keeping the ghosts perma-scared What does the state space have to specify?
(agent position, dot booleans, power pellet booleans, remaining scared time)
状态空间图中，每个状态只出现一次！ 几乎不在内存中构建完整的状态空间图（太 大了），但它是非常有用的
状态空间图
状态空间图: 搜索问题的数学表示
Nodes are (abstracted) world configurations Arcs represent successors (action results) The goal test is a set of goal nodes (maybe only one)
状态空间中状态数量?
世界状态:
Agent positions: 120 Food count: 30 Ghost positions: 12 Agent facing: NSEW
数量
世界状态? 120x(230)x(122)x4 路线规划状态? 120 “吃光豆子”状态? 120x(230)
DFS扩展哪些节点?
Some left prefix of the tree. Could process the whole tree! If m is finite, takes time O(bm)
… m tiers b 1 node b nodes b2 nodes
内存需求?
广度优先搜索(Breadth-First Search)
广度优先搜索
Strategy: expand a shallowest node first a b d
S
G
c
e f r
Implementation: Fringe is a FIFO queue
h
p
q
S
d Search
e
p r q
Tiers
Problem: Eat-All-Dots
States: {(x,y), dot booleans} Actions: NSEW Successor: update location and possibly a dot boolean Goal test: dots all false
a b d c e G
f
h
状态空间图中，每个状态只出现一次！ 几乎不在内存中构建完整的状态空间图（太 大了），但它是非常有用的
S
p
q
r
Tiny search graph for a tiny search problem
搜索树
This is now / start
“N”, 1.0 “E”, 1.0
Quiz: DFS vs BFS
Quiz: DFS vs BFS
什么情况下BFS优于DFS?
什么情况下DFS优于BFS?
迭代深入搜索(Iterative Deepening)
Idea: 结合DFS的空间优势与BFS的时间优势
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. …..
Only has siblings on path to root, so O(bm)
完备性?
m could be infinite, so only if we prevent cycles (more later)
bm nodes
最优性?
No, it finds the “leftmost” solution, regardless of depth or cost
Yes!
代价一致搜索
UCS 探索了递增的轮廓线
… c1 c2 c3
优点: 完备性、最优性!
缺点:
在每一个“方向”上进行探索 没有关于目标信息
Start Goal
搜索算法
所有的搜索算法都是相同的，除 了对边缘的处理策略
从概念上说，所有的边缘是优先队列 (即附加优先级的节点集合) 对于DFS, BFS，可以通过使用栈或队 列代替优先队列，从而减少log(n) 的 开支
… m tiers
b
1 node b nodes b2 nodes
例子:
b 分支因子 m 最大深度 d 最浅目标节点的深度
整个树的节点数目?
1 + b + b2 + …. bm = O(bm)
bm nodes
例子: 树搜索
a b d c
G
e
f h q r
S
p
深度优先搜索(Depth-First Search)
… b
浪费冗余?
通常绝大多数的节点都在底层，所以上层的节 点生成多次影响不是很大。
代价敏感搜索(Cost-Sensitive Search)
2 b 1 8 2 e 8 h 4 r f 2 2 d 9
START
a
GOAL
2 c 3 2
3
1 p
4 15
q
BFS finds the shortest path in terms of number of actions. It does not find the least-cost path. We will now cover a similar algorithm which does find the least-cost path.
初始状态:
Arad
目标测试:
Is state == Bucharest?
解?
状态空间包含什么?
状态空间 包含了环境中的每一个细节
搜索状态 只保留行动需要的细节
Problem: Pathing
States: (x,y) location Actions: NSEW Successor: update location only Goal test: is (x,y)=END
a
How big is its search tree (from S)?
S
G
b
Important: Lots of repeated structure in the search tree!
树搜索
例子: 罗马尼亚旅行
基于搜索树的搜索
搜索:
扩展出潜在的行动 (tree nodes) 维护所考虑行动的边缘(fringe)节点 试图扩展尽可能少的树节点
b
a
c
a p q h q
e r f c a
G
h p q q c a
f
G
广度优先搜索(BFS) 特性
BFS扩展哪些节点?
Processes all nodes above shallowest solution Let depth of shallowest solution be s s tiers Search takes time O(bs)