数据结构与算法(Python语言描述)课件DS1-intro

数据结构与算法（Python语言版）：引言裘宗燕，2014-9-24-/1/多叉路口设计一个信号灯管理系统不同行驶路线间可能出现冲突存在现实的安全问题，慎重！需要对行驶方向分组，使：同属一组的各方向行驶的车辆，同时行驶可以保证安全分组应该尽可能大一些提高路口的效率（经济问题）CDBEA一个交叉路口的模型数据结构与算法（Python语言版）：引言裘宗燕，2014-9-24-/2/问题分析所有可能通行方向（设计一种形式表示）ABACADBABCBDDADBDCEAEBECEDCDBEA一个交叉路口的模型行驶方向的分组，关键情况：有些方向相互冲突，同时开放会相互阻碍，而且有撞车危险为了安全，不应该为任意两个冲突的行驶方向同时开绿灯，因此它们不能放入同一个分组数据结构与算法（Python语言版）：引言裘宗燕，2014-9-24-/3/问题分析表示冲突的方式是在冲突方向之间划一条连线CDBEA一个交叉路口的模型ABACADBABCBDDADBDCEAEBECED数据结构与算法（Python语言版）：引言裘宗燕，2014-9-24-/4/问题分析问题求解线索：把冲突图中的结点分组保证有边相连的结点不同组同组行驶方向互不冲突，可同时通行问题：哪些结点可同组，共分为多少个组？显然解：每个方向独立作为一个组进一步目标：分组最少（同时通行方向多，提高路口利用率）ABACADBABCBDDADBDCEAEBECED数据结构与算法（Python语言版）：引言裘宗燕，2014-9-24-/5/问题分析地图着色问题（一个“等价”求解问题）：把图中结点看作国家，结点间连线看作两国边界结点问题就变成了著名的“地图着色问题”：求出可将图中所有国家着色，并使相邻国的颜色不同的最少颜色数由具体问题得到的图（可能）不是平面图（不能画在一个平面上使连线都不相交），因此需要的颜色数可能多于4ABACADBABCBDDADBDCEAEBECED数据结构与算法（Python语言版）：引言裘宗燕，2014-9-24-/6/算法设计方法1，通过穷举选出最优设法逐个枚举出所有可能的合法分组，在枚举过程中，记录遇到的最小分组个数和对应分组情况通过这一过程一定能找到一个“最优”解（分组数最少的解）缺点：可能组合情况太多，逐个枚举需要指数时间（效率低）如果不同方向的集合比较大，求解时间可能长得无法忍受交通路口的支路不多（超过4的情况不多见），可以考虑这一算法数据结构与算法（Python语言版）：引言裘宗燕，2014-9-24-/7/算法设计方法2.“贪心法”这是一类典型的算法设计思路（算法的设计模式），基本想法是根据当时掌握的信息，尽可能地向得到解的方向推进通常不能找到最优解，但能找到“可接受的”解数据结构与算法（Python语言版）：引言裘宗燕，2014-9-24-/8/算法设计算法梗概（伪代码）:算法输入：图G#记录图中的结点连接关系集合verts保存G中所有结点#建立初始状态设置集合groups=空集#记录得到的分组，元素是集合while存在未着色结点:#用贪心法反复找新分组选一种新颜色在未着色结点中给尽量多无互连边的点着色（构建一个分组）记录新着色的结点组#算法结束时集合groups里记录着一种分组方式#算法细节还需要进一步考虑数据结构与算法（Python语言版）：引言裘宗燕，2014-9-24-/9/算法设计采用贪心法，按结点排列顺序试探（演示）：ABACADBABCBDDADBDCEAEBECED数据结构与算法（Python语言版）：引言裘宗燕，2014-9-24-/10/算法设计贪心法应用于图1.2，得到的分组：绿色：AB,AC,AD,BA,DC,ED蓝色：BC,BD,EA红色：DA,DB白色：EB,ECCDBEA一个交叉路口的模型ABACADBABCBDDADBDCEAEBECED数据结构与算法（Python语言版）：引言裘宗燕，2014-9-24-/11/分析实际的可能分组不唯一，下面是另一满足要求的分组ABACADBABCBDDADBDCEAEBECEDCDBEA一个交叉路口的模型数据结构与算法（Python语言版）：引言裘宗燕，2014-9-24-/12/分析CDBEA一个交叉路口的模型ABACADBABCBDDADBDCEAEBECED得到分组：1：AB,AC,AD,BA,DC,ED2：BC,BD,EA3：DA,DB4：EB,EC解决了原来要解决的问题吗？数据结构与算法（Python语言版）：引言裘宗燕，2014-9-24-/13/分析如果希望提供最大行驶可能，问题就不是安全划分，而是基于安全划分的分组最大化。可从划分扩充得到第一种分组的扩充：1：AB,AC,AD,BA,DC,ED2：BC,BD,EA,BA,DC,ED3：DA,DB,BA,DC,ED,AD4：EB,EC,BA,DC,ED,EA后两组扩充时可在AD和EA任选CDBEA一个交叉路口的模型