《数据结构与算法实习概论》由会员分享，可在线阅读，更多相关《数据结构与算法实习概论（70页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法实习 概论,北京大学信息科学技术学院 第一讲代课：闫宏飞 主讲：张 铭 mzhang at 2014.9 张铭 赵海燕 王腾蛟 宋国杰，数据结构与算法实验教程（国家十一五规划教材），高教社2011年1月,农夫需要把狼、羊、菜和自己运到河对岸去，只有农夫能够划船，而且船比较小，除农夫之外每次只能运一种东西，还有一个棘手问题，就是如果没有农夫看着，羊会偷吃菜，狼会吃羊。请考虑一种方法，让农夫能够安全地安排这些东西和他自己过河。,例子,（人羊） 羊,（人狼菜） 菜,（人羊狼） 狼,（人羊菜） 羊,（人羊狼菜） 狼菜,人,人羊,人狼,人羊,人菜,（人狼菜） 狼菜,（人羊） 空,人,人羊,
2、（人狼菜） 人羊狼菜,算法数据结构,问题（problem）： 从输入到输出的一种映射函数 数据结构（Data Structure）：逻辑数据结构在计算机中的存储表达，支持相应的操作 算法（algorithm）：对特定问题求解过程的描述方法 程序（program） ： 算法在计算机程序设计语言中的实现, 程序,课程目标,配合“数据结构与算法”主课 补充高级数据结构知识 提高实际动手能力和程序设计的质量,数据结构的定义,数据的逻辑结构 图树二叉树线性表 数据的存储结构 顺序、链接 索引、散列 数据的运算 增、删、查、改 排序、检索,北京大学信息学院 版权所有，转载或翻印必究 Page 7,数据结构
3、与算法实习,数据结构与算法,算法分析与设计,计算概论,图形图像 队列、栈、图、矩阵、空间索引树、检索,数据库概论 线性表、多链表、排序及B+索引树,编译原理 字符串、栈、散列表及语法树,操作系统 队列、存储管理表、排序及目录树,人工智能 广义表、集合、搜索树及各种有向图,Web信息处理 队列、图、字符、矩阵散列、排序、索引、检索,概率统计,程序设计实习,集合论与图论,进度安排（可调顺序）,成绩评定办法,平时：10% 开卷随堂测试、课堂表现、团队合作 POJ作业：20% 北大ACM结果、源程序、实习报告 POJ机考：30% 综合上机题：20% 源程序、实习报告 期末闭卷考试 ： 20%,设计和实
4、现,问题求解 数学建模（问题建模） 数据结构抽象 算法抽象 效率分析 编程设想 选择能在合理时间内解决预期规模问题的简单算法和数据结构 在一些互相冲突的需求和约束条件之间寻找平衡 反复试验，推倒重来，直至,算法分类,穷举法万能，低效 避免穷举测试 回溯、搜索跳过无解分支 最优化问题的通法 递归分治自顶向下，问题化解 子结构不重复 分、治、合 动态规划自底向上，利用中间结果，迅速构造 最优子结构、重复子结构、无后效性 搜索中分支定界的特例 空间换时间 贪心法动态规划的特例 最优子结构最优解 否则，只是快速得到较优解,八皇后问题,在88格的国际象棋棋盘上摆放8个皇后，使其不能互相攻击 任意两个皇后
5、都不处于同一行、同一列或同一斜线上 问有多少种摆法？,八皇后问题的一个解,穷举法（枚举法）,4个皇后各占一行，穷举每一行上可能占有的列 共有44 256种情况 枚举时，可以排除直观不符合条件的情况，减小候选集 有4! 24种情况 最后输出合理的解,穷举法的代价,穷举问题域的所有解，找到所有最佳解 减少穷举次数 穷举的变量 注意穷举的顺序 减少判断每种情况的时间 时间代价最高 问题规模n，搜索空间，总搜索时间是： T= | t，O(n!) = O(nn)，O(2n) 指数级时间代价,四皇后问题及其解空间树,解表示成一个4维向量，（放置列号） 搜索空间：4叉树（排列树）,搜索过程(1),从结点1到
6、结点2，满足条件，放置皇后x1=1,继续向前,Q,搜索过程(2),结点3不满足条件，回溯到结点2； 再向下搜索到结点8；满足条件，放置皇后x2=3,继续向前,1,X1=1,2,3,4,5,6,7,4,3,X2=2,8,9,10,2,4,11,12,4,2,3,X3=3,X4=4,Q,X,Q,搜索过程(3),结点9不满足条件，回溯到结点8， 向下搜索到结点11，不满足条件，这时经结点8，回溯到结点2,1,X1=1,2,3,4,5,6,7,4,3,X2=2,8,9,10,2,4,11,12,4,2,3,X3=3,X4=4,Q,Q,X,X,搜索过程(4),向下搜索到结点13，满足条件，放置第二个皇后
7、x2=4; 继续向下搜索到结点14满足条件，放置第三个皇后x3=2;,1,X1=1,2,3,4,5,6,7,4,3,X2=2,8,9,10,2,4,11,12,4,2,3,13,14,15,2,3,16,17,3,2,4,X3=3,X4=4,Q,Q,Q,搜索过程(5),向下搜索到结点15，不满足条件，回溯到结点13；,1,X1=1,2,3,4,5,6,7,4,3,X2=2,8,9,10,2,4,11,12,4,2,3,13,14,15,2,3,16,17,3,2,4,X3=3,X4=4,Q,Q,Q,X,搜索过程(6),向下搜索到结点16，不满足条件，回溯到结点1；,1,X1=1,2,3,4,5
8、,6,7,4,3,X2=2,8,9,10,2,4,11,12,4,2,3,13,14,15,2,3,16,17,3,2,4,X3=3,X4=4,Q,Q,X,搜索过程(7),回溯到结点1后，向下搜索到结点18，满足条件，放置第一个皇后x1=2,1,X1=1,2,3,4,5,6,7,4,3,X2=2,8,9,10,2,4,11,12,4,2,3,13,14,15,2,3,16,17,3,2,4,2,18,X3=3,X4=4,Q,搜索过程(8),向下搜索到结点19，不满足条件，回溯到结点18； 向下搜索到结点24，不满足条件，回溯到结点18； 向下搜索到结点29，满足条件，放置第2个皇后x2=4；,
9、1,X1=1,2,3,4,5,6,7,4,3,X2=2,8,9,10,2,4,11,12,4,2,3,13,14,15,2,3,16,17,3,2,4,2,18,19,20,21,3,4,22,23,4,3,1,24,25,26,1,4,27,28,4,1,3,29,30,31,1,3,32,33,3,1,4,X3=3,X4=4,Q,X,X,Q,搜索过程(9),向下搜索到结点30，满足条件，放置第3个皇后x3=1； 向下搜索到结点31，满足条件，放置第4个皇后x4=3；此时，i=4, 找到有效 解,1,X1=1,2,3,4,5,6,7,4,3,X2=2,8,9,10,2,4,11,12,4,2
10、,3,13,14,15,2,3,16,17,3,2,4,2,18,19,20,21,3,4,22,23,4,3,1,24,25,26,1,4,27,28,4,1,3,29,30,31,1,3,32,33,3,1,4,X3=3,X4=4,Q,Q,Q,Q,四皇后的解空间树,1,X1=1,2,3,4,5,6,7,4,3,X2=2,2,18,29,30,31,1,3,32,33,3,1,4,X3=3,X4=4,状态空间,解空间树,根（root）：问题的起点 问题状态（problem states）：树中结点 状态空间（state space）：由根结点到其它结点的所有路径 解状态（solution s
11、tates）S：由根到S的路径确定了解空间中的一个元组 答案状态（answer states）S：由根到S的路径确定了这问题的一个解（即，它满足隐式约束条件）,回溯法图示,“可行则进，不行则换、换不成则退”。 简化为4皇后问题。搜索过程如下：,四后问题求解,回溯算法,可行则进，不行则换 换不成则退,八皇后问题的表示,棋盘行列、皇后依次编上0, 1,，7号 A0n-10n-1 表示nn棋盘上的格 行号从上至下、列号从左到右依次编号为0, 1,，n-1 八后问题的全部解向量为(x0, x1,，x7)。 xi表示皇后i所处的列数 对任何0i, j8，及ij，有xixj 状态空间缩小为8! 没有两个皇
12、后在同一斜线上（斜率为1 ） 重点！,斜率+1，i+j=0, 1, , 14,0 1 2 3 4 5 6 7,0 1 2 3 4 5 6 7,斜率-1，i-j=-7, 6, , 7,0 1 2 3 4 5 6 7,0 1 2 3 4 5 6 7,皇后的控制范围,第i个皇后时，前面几个皇后在各列、各对角线上的占用情况 bool An; / 前0i-1行皇后占用列 bool B2*n-1; / 斜率为+1的对角线 bool C2*n-1; / 斜率为-1， Ci-j+7,试探安排八个皇后,从第0行开始，逐步安排每行皇后。 对第i个皇后，找正确的位置(设为第j列 Aj、Bi+j、Ci-j+7都没有被
13、占用 标记Aj、Bi+j、Ci-j+7为被占用状态 继续安排下一个皇后(第i+1个) 否则，如果找不到合适位置，应该退回(即“回溯”)到第i-1行的皇后，重新安排 前面的安排不太合理,回溯过程,如果8个皇后都排好了，则打印这种方案 为了找到其它方案，应该回溯，重新试探皇后的下一种安排方法 抹掉前面试探留下的标记，即恢复Aj、Bi+j、Ci-j+7为未被占用状态 这种回溯过程将逐步返回 使得各行的皇后都能试探到各种可能的摆法,回溯法的框架,问题的解n元组(x0, x1,，xn-1)： void rectry(k) / 初始调rectry(0); 置Xk为第一个可能值； while (Xk可能值没
14、有试完) 设置Xk所涉及的标记; if (X0, X1，Xn-1)是解) 打印一组解; else rectry(k+1); 回溯，抹去Xk涉及的标记； 取下一个可能的Xk值; ,八皇后的递归算法,void queen(int i) int j; for (j=0; jn; j+) if (place(i,j) / 能放置吗 Xi = j; mark(i,j); / 标记（i,j）的影响 if (i n-1) queen(i+1); / 接着试下一个 else print(count); / 打印一个解 erase(i,j); / 回溯，去掉刚才标记 ,四皇后时，函数执行模拟,失败情况下回溯过程
15、模拟： queen(0) 试探x0=0, mark(0,0) queen(1) / for (j=0; jn;j+) 试探x1=2, mark(1,2) queen(2) / 摆不了，函数返回 erase(1,2) / 回溯 试探x1=3, mark(1,3) ,皇后函数执行模拟(续),四皇后成功情况下，回溯，继续求解： X = 1, 3, 0, 2为第一个解，求其他解 erase(3, 2) 试探下一个j=3, 当然不能摆 erase(2, 0), 试探其他，都失/queen(2) erase(1, 3), 试探其他，都失败/queen(1) erase(0, 1) / queen(0) x0 = 2, mark(0,2) queen(1) x1=0, mark(1, 0) .得到第二个解X=2, 0, 3, 1,八皇后算法讨论,如果
