文档介绍：算法设计与分析课程设计题目:世界名画陈列馆问题(分支限界法)专业:网络工程班级:学号:姓名:计算机工程系2012年11月16日一、算法问题描述世界名画陈列馆问题的优先队列式分支限界法。世界名画陈列馆由m×n个排列成矩形阵列的陈列室组成。为了防止名画被盗,需要在陈列室中设置警卫机器人哨位。每个警卫机器人除了监视它所在的陈列室外,还可以监视与它所在的陈列室相邻的上、下、左、右4个陈列室。试设计一个安排警卫机器人哨位的算法,使得名画陈列馆中每一个陈列室都在警卫机器人的监视之下,且所用的警卫机器人数最少。二、算法问题形式化表示本问题的m*n的陈列室的解可表示如下图所示。其中1代表在该陈列室设置警卫机器人哨位,0表示未在该陈列室设置警卫机器人哨位。01001001000100101000010000100001010010000001001010100101m*n陈列室的可能解最为极端的情况是所有元素的值为1。那什么情况下是最优解呢?就是设置警卫机器人哨位数最少即为最优。因为每个矩阵中的值都可以为1或0,有m*n个元素,有种可能满足约束条件的矩阵,要从种可能中遍历找到满足约束条件的1的个数最小的矩阵。由此可见这是一个NP问题。这里的约束条件就是当某一个元素为1时,相邻的4个方向上的元素值可以为0。三、期望输入与输出输入:第一行有2个正整数m和n(1≤m,n≤20)输出:将计算出的警卫机器人数及其最佳哨位安排输出。第一行是警卫机器人数;接下来的m行中每行n个数,0表示无哨位,1表示哨位。样例输入:44样例输出:40010100000010100四、算法分析与步骤描述分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。与回溯法不同,在搜索问题的解空间树时,每一个活结点只有一次机会成为扩展结点,活结点一旦成为扩展结点,就一次性产生其所有儿子结点,在这些儿子结点中,那些导致不可行解或导致非最优解的儿子结点被舍弃。其余儿子结点被加入活结点表中。此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。有两种常用的方法可用来选择下一个E-结点:(1)先进先出(FIFO)即从活结点表中取出结点的顺序与加入结点的顺序相同,因此活节点表的性质与队列相同。(2)最小耗费或最大收益法在这种模式中,每个结点都有一个对应的耗费或收益。如果查找一个具有最小耗费的解,则活节点表可以用最小堆来建立,下一个E-结点就是具有最小耗费的活结点;如果希望搜索一个具有最大收益的解,则可用最大堆来构造活结点表,下一个E-结点是具有最大收益的活结点。它采用自底向上的顺序,找到边界条件,将整个问题的最优解与问题的局部最优解用递推的等式联系起来,把边界条件代入递推等式逐步求得最优解。classMonitor{ intm,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) (); (Place[i]); }