例3多叉路口交通灯管理问题 把图12中的结点进行分组,使得有结点相连的结点不 在同一个组里。 ●地图着色问题 如果把上图中的一个结点理解为一个国家,结点之间 的连线看作两国有共同边界,上述问题就变成著名的 “着色问题”:即求出最少要几种颜色可将图中所有 国家着色,使得任意两个相邻的国家颜色都不相同。 ●通过上面的分析,我们就获得了该交通管系统的数学 模型。下面就可以着手进行算法的设计。 北京邮电大学自动化学院 16
北京邮电大学自动化学院 16 ⚫ 把图1.2中的结点进行分组，使得有结点相连的结点不 在同一个组里。 ⚫ 地图着色问题 ⚫ 如果把上图中的一个结点理解为一个国家， 结点之间 的连线看作两国有共同边界，上述问题 就变成著名的 “着色问题”：即求出最少要几种颜色可将图中所有 国家着色，使得任意两个相邻的国家颜色都不相同。 ⚫ 通过上面的分析，我们就获得了该交通管系统的数学 模型。下面就可以着手进行算法的设计。 例3多叉路口交通灯管理问题
例3多叉路口交通灯管理问题 1.对n个结点,逐个测试其所有组合; ●2.“贪心法” ● while有结点未着色; {选择一种新颜色; 在未着色的结点中给尽可能多的彼此结点之间没有边 点着色; 北京邮电大学自动化学院
北京邮电大学自动化学院 17 算法设计 ⚫ 2. “贪心法” ⚫ while 有结点未着色； ⚫ { 选择一种新颜色； ⚫ 在未着色的结点中,给尽可能多的彼此结点之间没有边 点着色； ⚫ } ⚫ 1. 对n个结点，逐个测试其所有组合； 例3多叉路口交通灯管理问题
着色结果 B AC D BA C BD DA DB DC EC ED EA EB EB EC 图12交叉路口的图示模型 北京邮电大学自动化学院
北京邮电大学自动化学院 18 AB AC AD BA BC BD DA D B DC EA EB EC ED 图1.2 交叉路口的图示模型 图 AB AC AD BA BC BD DA DB DC EA EB EC ED C E D A B 着色结果
例3多叉路口交通灯管理问题 ●把上面方法应用于图12,得到下面的分组: 绿色:AB,AC,AD,BA,Dc,ED 蓝色:BC,BD,EA 红色:DA,DB ●白色:EB,EC 北京邮电大学自动化学院 19
北京邮电大学自动化学院 19 ⚫ 把上面方法应用于图1.2，得到下面的分组： ⚫ 绿色：AB, AC, AD, BA, DC, ED ⚫ 蓝色：BC, BD, EA ⚫ 红色：DA, DB ⚫ 白色：EB, EC 例3多叉路口交通灯管理问题
第一章绪论 ●综上三个例子,描述这类非数值计算问题的数学模型 不再是数学方程,而是诸如表、树和图之类的数据结 构。 ●因此,简单说来,数据结构是一门研究非数值计算的 程序设计问题中计算机的操作对象以及它们之间的关 系和操作等等的学科。 数据结构就是研究数据的逻辑结构和物理结构它们之 间相互关系,并对这种结构定义相应的运算,而且确 保经过这些运算后所得到的新结构仍然是原来的结构 类型。 北京邮电大学自动化学院
北京邮电大学自动化学院 20 ⚫ 综上三个例子，描述这类非数值计算问题的数学模型 不再是数学方程，而是诸如表、树和图之类的数据结 构。 ⚫ 因此，简单说来，数据结构是一门研究非数值计算的 程序设计问题中计算机的操作对象以及它们之间的关 系和操作等等的学科。 ⚫ 数据结构就是研究数据的逻辑结构和物理结构它们之 间相互关系，并对这种结构定义相应的运算，而且确 保经过这些运算后所得到的新结构仍然是原来的结构 类型。 第一章 绪 论