文件名称：算法设计-数据库第一章ppt
文件大小：1.64MB
文件格式：PPT
更新时间：2024-05-15 15:15:41
数据库
算法设计： 穷举法：逐一检查所有可能组合，记录最小分组数和对应分组 贪心法：一类典型算法，其宗旨是根据当时掌握的信息，尽 可能地向得到解的方向推进 例3 多叉路口交通灯管理问题 C E D A B AB AC AD BA BC BD DA DB DC EA EB EC ED 图 找出V1中可用新颜色着色的结点集的程序框架： NEW={}; for(每个v∈V1)do if(v与NEW中所有结点间都没有边){ 从V1中去掉v; 把v加入NEW; } 结束时NEW中是可以用一种新颜色着色的结点。 上述算法的实现要基于集合和图的操作。 所需的集合和图操作: 判断一个集合是否为空：isSetEmpty(V1); 置一个集合为空：emptySet(NEW); 从集合中去掉一个元素：removeFromSet(V1,v); 向集合里增加一个元素：addToSet(NEW,v); 检查结点v与结点集NEW中各结点间在图G中是否有 边连接：notAdjacentWithSet(NEW,v,G); 有了图、集合和其上的操作，程序实现就不难了 初始时： 集合V包含图G中的所有结点 集合T={}，准备存放分组 重复做： while(存在未着色结点，即V不空) { 选择一种新颜色； 在未着色结点中给尽量多的无边互连的点着色； }