世界名画陈列馆问题(回溯法).doc

算法设计与分析课程设计题目： 世界名画陈列馆问题(回溯法) 专业： 班级： 学号： 姓名： 计算机工程系 2012年 11 月 16 日一、算法问题描述世界名画陈列馆问题。世界名画陈列馆由mn个排列成矩形阵列的陈列室组成。为了防止名画被盗，需要在陈列室中设置警卫机器人哨位。每个警卫机器人除了监视它所在的陈列室外，还可以监视与它所在的陈列室相邻的上、下、左、右4 个陈列室。试设计一个安排警卫机器人哨位的算法，使得名画陈列馆中每一个陈列室都在警卫机器人的监视之下，且所用的警卫机器人数最少。二、算法问题形式化表示本问题的m*n的陈列室的解可表示如下图所示。其中1代表在该陈列室设置警卫机器人哨位，0表示未在该陈列室设置警卫机器人哨位。01001001000100101000010000100001010010000001001010100101 m*n陈列室的可能解 最为极端的情况是所有元素的值为1。那什么情况下是最优解呢？就是设置警卫机器人哨位数最少即为最优。因为每个矩阵中的值都可以为1或0，有m*n个元素，有种可能满足约束条件的矩阵，要从种可能中遍历找到满足约束条件的1的个数最小的矩阵。由此可见这是一个NP问题。这里的约束条件就是当某一个元素为1时，相邻的4个方向上的元素值可以为0。三、期望输入与输出输入:第一行有2 个正整数m和n (1m,n20)输出：将计算出的警卫机器人数及其最佳哨位安排输出。第一行是警卫机器人数；接下来的m行中每行n个数，0 表示无哨位，1 表示哨位。样例输入：4 4样例输出：40 0 1 01 0 0 00 0 0 10 1 0 0四、算法分析与步骤描述 从上到下、从左到右的顺序依次考查每一个陈列室设置警卫机器人哨位的情况，以及该陈列室受到监视的情况，用i,j表示陈列室的位置，用xij表示陈列室i,j当前设置警卫机器人哨位的状态。当xij=1时，表示陈列室i,j设置了警卫机器人，当xij=0时，表示陈列室i,j没有设置了警卫机器人。用yij表示陈列室i,j当前受到监视的的警卫机器人的数量。当yij0时，表示陈列室i,j受到监视的警卫机器人的数量，当yij=0时，表示陈列室i,j没有受到监视。设当前已经设置的警卫机器人的哨位数为k，已经受到监视的陈列室的数量为t，当前最优警卫机器人哨位数为bestc。设回溯搜索时，当前关注的陈列室是i,j，假设该陈列室已经受到监视，即yij=1，此时在陈列室i,j处设置一个警卫机器人哨位，即xij=1，相应于解空间树的一个节点q，在陈列室i+1,j处设置一个机器人哨位，xi+1j=1，相应于解空间树的另一个节点p。容易看出，以q为根的子树的解，不优于以p为根的子树的解，以q为根的子树可以剪去。因此，在以从上到下，从左到右的顺序依次考察每一个陈列室时，已受监视的陈列室不必设置警卫机器人哨位。设陈列室i,j是从上到下、从左到右搜索到的第一个未受监视的陈列室，为了使陈列室i,j受到监视，可在陈列室i+1,j、i,j、i,j+1处设置警卫机器人哨位，在这3处设置哨位的解空间树中的结点分别为p、q、r。当yij+1=1时，以q为根的子树的解，不优于以p为根的子树的解，当yij+1=1且yij+2=1时，以r为根的子树的解，不优于以p为根的子树的解。搜索时应按照p、q、r的顺序来扩展结点，并检测节点p对节点q和节点r的控制条件。 int bestx=new intMAXMAX; /x用来设置当前警卫，y用来表示监控/情况，bestx返回最终结果int n, m, best, k = 0, t = 0; /当前已设置的警卫数为k，受监视的陈列室/数为t，当前最少警卫数为bestvoid change(int i, int j) /在(i, j)处设置一个警卫，并改变其周围受/监控情况 xij = 1; k+; for (int r = 1; r 2 容易验证 当n3，m3和n3，m4时无解，n4，m4有解。 设置哨位时，允许在的n1行和m1列设置哨位，但不要求的第n1行和m1列陈列室受到监视，那么当n=3且m=5时在不重复监视下有解那么n3，m5的不可重复监视问题一定有解。但是通过验证n3，m5的不可重复监视哨位设置问题无解，那么当n=3且m=5时在不重复监视下无解。 通过以上讨论就将所有情况分析完全了，简单写一个包含多个条件判断的程序就可以实现该算法。六、算法运行截图 七、算法复杂度分析 回溯法需要为问题定义一个解空间，这个解空间必须至少包含问题的一个解（可能是最优的）。使用递归