算法设计与分析-作业-第5-6章-v

采用回溯法，编程求解下述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)和为了得到正确解需要产生的初始随机解个数m2.分析程序运行时间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?),2）t(n)Cnk,对数据的线性回归分析,Step1.计算数据对Step2.以lgn为自变量x，以lgt(n)为因变量yStep3.利用Excel的”数据分析”功能，作出的散点图，观察lgnlgt(n)间的数据变化趋势Step4.利用Excel线性回归分析函数，针对数据对，回归分析，得到表达式y=k*x+b，即lgt(n)=k*lgn+bExcel线性回归函数：参见百度文库“excel回归分析”,分析结果1.算法运行数据，记录在（前一张）表格中2.散点图3.线性回归表达式lgt(n)=k*lgn+b,不许抄袭！,不同台式机、笔记本电脑的硬件配置不同，在2台不同机器上程序运行时间t(n)不可能完全相同！,图的m着色问题,从昆明LTE网络中，选取部分基站，计算基站间的距离，在部分基站间引入边，得到1）图1.n=22个基站顶点组成的图2）图3.n=42个基站顶点组成的图,说明：2个基站间如果无直接路径，则邻接矩阵中2个基站顶点间的权重为99999,图1.22个基站组成的无向图,图2.30个基站组成的无向图,图3.42个基站组成的无向图,图的m着色问题,要求,旅行商问题,针对昆明LTE网络，选取部分基站，计算基站间的距离，在部分基站间引入边，得到1）图1.n=22个基站顶点组成的图，以图中基站顶点作为城市2）图2.n=30个基站顶点组成的图，以图中基站顶点作为城市,图1.22个城市组成的无向图,图2.30个基站组成的无向图,图3.42个城市组成的无向图,旅行商问题（续）,参照教科书，编程实现回溯法、分支限界法，求解旅行商问题，并对比2个算法对同一问题的运行时间针对图1、图2，针对指定起始城市，计算最短旅行路径1）图122个基站图，起始城市结点202）图230个基站图，起始城市结点4,说明：图中顶点数目为42个基站时，可能运行时间过长，无法求出最终解，故不考虑图3,要求,1.修改完善程序，统计搜索过程中扫描过的搜索树结点总数L2.修改完善程序，记录程序运行时间T3.针对图1、图2，输出采用回溯法、分支限界法得到的1）从起始城市出发的最短旅行路径2）路径总长度3）扫描过的搜索树结点总数L4）程序运行时间T结果记录在下列表格中：,作业提交要求,三周内提交电子版，pdf格式作业文档内容包括：源程序