《算法设计与分析作业第56章v1》由会员分享，可在线阅读，更多相关《算法设计与分析作业第56章v1（21页珍藏版）》请在金锄头文库上搜索。
1、采用回溯法，编程求解下述3个问题，利用给定数据，验证算法正确性n皇后问题（局部搜索）图的m着色问题（回溯）旅行商问题（回溯，分支限界）n皇后问题分析掌握讲义ppt和“附件1.基于局部快速搜索的N皇后问题求解”中给出的“n皇后局部快速搜索”计算程序的原理、算法步骤、代码结构；利用给定的程序，针对不同问题规模n，计算正确的n后排列方案：n取值：10,00050,000100,000500,0001,000,0003,000,0006,000,00010,000,00030,000,00060,000,000要求1.对n的10个不同取值，编程统计程序运行时间t(n)和为了得到正确解需要产生的初始随机
2、解个数m 2. 分析程序运行时间t(n)、初始随机解个数m随问题规模n的变化规律 nt(n)、 nm注意：1）采用程序设计语言提供的时间测量函数，测量程序运行时间；2）了解程序结构，添加代码，统计产生的初始随机解个数m3）如果由于问题规模n过小，无法测出程序准确运行时间，可适当增大n的数值方法 根据资料/讲义，算法在在一个随机解上一个随机解上的最坏复杂度为的最坏复杂度为O(n3) 假设： t(n)=O(nk)，则 lgt(n) klgn， 通过对数据的线性线性回归分析回归分析，以lgn为自变量x，以lgt(n)为因变量y，得到回归表达式 y = k*x +b，判断：1）阶次k的范围( ? k
3、?),2）t(n) C nknmt(n)lg t(n)2 lg n3 lg n对数据的线性回归分析线性回归分析Step1. 计算数据对Step2. 以lgn为自变量x，以lgt(n)为因变量yStep3. 利用Excel的”数据分析”功能，作出的散点图，观察lgn lgt(n)间的数据变化趋势Step4. 利用Excel线性回归分析函数，针对数据对，回归分析，得到表达式 y = k*x +b，即 lgt(n) = k* lgn + bExcel线性回归函数：参见百度文库“excel回归分析回归分析”http:/ n分析结果分析结果1. 算法运行数据，记录在（前一张）表格中2. 散点图3. 线性
4、回归表达式lgt(n) = k* lgn + b不许抄袭！不同台式机、笔记本电脑的硬件配置不同，在2台不同机器上程序运行时间t(n)不可能完全相同！图的m着色问题从昆明LTE网络中，选取部分基站，计算基站间的距离，在部分基站间引入边，得到1）图1.n=22个基站顶点组成的图2）图3.n=42个基站顶点组成的图说明：2个基站间如果无直接路径，则邻接矩阵中2个基站顶点间的权重为9999914681819112217716121421101321539520图1.22个基站组成的无向图图2.30个基站组成的无向图28199730232526212720228121618112924101411553
5、6132174133422327440292213202411123638107393171530981819213426324137142825253563116图3.42个基站组成的无向图图的m着色问题要求问题用到的颜色总数m（色数）搜索过的结点总数L程序运行时间T（单位：s）22个基站42个基站旅行商问题针对昆明LTE网络，选取部分基站，计算基站间的距离，在部分基站间引入边，得到1）图1.n=22个基站顶点组成的图，以图中基站顶点作为城市2）图2.n=30个基站顶点组成的图，以图中基站顶点作为城市14681819112217716121421101321539520图1.22个城市组成的
6、无向图图2.30个基站组成的无向图281997302325262127202281216181129241014115536132174133422327440292213202411123638107393171530981819213426324137142825253563116图3.42个城市组成的无向图旅行商问题（续）参照教科书，编程实现回溯法、分支限界法回溯法、分支限界法，求解旅行商问题，并对比2个算法对同一问题的运行时间针对图1、图2，针对指定起始城市，计算最短旅行路径1）图122个基站图，起始城市结点202）图230个基站图，起始城市结点4说明：图中顶点数目为42个基站时，可能
7、运行时间过长，无法求出最终解，故不考虑图3要求1.修改完善程序，统计搜索过程中扫描过的搜索树结点总数L2.修改完善程序，记录程序运行时间T3.针对图1、图2，输出采用回溯法、分支限界采用回溯法、分支限界法得到的1）从起始城市出发的最短旅行路径2）路径总长度3）扫描过的搜索树结点总数L4）程序运行时间T 结果记录在下列表格中：问题求解算法最短回路路径总长度（单位：m）搜索过的结点总数程序运行时间（单位：s）22个基站回溯分支限界30个基站回溯分支限界作业提交要求三周内提交电子版，pdf格式作业文档内容包括：源程序代码，运行结果文档名称：班号_学号_姓名_算法设计与分析_第5-6章邮件地址（计算机）：邮件主题：算法设计与分析作业提交
