世界名画陈列馆问题(分支限界法)(共4页).doc

精选优质文档-倾情为你奉上算法设计与分析课程设计题目： 世界名画陈列馆问题(分支限界法) 专业： 网络工程 班级： 学号： 姓名： 计算机工程系 2012年 11 月 16 日一、算法问题描述世界名画陈列馆问题的优先队列式分支限界法。世界名画陈列馆由m×n个排列成矩形阵列的陈列室组成。为了防止名画被盗，需要在陈列室中设置警卫机器人哨位。每个警卫机器人除了监视它所在的陈列室外，还可以监视与它所在的陈列室相邻的上、下、左、右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四、算法分析与步骤描述 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。与回溯法不同，在搜索问题的解空间树时，每一个活结点只有一次机会成为扩展结点，活结点一旦成为扩展结点，就一次性产生其所有儿子结点，在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃。其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。有两种常用的方法可用来选择下一个E-结点：（1）先进先出(FIFO)即从活结点表中取出结点的顺序与加入结点的顺序相同，因此活节点表的性质与队列相同。（2）最小耗费或最大收益法在这种模式中，每个结点都有一个对应的耗费或收益。如果查找一个具有最小耗费的解，则活节点表可以用最小堆来建立，下一个E-结点就是具有最小耗费的活结点；如果希望搜索一个具有最大收益的解，则可用最大堆来构造活结点表，下一个E-结点是具有最大收益的活结点。它采用自底向上的顺序，找到边界条件，将整个问题的最优解与问题的局部最优解用递推的等式联系起来，把边界条件代入递推等式逐步求得最优解。class Monitor int m,n;/矩阵的大小 char Matrix;/矩阵int Place;/监控所放置的位置 i = room / 5;/min是在此矩阵内所需要的最少监控数量 if(room % 5!=0) i+; for(i = 0; i < room; i+)/输出矩阵 if(i != 0 && i % n = 0) System.out.println(); System.out.print(Placei); System.out.println(); boolean Prem_Modify(int Layer,int room)/Layer当前需要移动的/控编号,room,可移动的上线boolean SetMonitor(int Demolition,int Set)/设置监控置,/Demolition拆除,Set安装 for(i = 0; i < m; i+) for(j = 0; j < n; j+) if(Matrixij = 0) return false; return true; 五、问题实例及算法运算步骤设陈列馆由m*n个陈列室组成,因为不存在重复监视，所以很多情况下都无解，我们采用的做法是根据m和n的值进行分类讨论。首先，先比较m、n大小，使m始终大于n，方面程序书写。分三种情况讨论： n1 这时可以直接写出最优解： 当m mod 31时，将哨位置于（1，3k1）； 当m mod 30或2时，将哨位置于（2，3k2），其中k0、1、m/3。 n2 这种情形下必须2端分别设置2个哨位，他们各监视三个陈列室。那么当m为偶数时问题就无解了。 当m为奇数时，将哨位分别至于（1，4k3）和（2，4k1），k0、1、m/4。 n>2 容易验证 当n3，m3和n3，m4时无解，n4，m4有解。 设置哨位时，允许在的n1行和m1列设置哨位，但不要求的第n1行和m1列陈列室受到监视，那么当n>=3且m>=5时在不重复监视下有解那么n3，m5的不可重复监视问题一定有解。但是通过验证n3，m5的不可重复监视哨位设置问题无解，那么当n>=3且m>=5时在不重复监视下无解。 通过以上讨论就将所有情况分析完全了，简单写一个包含多个条件判断的程序就可以实现该算法。 4*4矩阵相应的一维数组就是array16一共16个空间，转换成矩阵坐标也比较简单如在array数组中坐标array8则对应的矩阵坐标是Matrix8%48/4所以完全可以用一维数组来替代矩阵；再根据一维数组来计算所有安置的可能情况如2*3矩阵共6个空间，假如我要在6个空间安置3个监控则相当于离散数学中组合的概念即C(6,3) = 20。六、算法运行截图 七、算法复杂度分析 分支限界法是另一种系统地搜索空间的方法，与回溯法的主要区别在于对E结点的扩充方式。每个活节点仅有一次机会变成E结点。当一个结点变为E结点时，则生成从该结点移动一步即可到达的所有新结点。在生产的结点中，抛弃那些不可能导出可行解的结点，其余结点加入到活结点表，然后从表中选择一个结点作为下一个E结点。从活结点表中去除所选择的结点并进行扩充，直到找到解或活动表为空扩充才结束。该算法时间复杂度为O()。专心-专注-专业