第5章 回溯算法实验指导.doc

第5章回溯算法
实验5.1回溯算法的实现和时间复杂度测试
1.实验目的
编程实现经典的回溯算法，理解回溯算法设计的基本思想、程序实现的相关技巧，加深对回溯算法设计与分析思想的理解。通过程序的执行时间测试结果，与理论上的时间复杂度结论进行对比、分析和验证。
2.算法原理
回溯算法的基本思想
回溯算法是一个既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先策略从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则进入该子树，继续按深度优先的策略进行搜索。回溯算法的基本设计范式如下：
Backtrack(n)
k=1
while(k>0)do
ifTk(x1,x2,...,x(k-1))的值还未取遍then
xk=Tk(x1,x2,...,x(k-1))中未取遍过的值
ifBk(x1,x2,...,xk)then//可行解//
(x1,x2,...,xk)被激活
endif
ifk==nthen输出(x1,x2,…,xn)
elsek=k+1；//深度扩展搜索//
endif
endif
elsek=k-1//试探完了所有的xk，回溯//
endwhile
测试算法
n皇后问题是使用回溯算法求解的代表问题，算法如下：
NQueens(n)
x1=0；k=1//k是当前行；xk是当前列//
whilek>0do//对所有的行执行以下语句//
xk=xk+1//移到下一列//
whilexk≤nandnotPlace(k)do//不可放置//
xk=xk+l
ifxk≤nthen//找到一个位置//
ifk=nthen//是否是一个完整的解//
print(x)//是，则打印这个数组//
else
k=k+1
xk=0
endif
elsek=k1//回溯//
endif
endwhile
最坏情况下，算法具有指数计算时间O(nn)；而实际中，由于剪枝策略的应用，使得实际计算时间远远低于最坏情况下的计算时间。
3.实验内容
（1）编程实现以上n皇后问题的回溯算法，记录随着皇后数n增加算法的执行时间，分析并以图形方式展现增长率；测试、验证、对比算法的时间复杂度。
（2）回溯算法应用：编程实现批处理处业调度问题。
4.实验步骤和要求
(1)编程实现以上NQueens算法，并进行测试，保证程序正确无误。其中，分别在程序开始和结束处设置记录系统当前时间的变量、用于计算程序执行的时间（以毫秒(ms)作为时间的计数单位）。
(2)测试随着n增加程序执行时间增加的趋势（n=4,8,15,20,25,30,35），并使用MSExcel图表绘制工具生成程序执行时间的曲线图。
(3)与理论时间复杂度结论对比分析，完成实验报告。
(4)算法应用编程：利用回溯法编程实现批处理处业调度问题，要求有较好的数据输入输出设计、程序中关键位置给出文字注释，实验报告中就给出求解该问题的分析过程。