第5章 回溯算法实验指导

《第5章 回溯算法实验指导》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第5章回溯算法实验5.1回溯算法的实现和时间复杂度测试1.实验目的编程实现经典的回溯算法，理解回溯算法设计的基本思想、程序实现的相关技巧，加深对回溯算法设计与分析思想的理解。通过程序的执行时间测试结果，与理论上的时间复杂度结论进行对比、分析和验证。2.算法原理n回溯算法的基本思想回溯算法是一个既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先策略从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树

2、的系统搜索，逐层向其祖先结点回溯。否则进入该子树，继续按深度优先的策略进行搜索。回溯算法的基本设计范式如下：Backtrack(n)k=1while(k>0)doifTk(x1,x2,...,x(k-1))的值还未取遍thenxk=Tk(x1,x2,...,x(k-1))中未取遍过的值ifBk(x1,x2,...,xk)then//可行解//(x1,x2,...,xk)被激活endififk==nthen输出(x1,x2,…,xn)elsek=k+1；//深度扩展搜索//endifendifelsek=k-1//试

3、探完了所有的xk，回溯//endwhilen测试算法n皇后问题是使用回溯算法求解的代表问题，算法如下：NQueens(n)x1=0；k=1//k是当前行；xk是当前列//whilek>0do//对所有的行执行以下语句//xk=xk+1//移到下一列//whilexk≤nandnotPlace(k)do//不可放置//xk=xk+lifxk≤nthen//找到一个位置//ifk=nthen//是否是一个完整的解//print(x)//是，则打印这个数组//elsek=k+1xk=0endifelsek=k-1//回溯

4、//endifendwhile最坏情况下，算法具有指数计算时间O(nn)；而实际中，由于剪枝策略的应用，使得实际计算时间远远低于最坏情况下的计算时间。3.实验内容（1）编程实现以上n皇后问题的回溯算法，记录随着皇后数n增加算法的执行时间，分析并以图形方式展现增长率；测试、验证、对比算法的时间复杂度。（2）回溯算法应用：编程实现批处理处业调度问题。4.实验步骤和要求(1)编程实现以上NQueens算法，并进行测试，保证程序正确无误。其中，分别在程序开始和结束处设置记录系统当前时间的变量、用于计算程序执行的时间（以毫秒

5、(ms)作为时间的计数单位）。(2)测试随着n增加程序执行时间增加的趋势（n=4,8,15,20,25,30,35），并使用MSExcel图表绘制工具生成程序执行时间的曲线图。(3)与理论时间复杂度结论对比分析，完成实验报告。(4)算法应用编程：利用回溯法编程实现批处理处业调度问题，要求有较好的数据输入输出设计、程序中关键位置给出文字注释，实验报告中就给出求解该问题的分析过程。