算法设计与分析-作业第5章.pptx

采用回溯法，编程求解下述3个问题，并利用给定数据，验证算法正确性 n皇后问题 图的m着色问题 旅行商问题 n皇后问题 分析掌握“附件1.基于局部快速搜索的N皇后问题求解”中给出的“n皇后局部快速搜索”计算程序的原理、算法步骤、代码结构； 利用给定的程序，针对不同问题规模n，计算正确的n后排列方案： n取值： 1,000 5,000 10,000 50,000 100,000 500,000 1,000,000 3,000,000 要求 1. 对n的8个不同取值，编程统计程序运行时间t(n)和为了得到正确解需要产生的初始随机解个数m 注意： 1）采用程序设计语言提供的时间测量函数，测量程序运行时间； 2）了解程序结构，添加代码，记录产生的初始随机解个数m 3）如果由于问题规模n过小，无法测出程序准确运行时间，可适当增大n的数值 n 随机解个数m t(n） 要求（续） 2. 分析程序运行时间t(n)=O(nk)、初始随机解个数m随问题规模n的变化规律 n～lg t(n)、 n～ m； 3. 与O(n2)、O(n3)进行比较，判断算法时间复杂度O(nk)的阶次k的范围：? ≤ k ≤ ? 说明：算法在一个随机解上的优化的最坏复杂度为O(N3) 4. 以表、图2种方式，表达上述分析结果 n m lg t(n) 2 lg n 3 lg n 针对不同问题规模n，测量程序运行时间时，为保证测量结果准确性、可比性， 关闭计算机上不必要的系统程序、应用程序 不同台式机、笔记本电脑的硬件配置不同，在2台不同机器上程序运行时间t(n)不可能完全相同！！！不许抄袭！ 图的m着色问题 从昆明LTE网络中，选取部分基站，计算基站间的距离，在部分基站间引入边，得到 1）图1. n=22个基站顶点组成的图 2）图2. n=42个基站顶点组成的图 1 4 6 8 18 19 11 22 17 7 16 12 14 21 10 13 2 15 3 9 5 20 图1. 22个基站组成的无向图 1 33 42 23 27 4 40 29 22 13 20 24 11 12 36 38 10 7 39 3 17 15 30 9 8 18 19 21 34 26 32 41 37 14 28 2 5 25 35 6 31 16 图2. 42个基站组成的无向图 图的m着色问题 参照教科书，编程实现基于回溯法的图的m着色算法 针对图1、图2，给定颜色总数m后，运行程序，为图中各个基站结点，分配颜色 颜色总数m设置： 1. 图1，m=22 2. 图2，m=42 要求 1. 修改完善程序，采用尽可能少的颜色k≤m，为图中各个顶点着色； 2. 修改完善程序，统计搜索过程中扫描过的搜索树结点总数L 3. 记录程序运行时间T 4. 输出图中各个顶点的着色方案、用到的颜色总数k、搜索过的结点总数L、程序运行时间T 旅行商问题 针对昆明LTE网络，选取部分基站，计算基站间的距离，在部分基站间引入边，得到 1）图1. n=22个基站顶点组成的图，以图中基站顶点作为城市 2）图2. n=42个基站顶点组成的图，以图中基站顶点作为城市 1 4 6 8 18 19 11 22 17 7 16 12 14 21 10 13 2 15 3 9 5 20 图1. 22个城市组成的无向图 1 33 42 23 27 4 40 29 22 13 20 24 11 12 36 38 10 7 39 3 17 15 30 9 8 18 19 21 34 26 32 41 37 14 28 2 5 25 35 6 31 16 图2. 42个城市组成的无向图 旅行商问题（续） 参照教科书，编程实现基于回溯的旅行商问题算法 针对图1、图2，指定起始城市，计算最短旅行路径 1） 图1，起始城市，结点20 2） 图2，起始城市，结点16 要求 1. 修改完善程序，统计搜索过程中扫描过的搜索树结点总数L 2.修改完善程序，记录程序运行时间T 3. 针对图1、图2，输出： 1）从起始城市出发的最短旅行路径 2）路径总长度 3）扫描过的搜索树结点总数L 4）程序运行时间T 作业提交要求 三周内提交电子版，pdf格式 作业文档内容包括： 源程序代码，运行结果 文档名称： 班号_学号_姓名_算法设计与分析_第5章 邮件地址（计算机）： 邮件主题：算法设计与分析作业提交 作业提交要求 三周内提交电子版，pdf格式 作业