《回溯法实验》实验报告.pdf

分享高质量文档

实验4、《回溯法实验》

一、实验目的

1.掌握回溯算法思想

2.掌握回溯递归原理

3.了解回溯法典型问题

二、实验内容

1.编写一个简单的程序，解决8皇后问题。

2.批处理作业调度问题

[问题描述]给定n个作业的集合J=(J1,J2,…,Jn)。每一个作业Ji都有两项任务

需要分别在2台机器上完成。每一个作业必须先由机器1处理，然后再由机器2处理。作业

Ji需要机器i的处理时间为tji，i=1,2,…,n;j=1,2。

对于一个确定的作业调度，设Fji是作业i在机器i上完成处理的时间。则所有作业在

机器2上完成处理的时间和成为该作业调度的完成时间和。

批处理作业调度问题要求对于给定的n个作业，制定一个最佳的作业调度方案，使其完

成时间和达到最小。

要求输入：

1）作业数2）每个作业完成时间表：

作业完成时间机器1机器2

作业121

作业231

作业323

要求输出：1）最佳完成时间2）最佳调度方案

提示：算法复杂度为O(n!),建议在测试的时候n值不要太大，可以考虑不要超过12。

3.数字全排列问题

任意给出从1到N的N个连续的自然数，求出这N个自然数的各种全排列。如N=3时，

共有以下6种排列方式：123，132，213，231，312，321。

注意：数字不能重复，N由键盘输入（N=9）。

三、算法思想分析

1.八皇后问题是典型的回溯问题，先从空格子起逐行放皇后，如果符合要求即安全则放

置，否则返回上一行下一个位置继续，直至最后一行安全放置则为一种放置方式。

2.批处理作业调度的解空间为排列数，不断利用递归函数直至叶节点，剪枝函数为当前

第1页共9页

分享高质量文档

分享高质量文档

用时与最佳用时的比较。关于时间的计算，每次选择作业后先将机器1用时累加，机器2

上总用时需要先比较上一个作业完成时间与此时机器1上的总用时，如果机器1上总用时大

于上一作业用时，那么机器2上用时则加上机器1上用时与此作业在机器2上的单独用时，

反之，则代表此时机器2仍然在处理上一任务，那么机器2上用时则加上上一作业用时与此

作业在机器2上的单独用时。

3.数字全排列问题的解空间为排列树，依次向下排列，判断是否继续的条件为该数字是

否已经使用，通过一个flag与for循环判断即可，直至到了最后一个数字则输出结果。

四、实验过程分析

1.八皇后问题的难点在于安全条件的设计，即同一列，对角线都不能同时放置，对角线

的设计比较巧妙，根据PPT设计向右斜为i-j+N,向左斜为i+j，利用二维数组很好的避免了

代码的重复与累赘。

2.批处理作业调度的回溯条件即当前时间与最佳时间的比较，本题的难点在于时间的计

算，最开始对于机器2上的总用时是用一个整型数据记录，但没办法与上一个作业用时比较，

或者说不方便进行下一次回溯条件的改变，后来参考课本PPT采用数组记录就解决了。计算

时间的另一个问题即作业进入机器2上时，上一个作业是否已经完成，需不需要等待，这里

要加判断条件，否则时间计算会出问题。

3.从数字全排列问题的实验中，我更加熟悉了回溯的基本套路，判断数字是否使用的

flag和for循环设计很典型也很实用。

五、算法源代码及用户屏幕

1.（1）算法源码

/***************************************

八皇后问题。

codeblocksC++

2018.11.3

**********************