搜索与回溯.ppt

文档介绍：2018/5/6
1
根据“信息学初学者之家”网站的统计,Ural(俄罗斯的Ural州立大学的简称,有名的Ural Online Problem Set 就是该校的系统)的题目类型大概呈如下的分布:
搜索动态规划贪心构造图论
约10% 约15% 约5% 约5% 约10%
计算几何纯数学题数据结构其它约5% 约20% 约5% 约25%
统计信息:
2018/5/6
2
搜索与回溯
2018/5/6
3
什么是搜索算法呢?
搜索算法是利用计算机的高性能来有目的地穷举一个问题的部分或所有的可能情况,从而求出问题的解的一种方法。
其实质就是---枚举,但又与枚举有所不同
搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的节点的过程。
2018/5/6
4
搜索:一般是通过状态转移不断地寻找目标状态或最优状态。
状态:是对问题在某一时刻的进展情况的数学描述
状态扩展:是问题从一种状态转移到另一种状态的操作。
2018/5/6
5
举例:二分查找
2 3 4 5 6 8 12 20 32 45 65 74 86 95 100
head
mid
tail
2018/5/6
6
查找示意图:
A[1]~A[15]
A[1]~A[7]
A[9]~A[15]
A[1]~A[3]
A[5]~A[7]
A[1]~A[1]
A[3]~A[3]
……
2018/5/6
7
一、宽度优先遍历(BFS)
2018/5/6
8
基本算法
给定图G和一个源点s, 宽度优先遍历按照从近到远的顺序考虑各条边. 算法求出从s到各点的距离
宽度优先的过程对结点着色.
白色: 没有考虑过的点
黑色: 已经完全考虑过的点
灰色: 发现过, 但没有处理过, 是遍历边界
依次处理每个灰色结点u, 对于邻接边(u, v), 把v着成灰色并加入树中, 在树中u是v的父亲(parent)或称前驱(predecessor). 距离d[v] = d[u] + 1
用队列Q管理所有的灰色节点
整棵树的根为s
2018/5/6
9
2018/5/6
10