《算法设计与分析》第06章

1、算法设计与分析DeSign and Analysis of AlgorithmsIn C+“十一五”国家级规划教材 陈慧南 编著电子工业出版社 南京邮电大学计算机学院 2008年3月第2部分 算法设计策略 南京邮电大学计算机学院 2008年3月第6章 贪心法 南京邮电大学计算机学院 2008年3月6.1 一般方法 6.2 背包问题 6.3 带时限的作业排序 6.4 最佳合并模式 6.5 最小代价生成树 6.6 单源最短路径 6.7 磁带最优存储 6.8 贪心法的基本要素 南京邮电大学计算机学院 2008年3月6.1 一般方法 南京邮电大学计算机学院 2008年3月最优化问题（optimizat

2、ion problems）是指这样一类问题，问题给定某些约束条件（constraint），满足这些约束条件的问题解称为可行解（feasible solution）。通常满足约束条件的解不是惟一的。为了衡量可行解的好坏，问题还给出了某个数值函数，称为目标函数（objective function），使目标函数取最大（或最小）值的可行解称为最优解（optimal solution）。 南京邮电大学计算机学院 2008年3月贪心法是通过分步决策（stepwise decision）的方法来求解问题的。贪心法每一步上用作决策依据的选择准则被称为最优量度标准（optimization criterion

3、）。在根据最优量度标准选择分量的过程中，还需要使用一个可行解判定函数。贪心策略并不是从整体上加以考虑的，它所做出的选择只是当前看似最佳选择，必须进一步证明该算法最终导致问题的一个整体最优解。 南京邮电大学计算机学院 2008年3月【程序61】贪心法SolutionType Greedy(SType a,int n) SolutionType solution=; for(int i=0;i0，pi0，0in。所谓背包问题是指求一种最佳装载方案，使得收益最大。所以，背包问题是现实世界一个常见的最优化问题。两类背包问题:如果每一件物品不能分割，只能作为整体或者装入背包，或者不装入，称为 0/1背包

4、问题；如果物品是可以分割的，也就是允许将其中的一部分装入背包为一般背包问题或简称背包问题。 南京邮电大学计算机学院 2008年3月6.2.2 贪心法求解 背包问题 背包问题的解可以表示成一个n-元组：X=(x0,x1,xn1)，0 xi1，0in，每个xi是第i件物品装入背包中的部分。 判定可行解的约束条件是： 南京邮电大学计算机学院 2008年3月 背包问题的最优解必须使下列目标函数取最大值： 南京邮电大学计算机学院 2008年3月例61 设有载重能力M=20的背包，3件物品的重量为:（w0,w1,w2）=(18,15,10)，物品装入背包的收益为：（p0,p1,p2）=(25,24,15)

5、。 南京邮电大学计算机学院 2008年3月 【程序62】背包问题的贪心算法 templateclass Knapsack public: Knapsack(int mSize,float cap,float *wei,T *prof); void GreedyKnapsack(float* x); private: float m,*w; T *p; int n; ; 南京邮电大学计算机学院 2008年3月templatevoid Knapsack:GreedyKnapsack(float* x) /前置条件：wi已按pi/wi的非增次序排列 float u=m; for (int i=0;i

6、n;i+) xi=0; for (i=0;iu) break; xi=1.0; u=u-wi; if (i0，di为整数。如果作业能够在截止期限之内完成，可获得pi0的收益。问题要求得到一种作业调度方案，该方案给出作业的一个子集和该作业子集的一种排列，使得若按照这种排列次序调度作业运行，该子集中的每个作业都能如期完成，并且能够获得最大收益。也就是说这种作业调度是最优的。 南京邮电大学计算机学院 2008年3月6.3.2 贪心法求解 例62 设有4个作业，每个作业的时限为(d0,d1,d2,d3)=(2,1,2,1),收益为(p0,p1,p2,p3)=(100,10,15,27)。 南京邮电大学

7、计算机学院 2008年3月 南京邮电大学计算机学院 2008年3月【程序63】带时限作业排序的贪心算法 void GreedyJob(int d, Set X, int n) /前置条件：p0p1,pn-1 X=0; for (int i=1;in;i+) if ( 集合 Xi 中作业都能在给定时限内完成) X=Xi; 南京邮电大学计算机学院 2008年3月6.3.3 算法正确性 定理62 程序62的贪心算法对于带时限作业排序问题将得到最优解。 南京邮电大学计算机学院 2008年3月 南京邮电大学计算机学院 2008年3月 南京邮电大学计算机学院 2008年3月6.3.4 可行性判定 定理63

8、 X=（x0,x1,xk）是k个作业的集合，=（0, 1,k）是X 的一种特定排列，它使得，其中，是作业j的时限。X是一个可行解当且仅当X中的作业能够按次序调度而不会有作业超期。 南京邮电大学计算机学院 2008年3月 南京邮电大学计算机学院 2008年3月6.3.5 作业排序贪心算法 定理63提供了一种高效的可行解判定方法。使得在按最优量度标准，即按作业收益的非增次序选择下一个作业后，可以有效地判定是否可将该作业加入已生成的部分解向量X。 南京邮电大学计算机学院 2008年3月【程序64】带时限的作业排序程序int JS(int *d, int *x, int n) /设p0p1pn-1 i

9、nt k=0; x0=0; for (int j=1;j=0 & dxrdj & dxrr+1)r-; if(r0|dxrr+1) for (int i=k;i=r+1;i-) xi+1=xi; xr+1=j; k+; return k; 南京邮电大学计算机学院 2008年3月6.3.6 一种改进算法本小节将介绍一种带时限作业排序的快速算法，它采用不同于前者的可行解判定方法，可使算法的时间从(n2)减少到接近O(n)。 南京邮电大学计算机学院 2008年3月 南京邮电大学计算机学院 2008年3月例63 设n=5个作业，作业的时限为:(d0,d1,d2,d3,d4)=(2,2,1,3,3),收

10、益为: (p0,p1,p2,p3,p4)=(20,15,10,5,1)。 南京邮电大学计算机学院 2008年3月 南京邮电大学计算机学院 2008年3月【程序65】使用并查集的带时限作业排序 int FJS(int *d,int *x,int n) UFSet s(n); int b,k=-1,*f=new intn+1; for (int i=0;i=n;i+) fi=i; 南京邮电大学计算机学院 2008年3月 for (i=0;in;i+) if(ndi) b=n;else b=di; int r=s.Find(b); if (fr) x+k=i; int t=s.Find(fr-1);

11、 s.Union(t,r); fr=ft; delete f; return k; 南京邮电大学计算机学院 2008年3月 南京邮电大学计算机学院 2008年3月6.4 最佳合并模式 南京邮电大学计算机学院 2008年3月6.4.1 问题描述 两路合并外排序算法通过反复执行将两个有序子文件合并成一个有序文件的操作，最终将n个长度不等的有序子文件合并成一个有序文件。合并n个有序子文件成为一个有序文件的合并过程可以有多种方式，称为合并模式。在整个合并过程中，需从外存读写的记录数最少的合并方案称为最佳合并模式（optimal merge pattern）。 南京邮电大学计算机学院 2008年3月例6

12、4 设有5个有序子文件（F1,F2,F3,F4,F5），其长度分别为（20，30，30，10，5）。现通过两两合并将其合并成一个有序文件。 南京邮电大学计算机学院 2008年3月带权外路径长度是针对扩充二叉树而言的。扩充二叉树（extended binary tree）中除叶子结点外，其余结点都必须有两个孩子。扩充二叉树的带权外路径长度（weighted external path length）定义为： 南京邮电大学计算机学院 2008年3月6.4.2贪心法求解 两路合并最佳模式问题的最优量度标准为带权外路径长度最小。 南京邮电大学计算机学院 2008年3月两路合并最佳模式的贪心算法简述如下

13、：设Ww0,w1 ,wn1是n个有序文件的长度；以每个权值作为根结点值，构造n棵只有根的二叉树；选择两棵根结点权值最小的树，作为左右子树构造一棵新二叉树，新树根的权值是两棵子树根的权值之和；重复第2步，直到合并成一棵二叉树为止。 南京邮电大学计算机学院 2008年3月【程序66】两路合并最佳模式的贪心算法templatestruct HNode/优先权队列中的元素的类型 operator T()const return weight; BTNode *ptr; T weight; 南京邮电大学计算机学院 2008年3月template BTNode* CreateHfmTree (T* w,i

14、nt n) /w 为一维数组保存n个权值PrioQueue HNode pq(2*n-1); BTNode*p;HNode a,b; for (int i=0;in;i+) p=new BTNode(wi); a.ptr=p;a.weight=wi; pq.Append(a); 南京邮电大学计算机学院 2008年3月for (i=1;in;i+) pq.Serve(a);pq.Serve(b); a.weight+=b.weight; p=new BTNode(a.weight,a.ptr,b.ptr); a.ptr=p; pq.Append(a); pq.Serve(a); return a

15、.ptr; 南京邮电大学计算机学院 2008年3月6.4.3 算法正确性 定理64设有n个权值W=w0,w1 ,wn1作为外结点的权值，构造两路合并树的贪心算法将生成一棵具有最小带权外路径长度的二叉树。 南京邮电大学计算机学院 2008年3月 南京邮电大学计算机学院 2008年3月6.5 最小代价生成树 南京邮电大学计算机学院 2008年3月6.5.1 问题描述问题一个无向连通图的生成树是一个极小连通子图，它包括图中全部结点，并且有尽可能少的边。一棵生成树的代价是树中各条边上的代价之和。一个网络的各生成树中，具有最小代价的生成树称为该网络的最小代价生成树（minimum-cost spanni

16、ng tree）。 南京邮电大学计算机学院 2008年3月6.5.2 贪心法求解 最优量度标准 选择使得迄今为止已入选S中边的代价之和增量最小的边 克鲁斯卡尔算法的贪心准则是：按边代价的非减次序考察E中的边，从中选择一条代价最小的边e=(u,v)。 普里姆算法的贪心准则是：在保证S所代表的子图是一棵树的前提下选择一条最小代价的边e=(u,v)。 南京邮电大学计算机学院 2008年3月【程序67】最小代价生成树的贪心算法ESetType SpanningTree(ESetType E, int n) /G=(V,E)为无向图 ESetType S=; int u,v,k=0; EType e;

17、while (kn-1 & E中尚有未检查的边) eselect(E); if (Se不包含回路) S=Se;k+; return S; 南京邮电大学计算机学院 2008年3月6.5.3普里姆算法 【程序68】普里姆算法 templatestruct ENode/带权图的边结点int adjVex;T w; ENode* nextArc; 南京邮电大学计算机学院 2008年3月template class Graphpublic: Graph (int mSize); void Prim(); protected: void Prim(int k,int* nearest,T* lowcost

18、); ENode* a; int n; ; 南京邮电大学计算机学院 2008年3月templatevoid Graph:Prim(int s)/公有成员函数int* nearest=new intn,*lowcost=new intn;Prim(s,nearest,lowcost);for(int j=0;jn;j+) cout(nearestj,“ j,lowcostj) ;coutendl; delete nearest; delete lowcost; 南京邮电大学计算机学院 2008年3月templatevoid Graph:Prim(int k, int* nearest,T* lo

19、wcost)/私有成员函数 bool* mark=new booln; ENode *p; if (kn-1) throw OutofBounds; for (int i=0;in;i+) nearesti=-1;marki=false; lowcosti=INFTY; lowcostk=0; nearestk=k; markk=true; 南京邮电大学计算机学院 2008年3月 for (i=1;inextArc) int j= p-adjVex; if (!markj )&(lowcostjp-w) lowcostj=p-w; nearestj=k; T min=INFTY; for (i

20、nt j=0;jn;j+) if (!markj)&(lowcostjmin) min=lowcostj; k=j; markk=true; 普里姆算法的运行时间是O(n2)。 南京邮电大学计算机学院 2008年3月 南京邮电大学计算机学院 2008年3月6.5.4 克鲁斯卡尔算法克鲁斯卡尔算法从边的集合E中，按照边的权值从小到大的次序依次选取边加以考察。 template struct eNodeoperator T ()const return w; int u,v;T w; ; 南京邮电大学计算机学院 2008年3月 南京邮电大学计算机学院 2008年3月 【程序69】克鲁斯卡尔算法 t

21、emplate void Graph:Kruskal( PrioQueueeNode & pq) eNode x;UFSet s(n); int u,v,k=0; 南京邮电大学计算机学院 2008年3月 while (kn-1 & !pq.IsEmpty() pq.Serve(x); u=s.Find(x.u); v=s.Find(x.v); if (u!=v) s.Union(u,v); k+; cout(x.u,“ x.v,x.w) ; coutendl; if (kn-2) throw NonConnected; 克鲁斯卡尔算法的时间复杂度为 O（elog e）。 南京邮电大学计算机学院

22、 2008年3月6.5.5 算法正确性定理65 设图G=（V，E）是一个带权连通图，U是V的一个真子集。若边(u,v)E是所有uU, vV-U的边中权值最小者，那么一定存在G的一棵最小代价生成树T=(V,S)，(u,v)S。这一性质称为MST（minimum spanning tree）性质。 南京邮电大学计算机学院 2008年3月定理66 普里姆算法和克鲁斯卡尔算法都将产生一个带权无向连通图的最小代价生成树。 南京邮电大学计算机学院 2008年3月6.6 单源最短路径 南京邮电大学计算机学院 2008年3月6.6.1 问题描述单源最短路径问题是：给定带权的有向图G=(V,E)和图中结点sV，

23、求从s到其余各结点的最短路径，其中，s称为源点。 南京邮电大学计算机学院 2008年3月 南京邮电大学计算机学院 2008年3月6.6.2 贪心法求解迪杰斯特拉（Dijkstra） 算法首先求得长度最短的一条最短路径，再求得长度次短的一条最短路径，依此类推，直到从源点到其它所有结点之间的最短路径都已求得为止。 南京邮电大学计算机学院 2008年3月6.6.3 迪杰斯特拉算法 【程序610】迪杰斯特拉算法templateclass MGraph public: MGraph(int mSize); void Dijkstra(int s,T*& d,int*& path); 南京邮电大学计算机学

24、院 2008年3月private: int Choose(int* d, bool* s); T*a; int n; ; 南京邮电大学计算机学院 2008年3月template int MGraph:Choose(int* d, bool* s) int i,minpos; T min; min=INFTY; minpos=-1; for (i=1;in;i+) if (dimin &!si) min=di;minpos=i; return minpos; 南京邮电大学计算机学院 2008年3月template void MGraph:Dijkstra(int s, T*& d,int*& p

25、ath) int k,i,j; if (sn-1) throw OutOfBounds; bool *inS=new booln; d=new Tn;path=new intn; for (i=0;in;i+) inSi=false;di=asi; if (i!=s & diINFTY) pathi=s; else pathi=-1; 南京邮电大学计算机学院 2008年3月 inSs=true; ds=0; for (i=1;in-1;i+) k=Choose(d,inS); inSk=true; for (j=0; jn; j+) if (!inSj & dk+akj dj) dj=dk+a

26、kj; pathj=k; 南京邮电大学计算机学院 2008年3月 南京邮电大学计算机学院 2008年3月6.6.4 算法正确性 定理67 已知带权有向图G=(V,E)，其源点为s，迪杰斯特拉算法使得对所有i，iV-s，di(s,i)，且一旦di= (s,i)，它将不再改变。定理68 已知带权有向图G=(V,E)，其源点为s，迪杰斯特拉算法使得对所有结点i和j, iS，jV-S，必有didj。 南京邮电大学计算机学院 2008年3月 南京邮电大学计算机学院 2008年3月定理69 已知带非负权值的有向图G=(V,E)，路径（s=v0, ,vi,vk=t）是从s到vk的一条最短路径，viV，0ikn，则子路径（s=v0, ,vi）和（vi,vk=t）必定分别是从s到vi 和vi到t的最短路径。定理610 已知带非负权值的有向图G=(V,E)，其源点为s，迪杰斯特拉算法结束时，对所有结点i，有di=(s,i)。 南京邮电大学计算机学院 2008年3月6.7 磁带最优存储 南京邮电大学计算机学院 2008年3月6.7.1 单带最优存储 问题 设有n个程序编号为0,n-1，存放在长度为L的磁带上，程序i在磁带上的存储长度为ai，0in。假定每个程序被检索地概率相等，则平均检索时间（mean retrieval time MRT）定义为 单带最优存储问题是求这n个程序的一种排列，使得MRT