算法合集之《数据关系的简化》.ppt
《算法合集之《数据关系的简化》.ppt》由会员分享,可在线阅读,更多相关《算法合集之《数据关系的简化》.ppt(47页珍藏版)》请在三一文库上搜索。
1、数据关系的简化,长沙雅礼中学 何林,常用的数据关系:线性序列,树,图,坐船问题 雅礼中学有n个学生去公园划船。一条船最多可以坐两个人。如果某两个学生同姓或者同名就可以坐在一条船上。 学校希望每个同学都坐上船,同时学校想要租用最少的船。请问:学校至少要租多少船?,伍昱 伍平 何林 何刚 黄刚 何凡,伍昱,伍平,黄刚,何刚,何林,何凡,伍昱,伍平,黄刚,何刚,何林,何凡,最优解,OR,图树,一个包含n个点的无向图 同名或者同姓的人之间连一条边,图模型,最小边覆盖,任意图最大匹配!,伍昱 伍平 何林 何刚 黄刚 何凡,伍昱,伍平,黄刚,何刚,何林,何凡,树结构,一片森林 每个节点和左孩子同姓 每个节
2、点和右孩子同名,树的构造,首先假设所有人是一个连通图,黄刚,树的构造,首先假设所有人是一个连通图,雷锋,雷涛,黄涛,欧阳锋,黄嘎,张嘎,雷震子,黄药师,周涛,黄刚,张药师,没有左儿子了,树的构造,首先假设所有人是一个连通图,雷锋,雷涛,黄涛,欧阳锋,黄嘎,张嘎,雷震子,黄药师,周涛,黄刚,张药师,树的构造,首先假设所有人是一个连通图,黄刚,欧阳涛,树的构造,首先假设所有人是一个连通图,黄刚,雷锋,雷涛,黄涛,欧阳锋,黄嘎,张嘎,雷震子,黄药师,周涛,张药师,欧阳涛,没有右儿子,树的构造,首先假设所有人是一个连通图,黄刚,雷锋,雷涛,黄涛,欧阳锋,黄嘎,张嘎,雷震子,黄药师,周涛,张药师,欧阳涛
3、,树的匹配,黄刚,雷锋,雷涛,黄涛,欧阳锋,黄嘎,张嘎,雷震子,黄药师,周涛,张药师,欧阳涛,分析叶子节点,独子!,树的匹配,黄刚,雷锋,雷涛,黄涛,欧阳锋,黄嘎,张嘎,雷震子,黄药师,周涛,张药师,欧阳涛,独子的情况,他们坐一条船,剩下的树依然是连通的,树的匹配,黄刚,雷锋,雷涛,黄涛,欧阳锋,黄嘎,张嘎,雷震子,黄药师,张药师,分析叶子节点,落单! 树不连通!,不是独子,树的匹配,黄刚,雷锋,雷涛,黄涛,欧阳锋,黄嘎,张嘎,雷震子,黄药师,张药师,分析叶子节点,树的匹配,非独子的情况,每次让两个人坐上一条船 树始终保持连通 假设树中有n个点,(n+1)/2条船即可容纳所有人。 这无疑是最优
4、解。,树的匹配,设森林中有m棵树,所有树的规模是n1, n2, , nm。 对每棵树分别处理。 答案是(i=1m)(ni+1)/2,森林的匹配,图树小结,任意图最大匹配!,简单贪心,O(n2)或O(n3)的时间复杂度 编程复杂度很高,O(n) 的时间复杂度 编程复杂度很低,树的统计 一棵树含有n个节点。 节点编号为1, 2, 3, , n。 定义t(v)为v的后代中所有编号小于v的节点个数。 求t(1), t(2), t(3), , t(n)。,树线性,树线性,7,10,1,9,3,4,11,6,8,5,15,12,2,14,13,t(9)=3,t(10)=1,t 1 2 3 4 5 6 7
5、8 9 10 11 12 13 14 15 0 0 0 0 0 1 6 0 3 1 0 0 0 2 0,对每个点,逐个检查其后代。 时间复杂度O(n2)。 当n=30000就不可承受。,树线性,后代,如何把这个“先后”顺序表现出来呢,树线性,线性,一个序列中元素之间的先后关系十分明显,7,10,14,2,13,1,9,11,6,5,8,3,15,12,4,树线性,7,10,1,9,3,4,11,6,8,5,15,12,2,14,13,线性,一个序列中元素之间的先后关系十分明显,7,10,14,2,13,1,9,11,6,5,8,3,15,12,4,对应,后代,多出来的部分,9,树线性,线性,逆
6、序DFS遍历,7,10,14,2,13,1,9,11,6,5,8,3,15,12,4,树线性,7,10,1,9,3,4,11,6,8,5,15,12,2,14,13,线性,对应,后代,多出来的部分,9,7,10,14,2,13,1,9,11,6,5,8,3,15,12,4,树线性,7,10,1,9,3,4,11,6,8,5,15,12,2,14,13,7 10 14 2 13 1 9 11 6 5 8 3 15 12 4,7 4 3 12 15 9 6 8 5 11 1 10 14 13 2,DFS遍历,逆DFS遍历,树线性,7,10,1,9,3,4,11,6,8,5,15,12,2,14,1
7、3,7 10 14 2 13 1 9 11 6 5 8 3 15 12 4,7 4 3 12 15 9 6 8 5 11 1 10 14 13 2,DFS遍历,逆DFS遍历,后代!,重叠容斥原理,树线性,7,10,1,9,3,4,11,6,8,5,15,12,2,14,13,7 10 14 2 13 1 9 11 6 5 8 3 15 12 4,7 4 3 12 15 9 6 8 5 11 1 10 14 13 2,DFS遍历,逆DFS遍历,9的直系祖先,红+蓝+黄=全部+后代,树线性,7,10,1,9,3,4,11,6,8,5,15,12,2,14,13,7 10 14 2 13 1 9 1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据关系的简化 算法 数据 关系 简化
链接地址:https://www.31doc.com/p-3488305.html