算法分析与设计

时间

2020.5.17

 实验名称

世界名画陈列馆问题

实验目的

通过上机实验，要求深层掌握回溯法算法的问题描述、算法设计思想、程序设计。

实验原理

给定任意几组数据，利用回溯法限界剪枝的思想，根据题目所给出的条件，计算出警卫机器人数量最少的最佳哨位安排方案。

实验步骤

 问题分析：

给定n(20)和m(20),表示一个n*m的网格,可在格点上放置机器人,机器人会使所在格点和上下左右格点都进入监视状态,问最少放置多少个机器人会使得所有格点都进入监视状态?

本题的状态空间树是一颗子集树，可以通过子集树的回溯法框架解题；

使用回溯法,从上到下从左到右依次考察每个格子的格子设哨位的情况和每个格子受监视情况。
    用x[i][j]表示陈列室（i，j）设置机器人哨位的状态、y[i,j]表示（i，j）受监视的状态，已设置警卫机器人哨位数K，已受监视陈列馆数t、当前最优警卫机器人哨位数bestk；

 剪枝策略：

1. 可以证明,放置的机器人个数不会超过n*m/3+1个(按每个机器人仅辐射左右或上下考虑).以n*m/3+2为初始最优值,当放置的个数超过当前最优值时,剪去；
2. 可以证明,当前访问的格点(i,j)已被监视时,放置在(i,j)的情况一定不会比放置在(i+1,j+1)的情况好.当(i+1,j+1)不在网格中时,(i+1,j)和(i,j+1)同理；所以,如果(i,j)已被监视,则不需要在此处放置机器人,直接跳过即可；

1. 当(i,j)未被监视时,若(i,j+1)已被监视,则在(i,j)放置情况q接结点一定不会比在(i+1,j)放置的情况p结点好（q受控于p），所以当且仅当(i,j)在网格右下角或者(i,j+1)未被监视时才考虑放置在(i,j)的情况；
2. 当(i,j)未被监视时,若(i,j+1)和(i,j+2)均被监视,则在(i,j+1)放置的情况r结点一定不会比在(i+1,j)放置的情况p结点好,所以当且仅当(i,j+1)或(i,j+2)未被监视时才考虑放置在(i,j+1)的情况；

即考虑顺序为p->q->r；

1. 当i=n时,不考虑放置在(i+1,j)的情况；
2. 记录已经监视的格点数,剩余未监视格点数/5（还需哨兵数的下界） + 已放置哨兵数如果大于最优值,则一定达不到比当前最优值更好的情况,剪去.
3. 类似于(6),考虑更紧的情况,并非每个机器人都能独立监视5个格点,至少会有m/4+1的冗余,这个剪枝仅适用于i<n-1的情况,因为最后两行由于最优值和已放置个数非常接近,总是达不到这个值.这个剪枝策略参考自习题答案。

 算法步骤：

 ①将用例数据从文件中读取并初始化数据；

 ②从上到下从左至右开始遍历n*m矩阵（遍历解空间树），对当前位置及（i，j）进行如下操作：

 ③如果到达了叶结点即i>n，且当前哨兵数小于当前最优值，则更新最优值与最优解；

   否则，如果当前位置满足了显示剪枝策略，则开始递归返回，不再往下深入；

   如果不满足显示剪枝条件，则检查p、q、r的受控情况及时剪枝，按p、q、r顺序扩展结点；

 ⑤矩阵遍历结束后的bestk即为最优值，输出；

关键代码

关键代码（带注释）

1. 所需数据

2. 放置机器人并更新周围监视状态change（）

放置机器人后x[i][j]=1，且周围五个点的监视情况＋1，如果y[i][j]=1，则说明是第一次受监视，将受监视结点数t+1；

3. 解除机器人并恢复被监视状态restore（）

若y[i][j]=0，则说明不再受监视，受监视节点数t-1；

4. 初始化函数compute（）

初始化所有数据，如果是1*1的矩阵则直接输出，否则开始遍历解空间树；

5. 回溯法求解（核心部分）

找到从（i，j）往后的第一个未受监视的结点；

如果达到边界则更新最优解；

按照显示剪枝条件进行剪枝；

按照p、q、r结点的顺序进行判断，如果不需剪枝，则扩展结点；

测试结果

运行结果截图及分析

对于题目样例：

结果正确；

 对于不同规模的数据：（3、6、9）

 时间复杂度随n的小幅增长呈现出指数级上升；

时间复杂度分析：

 回溯法求解子集树框架的时间复杂度为O（2 m * n）；

 空间复杂度为矩阵大小O（m*n）；

实验心得

通过这次实验，我回顾了回溯算法的子集树的解题框架基本原理，对剪枝函数和限界函数有了更深层次理解，这道题比之上面的三道题都要难，难点就在于剪枝函数以及解空间树的遍历顺序；

掌握了这道题基本上就掌握到了回溯法的核心思想了，因此花费大量的时间理解、解决这道题是有意义的。