算法合集之数据关系的简化.ppt

数据关系的简化,长沙雅礼中学 何林,常用的数据关系：线性序列，树，图,坐船问题 雅礼中学有n个学生去公园划船。一条船最多可以坐两个人。如果某两个学生同姓或者同名就可以坐在一条船上。学校希望每个同学都坐上船，同时学校想要租用最少的船。请问：学校至少要租多少船？,伍昱伍平何林何刚黄刚何凡,伍昱,伍平,黄刚,何刚,何林,何凡,伍昱,伍平,黄刚,何刚,何林,何凡,最优解,OR,图-树,一个包含n个点的无向图同名或者同姓的人之间连一条边,图模型,最小边覆盖,任意图最大匹配！,伍昱伍平何林何刚黄刚何凡,伍昱,伍平,黄刚,何刚,何林,何凡,树结构,一片森林每个节点和左孩子同姓每个节点和右孩子同名,树的构造,首先假设所有人是一个连通图,黄刚,树的构造,首先假设所有人是一个连通图,雷锋,雷涛,黄涛,欧阳锋,黄嘎,张嘎,雷震子,黄药师,周涛,黄刚,张药师,没有左儿子了,树的构造,首先假设所有人是一个连通图,雷锋,雷涛,黄涛,欧阳锋,黄嘎,张嘎,雷震子,黄药师,周涛,黄刚,张药师,树的构造,首先假设所有人是一个连通图,黄刚,欧阳涛,树的构造,首先假设所有人是一个连通图,黄刚,雷锋,雷涛,黄涛,欧阳锋,黄嘎,张嘎,雷震子,黄药师,周涛,张药师,欧阳涛,没有右儿子,树的构造,首先假设所有人是一个连通图,黄刚,雷锋,雷涛,黄涛,欧阳锋,黄嘎,张嘎,雷震子,黄药师,周涛,张药师,欧阳涛,树的匹配,黄刚,雷锋,雷涛,黄涛,欧阳锋,黄嘎,张嘎,雷震子,黄药师,周涛,张药师,欧阳涛,分析叶子节点,独子！,树的匹配,黄刚,雷锋,雷涛,黄涛,欧阳锋,黄嘎,张嘎,雷震子,黄药师,周涛,张药师,欧阳涛,独子的情况,他们坐一条船,剩下的树依然是连通的,树的匹配,黄刚,雷锋,雷涛,黄涛,欧阳锋,黄嘎,张嘎,雷震子,黄药师,张药师,分析叶子节点,落单！树不连通！,不是独子,树的匹配,黄刚,雷锋,雷涛,黄涛,欧阳锋,黄嘎,张嘎,雷震子,黄药师,张药师,分析叶子节点,树的匹配,非独子的情况,每次让两个人坐上一条船树始终保持连通假设树中有n个点，(n+1)/2条船即可容纳所有人。这无疑是最优解。,树的匹配,设森林中有m棵树，所有树的规模是n1,n2,nm。对每棵树分别处理。答案是(i=1.m)(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 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,树-线性,线性,逆序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,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,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 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遍历,红+蓝+黄=全部+后代,红：DFS序列中节点v后比他小的数的个数蓝：逆DFS序列中节点v后比他小的数的个数黄：v的直系祖先中比v小的节点个数全部：v-1,树-线性,红+蓝+黄=全部+后代,红：DFS序列中节点v后比他小的数的个数蓝：逆DFS序列中节点v后比他小的数的个数黄：v的直系祖先中比v小的节点个数全部：v-1,红：DFS序列中节点v后比他小的数的个数,问题：已知一个序列(DFS序列)，求每个数后面有多少个数比他小。,解答：用线段树即时更新。时间复杂度O(nlogn)。,树简化成线性结构后带来的“序”关系,树-线性,红+蓝+黄=全部+后代,红：DFS序列中节点v后比他小的数的个数蓝：逆DFS序列中节点v后比他小的数的个数黄：v的直系祖先中比v小的节点个数全部：v-1,蓝：逆DFS序列中节点v后比他小的数的个数,问题：已知一个序列(逆DFS序列)，求每个数后面有多少个数比他小。,解答：用线段树即时更新。时间复杂度O(nlogn)。,树简化成线性结构后带来的“序”关系,树-线性,红+蓝+黄=全部+后代,红：DFS序列中节点v后比他小的数的个数蓝：逆DFS序列中节点v后比他小的数的个数黄：v的直系祖先中比v小的节点个数全部：v-1,黄：v的直系祖先中比v小的节点个数,树-线性,红+蓝+黄=全部+后代,黄：v的直系祖先中比v小的节点个数,7,树-线性,红+蓝+黄=全部+后代,黄：v的直系祖先中比v小的节点个数,7,10,1,9,3,4,11,6,8,5,15,2,14,13,7 10,7,树-线性,红+蓝+黄=全部+后代,黄：v的直系祖先中比v小的节点个数,7,10,1,9,3,4,11,6,8,5,15,2,14,13,7 10 14,7 10,7,树-线性,红+蓝+黄=全部+后代,黄：v的直系祖先中比v小的节点个数,7,10,1,9,3,4,11,6,8,5,15,2,14,13,7 10 14 2,7 10 14,7 10,7,树-线性,红+蓝+黄=全部+后代,黄：v的直系祖先中比v小的节点个数,7,10,1,9,3,4,11,6,8,5,15,2,14,13,7 10 14 13,7 10 14 2,7 10 14,7 10,7,树-线性,红+蓝+黄=全部+后代,黄：v的直系祖先中比v小的节点个数,7,10,1,9,3,4,11,6,8,5,15,2,14,13,7 10 14 13,7 10 14 2,7 10 14,7 10,7,7 1,树-线性,红+蓝+黄=全部+后代,黄：v的直系祖先中比v小的节点个数,7,10,1,9,3,4,11,6,8,5,15,2,14,13,7 10 14 13,7 10 14 2,7 10 14,7 10,7,7 1,7 9,树-线性,红+蓝+黄=全部+后代,黄：v的直系祖先中比v小的节点个数,7,10,1,9,3,4,11,6,8,5,15,2,14,13,7 10 14 13,7 10 14 2,7 10 14,7 10,7,7 1,7 9,7 9 11,树-线性,红+蓝+黄=全部+后代,黄：v的直系祖先中比v小的节点个数,7,10,1,9,3,4,11,6,8,5,15,2,14,13,7 10 14 13,7 10 14 2,7 10 14,7 10,7,7 1,7 9,7 9 11,7 9 6,树-线性,红+蓝+黄=全部+后代,黄：v的直系祖先中比v小的节点个数,7,10,1,9,3,4,11,6,8,5,15,2,14,13,7 10 14 13,7 10 14 2,7 10 14,7 10,7,7 1,7 9,7 9 11,7 9 6,7 9 6 5,树-线性,红+蓝+黄=全部+后代,黄：v的直系祖先中比v小的节点个数,7,10,1,9,3,4,11,6,8,5,15,2,14,13,7 10 14 13,7 10 14 2,7 10 14,7 10,7,7 1,7 9,7 9 11,7 9 6,7 9 6 5,13的直系祖先,5的直系祖先,深度优先搜索中要用到一个栈来存储节点（比如递归）。任意时刻，栈顶元素的直系祖先就是栈中其余的节点。用一棵线段树来维护这个栈。求每个节点的直系祖先中有多少个比他本身小就能用O(nlogn)的时间复杂度实现。,树-线性,红+蓝+黄=全部+后代,红：DFS序列中节点v后比他小的数的个数蓝：逆DFS序列中节点v后比他小的数的个数黄：v的直系祖先中比v小的节点个数全部：v-1,综合上面的分析，红、蓝、黄我们都能在O(nlogn)的时间复杂度内求出。所以整个问题解决，时间复杂度是O(nlogn)。,树-线性 小结,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的直系祖先,红+蓝+黄=全部+后代,图树，树序列。有时候不需要包罗万象的所有信息合理的组织数据之间的关系利用简化数据关系实现数据的有序化简化后的关系更明了，有利于窥见本质矛盾。,数据关系的简化,谢谢！,