9512.net
甜梦文库
当前位置:首页 >> 学科竞赛 >>

2014信息学奥林匹克夏令营-day6搜索算法的应用(张信)



搜索算法的应用
JSOI 2014 夏令营 (A)
Suzhou High School of Jiangsu Province, Sean Chang

课程内容
? 搜索算法回顾 ? 实例分析 ? 总结

Suzhou High School of Jiangsu Province, Sean Chang



搜索算法是什么?
? 搜索算法是利用计算机的高性能来有目的

的穷举一个问题的部分或所有的可能情况, 从而求出问题的解的一种方法 和人工智能中占有重要地位

? 搜索算法被称为“通用解题法”,在算法
? 许多算法其实是搜索算法的拓展(如动态

规划、图论中的一些算法等)

Suzhou High School of Jiangsu Province, Sean Chang

搜索算法的几个关键概念
? 状态

– 对一个问题在某一时刻进展情况的数学表示
– 问题从一个状态到另一个(或多个)状态的操 作

? 状态转移

? 状态空间

– 由状态作为顶点,状态转移作为边而形成的一 个隐式图
Suzhou High School of Jiangsu Province, Sean Chang

搜索算法的几个关键概念
? 搜索过程就是对状态空间遍历的过程 ? 搜索的一个可行解就是从起始状态到目标

状态集中任意状态的一条路径 我们称之为搜索树

? 对状态空间遍历的结果往往呈现为树型,

Suzhou High School of Jiangsu Province, Sean Chang

搜索算法的分类
?

盲目搜索

– 深度优先搜索(DFS) – 广度优先搜索(BFS) – 纯随机搜索 – 重复式搜索(迭代+DFS,柱形搜索等)

?

启发式搜索:一种有准备、为追求效率而有的 放矢的智能搜索
– 贪心搜索 – A*、IDA*

Suzhou High School of Jiangsu Province, Sean Chang

深度优先搜索(DFS)
算法模型 ? 数据结构
? ? ?

难点

算法框架 时空效率

– 非递归形式的实现 – 剪枝

– 递归形式 – 非递归形式 – 时间复杂度 – 空间复杂度
Suzhou High School of Jiangsu Province, Sean Chang

?

广度优先搜索(BFS)
? 算法模型 ? 数据结构 ? 算法框架 ? 时空效率 ? 难点

– 状态空间大小的估算 – 状态的判重 – 解路径的保存与输出

– 时间复杂度 – 空间复杂度
Suzhou High School of Jiangsu Province, Sean Chang

搜索算法的特点
? 基于穷举,算法时间复杂度高 ? 具有代码框架,程序实现较为容易 ? 适用性好,可以解决很多问题

Suzhou High School of Jiangsu Province, Sean Chang

搜索算法需要掌握的要点
? 对任意一个问题能很快的分析出状态和状

态转移过程,建立状态空间

? 能选择一个合理的搜索策略 ? 能估计问题的时空性能,并尽可能对其进

行优化

Suzhou High School of Jiangsu Province, Sean Chang

搜索算法在NOIP比赛时的作用
? 单纯的搜索题(主要考察优化) ? 搜索算法与其他算法相结合的题目 ? 使用搜索算法进行验证 ? 使用搜索算法解决小规模数据

Suzhou High School of Jiangsu Province, Sean Chang

课程内容
? 搜索算法回顾 ? 实例分析 ? 总结

Suzhou High School of Jiangsu Province, Sean Chang

状态和状态表示
? 野人和传教士过河问题

– 有3个传教士和3个野人要过河,河上有一条船, 传教士和野人都会划船,但船上只有两个座位。 任何时刻,河岸的任何一边,野人数量都不能 比传教士多,否则传教士会遭遇不测。 – 如何安全的让所有传教士和野人都过河呢?

Suzhou High School of Jiangsu Province, Sean Chang

传教士与野人问题
? 请给出状态的表示方法,并给出初始状态

和目标状态

? 请给出所有状态转移的表示方法,并举例

实现状态直接的转换

Suzhou High School of Jiangsu Province, Sean Chang

棋盘游戏
? 在一个4*4的棋盘上有8个黑棋和8个白棋,

当且仅当两个格子有公共边时,这两个格 子上的棋是相邻的。棋子的移动规则是交 换相邻的两个棋子。现给出一个初始棋盘 和一个最终棋盘,请你使用最少的移动操 作,使棋盘从初始状态变为最终状态。

Suzhou High School of Jiangsu Province, Sean Chang

棋盘游戏
? ? ? ?

1111 0000 1110 0010

?

4

? ?

1010 0101 1010 0101
Suzhou High School of Jiangsu Province, Sean Chang

? ?

棋盘游戏
? 请给出状态的表示方法 ? 请给出所有状态转移的表示方法

Suzhou High School of Jiangsu Province, Sean Chang

剪枝
? 分类
? ?

– 可行性剪枝

– 最优性剪枝(上下界剪枝)

根据判断继续搜索是否能到达目标状态来进行剪枝 根据判断当前状态是否能够达到比已知的最优情况更 优的状态来进行剪枝

Suzhou High School of Jiangsu Province, Sean Chang

剪枝
? 请结合刚才野人过河的问题,给出剪枝条



– 可行性剪枝 – 最优性剪枝

Suzhou High School of Jiangsu Province, Sean Chang

剪枝
? 剪枝原则

– 正确性
?
? ?

– 准确性

保证不丢失正确的结果
判断合理,使不包含解的分支尽可能多的被剪掉 剪枝不是越多越好,要平衡剪枝的力度和代价,尽量 不用力度小但代价大的剪枝策略
Suzhou High School of Jiangsu Province, Sean Chang

– 高效性

迷宫问题
? 迷宫问题大家都很熟悉了,那么在迷宫问

题中,方向选择的不同会对问题求解带来 什么影响呢?

Suzhou High School of Jiangsu Province, Sean Chang

改变搜索的顺序的一些方法
? 静态优化搜索顺序 ? 纯随机搜索顺序 ? 动态调整搜索顺序

– 贪心 – 启发式搜索

Suzhou High School of Jiangsu Province, Sean Chang

选择搜索顺序的一些建议
? 先搜索取值范围较小的元素 ? 先搜索对其他搜索元素取值范围影响较大

的元素

? 先搜索对解影响较大的元素

Suzhou High School of Jiangsu Province, Sean Chang

质数方阵
?

在一个5*5的方阵中填入数字,使得这些数字 满足如下条件:

– 每一行的5个数字(从左往右)构成一个5位质数 – 每一列的5个数字(从上往下)构成一个5位质数 – 两条对角线上的5个数字(从左往右)构成两个5 位质数 – 所有质数各位数字之和为 N,且第一位不为零 – 方阵左上角的数字为 K
?

请根据给点的N和K,求出所有符合条件的方阵
Suzhou High School of Jiangsu Province, Sean Chang

质数方阵
? 输入
? 输出

– 11 1
– 11351 – 14033 – 30323 – 53201 – 13313

(有多组,此处仅输出一组)

Suzhou High School of Jiangsu Province, Sean Chang

质数方阵
? 首先确定取值范围最小的最后一行和最后

一列

? 然后确定影响最大的两条对角线 ? 然后呢? ? 还可以采取哪些方法来减少搜索量?

– 预处理

Suzhou High School of Jiangsu Province, Sean Chang

跳马遍历问题
? 在一个n*n的国际象棋棋盘上有一个“马”,

根据国际象棋中马的行进规则,请你不重 复的走完棋盘上所有的格子。

Suzhou High School of Jiangsu Province, Sean Chang

坦克大战
? 在一个N*M(2<=N,M<=300)的地图上,

有钢墙、有河流、有平地、有砖墙,当然 还有一台坦克,有钢墙和河流的地方坦克 不能通过,平地可以通过且需花费一个单 位时间,砖墙不可通过,但可以将其摧毁, 摧毁砖墙时坦克不能移动其需消耗一个单 位时间。请问坦克从起点走到终点至少需 要多少单位时间?

Suzhou High School of Jiangsu Province, Sean Chang

坦克大战
? 如何搜索?

– DFS
?
?

求最优解可能会TLE

– BFS

适合求最优解 ? 如何处理砖墙呢?

Suzhou High School of Jiangsu Province, Sean Chang

优先队列
? 普通队列的一种变形 ? 队列中的每个元素都有优先级,出队时,

并不是简单的将队首元素出队,而是将最 高优先级的元素出队

? 操作系统中CPU调度就是一个优先队列

Suzhou High School of Jiangsu Province, Sean Chang

优先队列
? 数据结构
?

– 有序的线性表或链表 –堆
?

入队的时间复杂度O(n) ? 出队的时间复杂度O(1)
入队和出队的时间复杂度都是O(log2n)

– C++的STL库中有有优先队列(大根堆)

Suzhou High School of Jiangsu Province, Sean Chang

坦克大战
? 如何使用优先队列处理坦克大战呢?

– 以到达每一个点的最少总时间作为权值 – 出队时优先选择权值小的元素先出队

Suzhou High School of Jiangsu Province, Sean Chang

八立方拼图游戏
? 在一个3*3的棋盘上有8个立方体,每个立

方体上都被喷涂上了三种颜色,你可以将 一个立方体滚动到相邻的空位上。 ? 初始状态下,所有立方体都是上下为白色, 左右为蓝色,前后为红色。 ? 现给你一个顶面的状态图,请你用最少的 移动次数将棋盘从初始状态移动到这个目 标状态。
Suzhou High School of Jiangsu Province, Sean Chang

八立方拼图游戏
?2 ?R ?R ?E

1 BW WW WW

?3

Suzhou High School of Jiangsu Province, Sean Chang

八立方拼图
? 状态空间有多少 ? 怎么搜索

– 单向广度优先搜索 – 双向广度优先搜索

? 在搜索过程中如何处理状态重复的情况呢?

Suzhou High School of Jiangsu Province, Sean Chang

状态的判重
? 除非状态空间图本身就是无环的,或者拥

有很强的结点扩展方式来避免产生重复, 广度优先搜索都是需要对状态进行判重的。

Suzhou High School of Jiangsu Province, Sean Chang

状态判重
? 常用的判重方法
? ? ? ?

– 直接利用队列进行判重 – 利用二分进行判重 – 能有添加和查找的期望值都能达到 O(1) 的判 重方式吗?
Suzhou High School of Jiangsu Province, Sean Chang

添加的复杂度 查找的复杂度 添加的复杂度 查找的复杂度

散列表(哈希表)
? 散列表是根据关键字直接访问在内存存储

位置的数据结构。它通过一个函数的计算, 将关键字映射到表中的一个位置,这加快 了查找的速度

? 这个映射函数称为散列函数
? 存放记录的数组称为散列表

? 所得的存储地址称为散列地址
Suzhou High School of Jiangsu Province, Sean Chang

散列表
A

x1 x2

x4
x5

B C

x3

D E

Suzhou High School of Jiangsu Province, Sean Chang

散列函数的构造方法(数字)
? 直接定址法

– 直接去关键字或关键字的某个线性函数值作为 散列地址 – 比如,统计个年龄段的人口数量时,可以年龄 作为关键字,取自身为散列函数 – 又如,我们把一个多维数组转变为一维时,以 下标为关键字,取线性函数为散列函数

Suzhou High School of Jiangsu Province, Sean Chang

散列函数的构造方法(数字)
? 数字分析法

– 取关键字的若干数位组成散列地址(可能出现 的关键字已知) – 比如以身份证号码作为关键字时,可以选择其 中部分直接作为散列地址 – 取那几位呢?
?

取差异最大的那几位

Suzhou High School of Jiangsu Province, Sean Chang

散列函数的构造方法(数字)
? 平方取中法

– 取关键字平方后的中间几位为散列地址 – 一个数平方后的中间几位数字和原数字的每一 位都相关,由此期望随机分布的关键字得到的 散列地址也是随机的 – 将关键字分割为位数相等的几部分,然后将这 几部分的叠加和(舍去进位)作为散列地址
Suzhou High School of Jiangsu Province, Sean Chang

? 折叠法

散列函数的构造方法(数字)
? 随机数法 ? 除留余数法

– 取关键字被某个不大于散列表表长的数p除后的 余数为散列地址,即hash(x) = x mod p – 可以对关键字直接取模,也可在折叠法、平方 取中法等运算之后取模 – p的选取非常重要,一般取素数或表长
Suzhou High School of Jiangsu Province, Sean Chang

散列函数(字符串)
? 字符串的判重,特别是比较长的字符串的

判重也是非常耗时的

? 字符串的散列函数有很多,如ELFHash,

APHash,BKDRHash等

Suzhou High School of Jiangsu Province, Sean Chang

ELFHash
function ElfHash(s: string): longint; var i, num, g: longint; begin num := 0; for i := 1 to length(s) do begin num := (num shl 4) + ord(s[i]); g := num and $F0000000; if g <> 0 then num := num xor (g shr 24); num := num and (not g); end; ElfHash := num and &7FFFFFFF; end;
Suzhou High School of Jiangsu Province, Sean Chang

BKDRHash
const seed = 131; function BKDRHash(s: string): longint; var i, num: longint; begin num := 0; for i := 1 to length(s) do num := (num * seed + ord(s[i])) and $FFFFFFF; BKDRHash := num and $7FFFFFFF; end;
Suzhou High School of Jiangsu Province, Sean Chang

碰撞
? 若不同的关键字可能得到用一个散列地址,

即当 x1 <> x2 时,f(x1) = f(x2),这种 现象称为碰撞。

Suzhou High School of Jiangsu Province, Sean Chang

均匀散列函数
? 若对于关键字集合中的任一个关键字,经

散列函数映象到地址集合中任何一个地址 的概率是相等的,则称此类散列函数为均 匀散列函数,这就是使关键字经过散列函 数得到一个“随机的地址”,从而减少碰 撞。

Suzhou High School of Jiangsu Province, Sean Chang

碰撞的处理
? 开放地址法

– hashi=(hash(key) + di) mod m – 探测方式
?

线性探测:di取 1,2,3,…… ? 平方探测:di取 12,-12,22,-22,32,-32,…… ? 伪随机探测:di 取伪随机数

Suzhou High School of Jiangsu Province, Sean Chang

碰撞的处理
? 拉链法

– 拉出一个动态链表替代静态顺序存储结构 – 可以避免散列函数的冲突,但增加了编程的复 杂度 – 设计两种或者多种散列函数 – 可以在很大程度上避免冲突

? 多散列法

? 建立公共溢出区
Suzhou High School of Jiangsu Province, Sean Chang

散列表的性能
? 散列表的性能很大程度上取决于碰撞产生

的多少。碰撞越多,性能就越差。完全没 有碰撞的散列表性能最好。一般以平均查 找长度来衡量。 ? 影响碰撞数量的因素主要包括

– 散列函数是否均匀 – 处理碰撞的方法 – 散列表的装载因子(表中元素的个数 / 表长)
Suzhou High School of Jiangsu Province, Sean Chang

散列表的用途
? 统计 ? 查找

Suzhou High School of Jiangsu Province, Sean Chang

散列的相关代码
? 除留余数+线性探测

function Hash(K, i: longint): longint begin Hash := (K mod m + i) mod m; end;

Suzhou High School of Jiangsu Province, Sean Chang

散列的相关代码
function HashSearch(T: HashTable; K: longint; var pos: longint): integer; var i: longint; begin for i := 0 to m - 1 do begin pos := Hash(K,i); if(T[pos] = K) then exit(1); if(T[pos] = 0) then exit(0); end; exit(-1); end;

Suzhou High School of Jiangsu Province, Sean Chang

散列的相关代码
procedure HashInsert(T: HashTable, v: longint); var pos: longint; sign: integer; begin sign := HashSearch(T, v, pos); if (sign = 0) then T[pos] := v else if (sign = 1) then writeln('duplicate!'); else writeln('overflow!'); end;

Suzhou High School of Jiangsu Province, Sean Chang

八立方拼图
? 怎么设计一个散列函数来判重呢?

– 你需要估算出大概的状态空间数量 – 选择除留余数法,选取一个比最大状态数量稍 大些的素数 – 选择一个碰撞处理的方法

Suzhou High School of Jiangsu Province, Sean Chang

搭建积木
? 将N(N

<= 25000)块单位立方体积木 按指令进行搭建(第一块积木放在地面 上),如果搭建过程中出现一个位置放置 多块积木或有积木被放置到地面之下的情 况,则说明非法。 是可见的。

? 如果没有非法情况出现,输出有多少个面

Suzhou High School of Jiangsu Province, Sean Chang

搭建积木
? 如何来判断是否出现同一个位置出现两块

积木的情况?

Suzhou High School of Jiangsu Province, Sean Chang

课程内容
? 搜索算法回顾 ? 实例分析 ? 总结

Suzhou High School of Jiangsu Province, Sean Chang



更多相关文章:
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图