数据结构与算法Python语言描述教学课件 DS1-intro.ppt

《数据结构与算法Python语言描述教学课件 DS1-intro.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1，引言问题求解数据结构算法算法分析Python程序的代价分析数据抽象：概念和作用与过程抽象的比较定义类型（class定义）问题求解使用计算机是为了解决实际问题。牵涉到：能用计算机解决的问题的性质和特点用计算机解决问题的途径和方法解决一个实际问题，首先要在计算机里建立该问题的求解模型：处理实际问题中的各种对象及其相互关系把这些信息映射到计算机可以处理的表示形式用Python解决问题，就是映射到Python能处理的某种结构把实际问题的求解过程映射到一个计算过程，用程序实现该过程例如，用Python语言写出解决问题的程序程序设计/软件开发

2、就是要实现这两个映射但，应该怎么做？问题求解为解决一个实际问题而开发程序的工作通常可分成下面四个阶段未必能按顺序一次完成，经常出现反复，参看下图：问题调试运行程序检查代码编程问题的严格描述分析，形式化调试运行中发现程序有逻辑错误检查或调试运行中发现代码有语法或类型等方面的错误完成的程序问题的严格描述：specification代码：code，貌似程序但可能有语法等错误逻辑错误：logicerror，即，程序不符合预期，不能完成所希望的工作调试运行中发现问题分析有误问题求解用计算机解决问题的过程和阶段：分析阶段：弄清需要求解的问题，给出

3、尽可能严格详尽的描述设计阶段：设计出与实际问题对应的求解方案，进而设计出有关实现的细节方案（信息到数据表示的映射，规划求解过程等）这部分工作与本课程关系最密切编码阶段：用某种计算机可以执行的形式，实现第2阶段的设计与本课程有关，例如用Python编程需要考虑语言的特点，各种可以利用的语言特征测试和维护：确认得到的程序能解决问题，以及为满足某些实际目标或需要而修改程序，扩充功能等下面通过一个例子展示这一过程问题求解示例假设现在需要为一个多叉路口设计一个信号灯管理系统具体路口的交通要求情况见图图中箭头表示单行方向不同行驶路线间可能出现冲突

4、存在现实的安全问题，慎重！需要对行驶方向分组，使：同属一组的各方向行驶的车辆，同时行驶可以保证安全分组应该尽可能大一些提高路口的效率（经济问题）不是很简单的问题，需要深入分析这个图已经是实际问题的抽象与正确分配保证安全行车无关的信息已经被抽象掉集中关注重点是抽象的核心考虑问题分析问题较复杂，要采用某种严格的描述方式，以便能把问题看得更清楚所有可能通行方向（设计一种形式表示）ABACADBABCBDDADBDCEAEBECED下面用AB表示AB，其他类似考虑如何基于这种抽象表示，进一步看清问题的实质行驶方向的

5、分组，关键情况：有些方向相互冲突，同时开放会相互阻碍，而且有撞车危险为了安全，不应该为任意两个冲突的行驶方向同时开绿灯，因此它们不能放入同一个分组问题分析表示冲突的方式是在冲突方向之间划一条连线通过认真分析，得到下面的冲突图ABACADBABCBDDADBDCEAEBECED问题分析问题求解线索：把冲突图中的结点分组保证有边相连的结点不同组同组行驶方向互不冲突，可同时通行问题：哪些结点可同组，共分为多少个组？显然解：每个方向独立作为一个组进一步目标：分组最少（同时通行方向多，提高路口利用率）地图着色问题（一个“等价”求解问题）：把图中

6、结点看作国家，结点间连线看作两国边界结点问题就变成了著名的“地图着色问题”：求出可将图中所有国家着色，并使相邻国的颜色不同的最少颜色数由具体问题得到的图（可能）不是平面图（不能画在一个平面上使连线都不相交），因此需要的颜色数可能多于4ABACADBABCBDDADBDCEAEBECED算法设计通过分析构造出问题的求解模型后，下步考虑求解算法（的设计）算法设计研究求解问题的严格方法设计好的算法为编程实现提供了坚实的基础解决本问题（图着色问题）有许多方法不同方法有不同的性质，需要考虑方法1，通过穷举选出最优设法逐个枚举出所有可能的合法分组

7、，在枚举过程中，记录遇到的最小分组个数和对应分组情况通过这一过程一定能找到一个“最优”解（分组数最少的解）缺点：可能组合情况太多，逐个枚举需要指数时间（效率低）如果不同方向的集合比较大，求解时间可能长得无法忍受交通路口的支路不多（超过4的情况不多见），可以考虑这一算法算法设计方法2.“贪心法”这是一类典型的算法设计思路（算法的设计模式），基本想法是根据当时掌握的信息，尽可能地向得到解的方向推进通常不能找到最优解，但能找到“可接受的”解算法梗概（伪代码）:算法输入：图G#记录图中的结点连接关系集合verts保存G中所有结点#建立初始状态

8、设置集合groups=空集#记录得到的分组，元素是集合while存在未着色结点:#用贪心法反复找新分组选一种新颜色在未着色结点中给尽量多无互连边的点着色（构建一个分组）记录新着色的结点组#算法结束时集合groups里记录