算法设计与分析-作业-第4章

《算法设计与分析-作业-第4章》由会员分享，可在线阅读，更多相关《算法设计与分析-作业-第4章（25页珍藏版）》请在装配图网上搜索。

1、 编程实现下述4个算法，利用给定数据，验证算法正确性n基于贪心法的凸多边形三角剖分n哈夫曼编码n单源最短路径n最小生成树基于贪心法的凸多边形三角剖分-参见第3章pptn利用：1.“附件个基站凸多边形数据”2.“附件3-2.29个基站凸多边形数据”给出的21凸多边形顶点数据、29凸多边形顶点数据，以顶点间的地理距离作为连接2个顶点的边、弦的权值，对这2个凸多边形采用贪心法进行三角剖分。算法要求：自上而下，（递归）分治，一分为三算法要求：自上而下，（递归）分治，一分为三凸多边形三角剖分n21凸多边形构造方法 根据xx市TD-LTE网络配置数据，选取全部基站eNODEB；以这些基站作为平面点，构造平

2、面点集的凸包，得到具有21个顶点的凸21边形 动态规划最优三角剖分（学生作业样例）凸多边形三角剖分n29凸多边形构造方法 根据xx市TD-LTE网络配置数据，选取部分基站eNODEB；以这些基站作为平面点，构造平面点集的凸包，得到具有29个顶点的凸29边形 动态规划最优三角剖分（学生作业样例）动态规划凸多边形最优三角剖分 .穷搜0606006min 0 16()kkijttkt kw v v vij k=3k=1由于在计算时还不知道k的确切位置，而k的所有可能位置只有j-i个，因此可以在这j-i个位置中选出使tij值达到最小的位置由此，tij可递归地定义为：时间复杂性O(n3)，当n较大时，算

3、法运行时间较长jijivvvwjktkitjitjkijki)(1min019void MinWeightTriangulation(int n，Type*t,int*s)for(int i=1;i=n;i+)tii=0;for(int r=2;r=n;r+)/*第1层循环 for(int i=1;i=n-r+1;i+)/*第2层循环 int j=i+r 1 tii=ti+1j+w(i-1,i,j)sii=i;for(int k=i+1;k i+r-1;k+)int u=tik+tk+1j+W(i-1,k,j);if(utij)tij)=u;sij)=k;利用启发式信息，在第2层循环内部，直接

4、选取某个vk，避免第3层循环，算法时间复杂性降为O(n2)Z找到更好的划分，并记录结果t:记录子问题最优值s：记录子问题最优划分点 子问题vi、vj,子问题规模r=j-i+1自下而上，不同规模r的子问题ii+1j贪心法凸多边形三角剖分n自上而下，（递归）分治，贪心 避免求解过多子问题n根据启发式信息选取断点vk：选取使dist(v0,vk)+dist(vk,vn)最小的vk 自上而下递归分治法，自上而下递归分治法，采用固定(贪心)分解方式：一分为三、一分一分为三、一分为二为二v0v1v2v3v4v5v6v0v1v2v3v4v5v6step1.v0v1v2v3v4v5v6=v0v1v2v3+v0

5、v3v6+v3v4v5v6step2.v3v4v5v6 =v3v5v6+v3v4v5不需要生成子问题不需要生成子问题v4v5v6优点：避免生成过多不需要的、没优点：避免生成过多不需要的、没有出现在最终剖分结果中的子问题有出现在最终剖分结果中的子问题递归分治法，递归分治法，一分为三、一分为二，分解标准一分为三、一分为二，分解标准贪心策略：贪心策略：v0v1v2v3v4v5v6对七边形v0v1v2v3v4v5v6，从非起点、终点v1v2v3v4v5这5个顶点中选择vk，如v3，使三角形v0vkv6的三边权重之和最小/最大v0v1v2v3v4v5v6对四边形v3v4v5v6，从v4v5这2个顶点中选

6、择vk，如v5，使三角形v3vkv6的三边权重之和最小/最大贪心法凸多边形三角剖分n要求 1.做图表示结果 2.计算三角剖分对应的目标值边长弦长总和 3.与第3章基于动态规划的最优三角剖分结果进行比较目标值、剖分形状 哈夫曼编码n利用“附件2.哈夫曼编码输入文本”给出的文本信息，统计26个英文字母及#出现的频率；n对a,b,c,.,x,y,z,#，设计哈夫曼编码；n按照哈夫曼编码，对输入文本重新编码；n计算采用哈夫曼编码，输入文本需要的存储比特数，并与定长编码方式需要的存储比特数进行比较。附件2.哈夫曼编码输入文本内容nInformally,an algorithm is any wellde

7、fined computational procedure that takes some value,or set of values,as input and produces some value,or set of values,as output.An algorithm is thus a sequence of computational steps that transform the input into the output.nWe can also view an algorithm as a tool for solving a well-specified compu

8、tational problem.The statement of the problem specifies in general terms the desired input/output relationship.The algorithm describes a specific computational procedure for achieving that input/output relationship.nAn algorithm is said to be correct if,for every input instance,it halts with the cor

9、rect output.We say that a correct algorithm solves the given computational problem.An incorrect algorithm might not halt at all on some input instances,or it might halt with an answer other than the desired one.Contrary to what one might expect,incorrect algorithms can sometimes be useful,if their e

10、rror rate can be controlled.We shall see an example of this in Chapter when we study algorithms for finding large prime numbers.Ordinarily,however,we shall be concerned only with correct algorithms.n空格、标点符号用”#“替换要求 给出如下结果n1.a,b,c,.,x,y,z,#中各成员在文本中的出现频率和哈夫曼编码n2.采用哈夫曼编码、定长编码，输入文本需要的存储比特数单源最短路径n从昆明LTE网

11、络中，选取部分基站，计算基站间的距离，在部分基站间引入边，得到1）22个基站顶点组成的图2）42个基站顶点组成的图 源点基站ID：567443终点基站ID：3310914681819112217716121421101321539520终点基站ID：565667源点基站ID：565845133422327440292213202411123638107393171530981819213426324137142825253563116单源最短路径n对22个基站顶点组成的图，以基站567443为源点，1.计算567443到其它各点的单源最短路径；2.计算567443到33109的最短路径 n对4

12、2个基站顶点组成的图，以基站565845为源点，1.计算565845到其它各点的单源最短路径；2.计算565845到565667的最短路径最小生成树n从昆明LTE网络中，选取部分基站，计算基站间的距离，在部分基站间引入边，得到1）22个基站顶点组成的图2）42个基站顶点组成的图 14681819112217716121421101321539520133422327440292213202411123638107393171530981819213426324137142825253563116最小生成树n生成这2个图的最小生成树n要求：n采用K算法，或P算法；n给出最小生成树的成本/代价/耗费costn做图，呈现出最小生成树,可以在原图上，用红色、粗线条，标记最小生成树的边 作业提交要求n三周内提交电子版，pdf格式 n作业文档内容包括：源程序代码，运行结果n文档名称：班号_学号_姓名_算法设计与分析_第4章n助教邮件地址（计算机）：邮件主题：算法设计与分析作业提交