学习]算法设计与分析-作业-第5-6章-v.ppt

《学习]算法设计与分析-作业-第5-6章-v.ppt》由会员分享，可在线阅读，更多相关《学习]算法设计与分析-作业-第5-6章-v.ppt（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、采用回溯法，编程求解下述3个问题，利用给定数据，验证算法正确性nn皇后问题（局部搜索）n图的m着色问题（回溯）n旅行商问题（回溯，分支限界）n皇后问题n分析掌握讲义ppt和“附件1.基于局部快速搜索的N皇后问题求解”中给出的“n皇后局部快速搜索”计算程序的原理、算法步骤、代码结构n利用给定的程序，针对10个不同问题规模n，计算正确的n后排列方案。n注意：根据实验机器的实际运行情况，选择合适问题规模，但需要保持10组数据。n例如，如果问题规模n=500,000时，算法运行时间已经达到4小时左右，可以在5,000至500,000间取10个不同的n值。考察这10个问题规模n下的算法运行时间此时，n可

2、以取值：5,00010,00050,000100,000200,000250,000270,000300,000400,000500,000要求n1.对n的10个不同取值，编程统计程序运行时间t(n)和为了得到正确解需要产生的初始随机解个数mn 2.分析程序运行时间t(n)、初始随机解个数m随问题规模n的变化规律 nt(n)、nmn注意：1）采用程序设计语言提供的时间测量函数，测量程序运行时间；2）了解程序结构，添加代码，统计产生的初始随机解个数m3）如果由于问题规模n过小，无法测出程序准确运行时间，可适当增大n的数值n方法 根据资料/讲义，算法在在一个随机解上一个随机解上的最坏复杂度为的最坏

3、复杂度为O(n3)假设：t(n)=O(nk)，则 lgt(n)klgn，通过对数据的线性线性回归分析回归分析，以lgn为自变量x，以lgt(n)为因变量y，得到回归表达式 y=k*x+b，判断：1）阶次k的范围(?k?),2）t(n)C nknmt(n)lg t(n)2 lg n3 lg n对数据的线性回归分析线性回归分析nStep1.计算数据对nStep2.以lgn为自变量x，以lgt(n)为因变量ynStep3.利用Excel的”数据分析”功能，作出的散点图，观察lgn lgt(n)间的数据变化趋势nStep4.利用Excel线性回归分析函数，针对数据对，回归分析，得到表达式 y=k*x+

4、b，即 lgt(n)=k*lgn+bnExcel线性回归函数：参见百度文库“excel回归分析回归分析”http:/ n分析结果分析结果1.算法运行数据，记录在（前一张）表格中2.散点图3.线性回归表达式lgt(n)=k*lgn+b不许抄袭！n不同台式机、笔记本电脑的硬件配置不同，在2台不同机器上程序运行时间t(n)不可能完全相同！图的m着色问题n从昆明LTE网络中，选取部分基站，计算基站间的距离，在部分基站间引入边，得到1）图1.n=22个基站顶点组成的图2）图3.n=42个基站顶点组成的图说明：2个基站间如果无直接路径，则邻接矩阵中2个基站顶点间的权重为999991468181911221

5、7716121421101321539520图1.22个基站组成的无向图图2.30个基站组成的无向图281997302325262127202281216181129241014115536132174133422327440292213202411123638107393171530981819213426324137142825253563116图3.42个基站组成的无向图图的m着色问题n要求n问题用到的颜色总数m（色数）搜索过的结点总数L程序运行时间T（单位：s）22个基站42个基站旅行商问题n针对昆明LTE网络，选取部分基站，计算基站间的距离，在部分基站间引入边，得到1）图1.n=15

6、个基站顶点组成的图，以图中基站顶点作为城市从n=22的基站图中，去除2组、7个位置相邻的基站：2,12,15;4,6,8,18对应地，从22个基站顶点的邻接矩阵(.xls)中，去除这7个基站对应的行、列，得到15个基站顶点的邻接矩阵14681819112217716121421101321539520图1.15个基站组成的无向图去除顶点2,12,15及关联边去除顶点6,4,8,18及关联边旅行商问题2）图2.n=20个基站顶点组成的图，以图中基站顶点作为城市从n=22的基站图中，去除2个位置相邻的基站：4,6对应地，从22个基站顶点的邻接矩阵(.xls)中，去除这2个基站对应的行、列，得到20

7、个基站顶点的邻接矩阵14681819112217716121421101321539520图2.20个基站组成的无向图去除顶点6,4及关联边14681819112217716121421101321539520图3.22个城市组成的无向图图4.30个基站组成的无向图281997302325262127202281216181129241014115536132174旅行商问题（续）n参照教科书，编程实现回溯法、分支限界法回溯法、分支限界法，求解旅行商问题，并对比2个算法对同一规模问题的运行时间n参照图1、图2，针对指定起始城市，计算最短旅行路径1）图115个基站图，起始城市结点202）图220

8、个基站图，起始城市结点20说明：图中顶点数目为22个基站时，可能导致：回溯法运行时间较长，或分支限界法占用内存空间过多，无法求出最终解，故不考虑顶点数目过多的图。要求n1.修改完善程序，统计搜索过程中扫描过的搜索树结点总数Ln2.修改完善程序，记录程序运行时间Tn3.针对图1、图2，输出采用回溯法、分支限界采用回溯法、分支限界法得到的1）从起始城市出发的最短旅行路径2）路径总长度3）扫描过的搜索树结点总数L4）程序运行时间T 结果记录在下列表格中：问题求解算法最短回路路径总长度（单位：m）搜索过的结点总数程序运行时间（单位：s）15个基站回溯分支限界20个基站回溯分支限界22个基站（可选）回溯法说明：如果时间充裕如果时间充裕（不做硬性要求）（不做硬性要求），试着针对n=22个基站组成的无向图，采用回溯法求解最短回路。n=22时，采用分支限界法求解时，可能需要搜索和记录的活结点过多，导致内存溢出。作业提交要求n最迟至第19周，提交电子版，pdf格式n作业文档内容包括：源程序代码，运行结果n文档名称：班号_学号_姓名_算法设计与分析_第5-6章n邮件地址（计算机）：邮件主题：算法设计与分析作业提交