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

《算法设计与分析-作业-第4章-2016》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、ype**t,int**s){for(inti=1;i<=n;i++)t[i][i]=0;for(intr=2;r<=n;r++)/*第1层循环for(inti=1;i<=n-r+1;i++){/*第2层循环intj=i+r–1t[i][i]=t[i+1][j]+w(i-1,i,j)s[i][i]=i;for(intk=i+1;k

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

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

6、边长弦长总和3.与第3章基于动态规划的最优三角剖分结果进行比较——目标值、剖分形状哈夫曼编码利用“附件2.哈夫曼编码输入文本”给出的文本信息，统计26个英文字母及#出现的频率；对{a,b,c,..,x,y,z,#}，设计哈夫曼编码；按照哈夫曼编码，对输入文本重新编码；计算采用哈夫曼编码，输入文本需要的存储比特数，并与定长编码方式需要的存储比特数进行比较。附件2.哈夫曼编码输入文本内容Informally,analgorithmisanywelldefinedcomputationalprocedurethattakessomevalue,orsetofvalues,asinpu

7、tandproducessomevalue,orsetofvalues,asoutput.Analgorithmisthusasequenceofcomputationalstepsthattransformtheinputintotheoutput.Wecanalsoviewanalgorithmasatoolforsolvingawell-specifiedcomputationalproblem.Thestatementoftheproblemspecifiesingeneralter