数据结构与算法（Python 语言版）
裘宗燕，2014-9-24-/1/
1，引言
问题求解
数据结构
算法
算法分析
Python 程序的代价分析
数据抽象：概念和作用
与过程抽象的比较
定义类型（class 定义）
数据结构与算法（Python 语言版）
裘宗燕，2014-9-24-/2/
问题求解
使用计算机是为了解决实际问题。牵涉到：
能用计算机解决的问题的性质，特点
用计算机解决问题的途径和方法
解决一个实际问题，就要在计算机里建立该问题的求解模型：
处理实际问题中的各种对象及其相互关系
把这方面信息映射到计算机可以处理的表示形式
用 Python 解决问题，就是映射到 Python 能处理的某种结构
把实际问题的求解过程映射到一个计算过程，用程序实现该过程
例如，用 Python 语言写出解决问题的程序
程序设计/软件开发就是要实现这两个映射
但，应该怎么做？
数据结构与算法（Python 语言版）
裘宗燕，2014-9-24-/3/
问题求解
为解决一个实际问题而开发程序的工作通常可分成下面四个阶段
未必能按顺序一次完成，经常需要反复
回忆上学期课程中画的描述这个过程的图示
1. 分析阶段：弄清需要求解的问题，给出尽可能严格的描述
2. 设计阶段：设计出与实际问题对应的求解方案，进而设计出有关实现
的细节方案（信息到数据表示的映射，规划求解过程等）
这部分工作与本课程关系最密切
3. 编码阶段：用某种计算机可以执行的形式，实现第 2 阶段的设计
与本课程有关，例如用 Python 编程
4. 测试和维护：确认得到的程序能解决问题，以及为满足某些实际目标
或需要而修改程序，扩充功能等
下面通过一个例子展示这一过程
数据结构与算法（Python 语言版）
裘宗燕，2014-9-24-/4/
问题求解示例
假设现在需要为一个多叉路口设计一
个信号灯管理系统
具体路口的交通要求情况见图
图中箭头表示单行方向
不同行驶路线间可能出现冲突
存在现实的安全问题，慎重！
需要对行驶方向分组，使：
同属一组的各方向行驶的车辆，
同时行驶可以保证安全
分组应该尽可能大一些
提高路口的效率（经济问题）
不是很简单的问题，需要深入分析
C
D
B
E
A
一个交叉路口的模型
这个图已经是实际问题的抽象
与正确分配保证安全行车无关的
信息已经被抽象掉
集中关注重点是抽象的核心考虑
数据结构与算法（Python 语言版）
裘宗燕，2014-9-24-/5/
问题分析
问题较复杂，要采用某种严格的描述方式，
以便能把问题看得更清楚
所有可能通行方向（设计一种形式表示）
A→B A→C A→D B→A B→C
B→D D→A D→B D→C E→A
E→B E→C E→D
下面用 AB 表示 A→B，其他类似
C
D
B
E
A
一个交叉路口的模型
考虑如何基于这种抽象表示，进一步看清问题的实质
行驶方向的分组，关键情况：
有些方向相互冲突，同时开放会相互阻碍，而且有撞车危险
为了安全，不应该为任意两个冲突的行驶方向同时开绿灯，因此它
们不能放入同一个分组
数据结构与算法（Python 语言版）
裘宗燕，2014-9-24-/6/
问题分析
表示冲突的方式是在冲突方向之间划一条连线
通过认真分析，得到下面的冲突图
C
D
B
E
A
一个交叉路口的模型
AB
AC AD
BA BC BD
DA D B DC
EA EB
EC ED
数据结构与算法（Python 语言版）
裘宗燕，2014-9-24-/7/
问题分析
问题求解线索：把冲突图中的结点分组
保证有边相连的结点不同组
同组行驶方向互不冲突，可同时通行
问题：哪些结点可同组，共分为多少个组？
显然解：每个方向独立作为一个组
进一步目标：分组最少（同时通行方向多，提高路口利用率）
地图着色问题（一个“等价”求解问题）：
把图中结点看作国家，结点间连线看作两国边界
结点问题就变成了著名的“地图着色问题”：求出可将图中所有国家
着色，并使相邻国的颜色不同的最少颜色数
由具体问题得到的图（可能）不是平面图（不能画在一个平面上使
连线都不相交），因此需要的颜色数可能多于4
AB AC AD
BA BC BD
DA D B DC
EA EB
EC ED
数据结构与算法（Python 语言版）
裘宗燕，2014-9-24-/8/
算法设计
通过分析构造出问题的求解模型后，下步考虑求解算法（的设计）
算法设计研究求解问题的严格方法
设计好的算法为编程实现提供了坚实的基础
解决本问题（图着色问题）有许多方法
不同方法有不同的性质，需要考虑
方法1，通过穷举选出最优
设法逐个枚举出所有可能的合法分组，在枚举过程中，记录遇到的最
小分组个数和对应的分组情况
这一过程一定能找到一个“最优”解（分组数最少的解）
缺点：可能组合数太多，逐个枚举需要指数时间（算法的效率低）
如果不同方向的集合比较大，求解时间可能长得无法忍受
交通路口的支路不多（超过4的情况不多见），可以考虑这一算法
数据结构与算法（Python 语言版）
裘宗燕，2014-9-24-/9/
算法设计
方法2. “贪心法”
这是一类典型的算法设计思路（算法的设计模式），基本想法是根据
当时掌握的信息，尽可能地向得到解的方向推进
通常不能找到最优解，但能找到“可接受的”解
算法梗概（伪代码）:
设法表示图 G # 记录图中的结点连接关系
集合 verts 保存 G 中所有结点 # 建立初始状态
设置集合 groups = 空集 # 记录得到的分组，元素是集合
while 存在未着色结点 : # 用贪心法反复找新分组
选一种新颜色
在未着色结点中给尽量多无互连边的点着色（构建一个分组）
记录新着色的结点组
# 算法结束时集合 groups 里记录着一种分组方式
# 算法细节还需要进一步考虑
数据结构与算法（Python 语言版）
裘宗燕，2014-9-24-/10/
算法设计
采用贪心法，按结点排列顺序试探（演示）：
AB AC AD
BA BC BD
DA D B DC
EA EB
EC ED
