世界名画陈列馆问题(分支限界法)

算法设计与分析课程设计题目：世界名画陈列馆问题(分支限界法)专业：网络工程班级：学号：姓名：计算机工程系2012年11月16日一、算法问题描述世界名画陈列馆问题的优先队列式分支限界法。世界名画陈列馆由m×n个排列成矩形阵列的陈列室组成。为了防止名画被盗，需要在陈列室中设置警卫机器人哨位。每个警卫机器人除了监视它所在的陈列室外，还可以监视与它所在的陈列室相邻的上、下、左、右4个陈列室。试设计一个安排警卫机器人哨位的算法，使得名画陈列馆中每一个陈列室都在警卫机器人的监视之下，且所用的警卫机器人数最少。二、算法问题形式化表示本问题的m*n的陈列室的解可表示如下图所示。其中1代表在该陈列室设置警卫机器人哨位，0表示未在该陈列室设置警卫机器人哨位。01001001000100101000010000100001010010000001001010100101m*n陈列室的可能解最为极端的情况是所有元素的值为1。那什么情况下是最优解呢？就是设置警卫机器人哨位数最少即为最优。因为每个矩阵中的值都可以为1或0，有m*n个元素，有nm*2种可能满足约束条件的矩阵，要从nm*2种可能中遍历找到满足约束条件的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;iroom;i++){//输出矩阵if(i!=0&&i%n==0)System.out.println();System.out.print(Place[i]);}System.out.println();booleanPrem_Modify(intLayer,introom){}//Layer当前需要移动的//控编号,room,可移动的上线booleanSetMonitor(intDemolition,intSet){//设置监控置,//Demolition拆除,Set安装for(i=0;im;i++)for(j=0;jn;j++)if(Matrix[i][j]==0)returnfalse;returntrue;}}五、问题实例及算法运算步骤设陈列馆由m*n个陈列室组成,因为不存在重复监视，所以很多情况下都无解，我们采用的做法是根据m和n的值进行分类讨论。首先，先比较m、n大小，使m始终大于n，方面程序书写。分三种情况讨论：n＝1这时可以直接写出最优解：当mmod3＝1时，将哨位置于（1，3k＋1）；当mmod3＝0或2时，将哨位置于（2，3k＋2），其中k＝0、1、…、m/3。n＝2这种情形下必须2端分别设置2个哨位，他们各监视三个陈列室。那么当m为偶数时问题就无解了。当m为奇数时，将哨位分别至于（1，4k＋3）和（2，4k＋1），k＝0、1、…、m/4。n2容易验证当n＝3，m＝3和n＝3，m＝4时无解，n＝4，m＝4有解。设置哨位时，允许在的n＋1行和m＋1列设置哨位，但不要求的第n＋1行和m＋1列陈列室受到监视，那么当n=3且m=5时在不重复监视下有解那么n＝3，m＝5的不可重复监视问题一定有解。但是通过验证n＝3，m＝5的不可重复监视哨位设置问题无解，那么当n=3且m=5时在不重复监视下无解。通过以上讨论就将所有情况分析完全了，简单写一个包含多个条件判断的程序就可以实现该算法。4*4矩阵相应的一维数组就是array[16]一共16个空间，转换成矩阵坐标也比较简单如在array数组中坐标array[8]则对应的矩阵坐标是Matrix[8%4][8/4]所以完全可以用一维数组来替代矩阵；再根据一维数组来计算所有安置的可能情况如2*3矩阵共6个空间，假如我要在6个空间安置3个监控则相当于离散数学中组合的概念即C(6,3)=20。六、算法运行截图七、算法复杂度分析分支限界法是另一种系统地搜索空间的方法，与回溯法的主要区别在于对E结点的扩充方式。每个活节点仅有一次机会变成E结点。当一个结点变为E结点时，则生成从该结点移动一步即可到达的所有新结点。在生产的结点中，抛弃那些不可能导出可行解的结点，其余结点加入到活结点表，然后从表中选择一个结点作为下一个E结点。从活结点表中去除所选择的结点并进行扩充，直到找到解或活动表为空扩充才结束。该算法时间复杂度为O(n2)。世界很大，风景很美；人生苦短，不要让自己在阴影里蜷缩和爬行。应该淡然镇定，用心灵的阳光驱散迷雾，走出阴影，微笑而行，勇敢地走出自己人生的风景！人们在成长与成功的路途中，往往由于心理的阴影，导致两种不同的结果：有些人可能会因生活的不顺畅怨天尤人，烦恼重重，精神萎靡不振，人生黯淡无光；有人可能会在逆境中顽强的拼搏和成长，历练出若谷的胸怀，搏取到骄人的成就。只有在磨难中成长和成功的人们，才更懂得生活，才更能体味出世态的炎凉甘苦，才更能闯出精彩的人生。阴影是人生的一部分。在人生的阳光背后，有阴影不一定都是坏事。我们应该感激伤害过自己的人，是他们让你的人生与众不同；感激为难你的人，是他们磨炼了你的心志；感激绊倒你的人，是他们强化了你的双腿；感激欺骗你的人，是他们增强了你的智慧；感激蔑视你的人，是他们警醒了你的自尊；感激遗弃你的人，是他们教会了你该独立。人生若要走向成功，有好多的阴影需要消除。必须消除自卑的阴影：自卑，是人生的一大阴影。我们要以一种平和的心态对待自己。不要总把注意力始终停留在自己的短处上，你停留的时间越长，自卑心就越重，灰色的阴影就越多、越浓。必须消除受挫的阴影：真正的强者，不但要学会在顺境中稳步前行，更重要的是学会消除逆境中的阴影。真正的强者，不会因幸运而沾沾自喜，固步自封，也不会因厄运而一蹶不振，昏昏庸庸，而应该从逆境中找到光亮，时时校准自己前进的目标和方向，一往直前，从从容容。必须消除贪婪的阴影：知足者常乐，不知足者能进取，知足与不知足都蕴涵着辩证法的哲理。贪婪的人永不知足，寡欲的人一身轻松。人世间，凡事都想求全，但凡事不可能求全；凡事都应知足，因为只有知足，才能开开心心，才能挣脱贪婪的缰绳。假如过于贪婪，只会加重人们的心理负担，使自己永远处于无尽的烦恼之中！必须消除无事生非的阴影：本来已经身家百万，你却奢求千万；本来已经儿女双全，你却奢求千金一对，成双儿男；本来已经事业有成，你还依然好高骛远。你贪欲无尽，你奢求无限；本是众人眼中的佼佼者，你却忧郁连连；本来圆圆满满，你却无事生非，庸人自扰，画牢自钻圈。你为何不能快快乐乐，阳光一点？！四季更替，不可改变；花开花落，顺其自然；月缺月圆，规律使然。若遇人生之阴影，要勇敢面对，积极消除。拥抱阳光，微笑向暖，你一定会快乐无限！著名专栏作家哈理斯和朋友在报摊上买报纸，朋友礼貌地对报贩说了声“谢谢”,但报贩却冷口冷脸，没发一言。“这家伙态度很差，是不是？”他们继续前行时，哈理斯问道。“他每天都是这样的。”朋友说。“那么你为什么还是对他那么客气？”哈理斯问。朋友答：“为什么我要让他决定我的行为？”每个人心中都有把“快乐的钥匙”,但我们却常在不知不觉中把它交给别人掌管。一位女士抱怨道：“我活得很不快乐，因为先生常出差不在家。”她把快乐的钥匙放在先生手里。一位妈妈说：“我的孩子不听话，让我很生气！”她把钥匙交在孩子手中。男人可能说：“上司不赏识我，所以我情绪低落。”这把快乐钥匙又被塞在老板手里。婆婆说：“我的媳妇不孝顺，我真命苦！”这些人都做了相同的决定，就是让别人来控制自己的心情。当我们容许别人掌控我们的情绪时，我们便觉得自己是受害者，于是，抱怨与愤怒成为我们唯一的选择。我们开始怪罪他人，并且传达一个信息：“我这样痛苦，都是你造成的，你要为我的痛苦负责！”这样的人使别人不喜欢接近，甚至望而生畏。一个成熟的人能握住自己快乐的钥匙，他不期待别人使他快乐，反而能将自己的快乐与幸福带给周围的人。生活，就是一种苦苦撑下去的历程，没有谁的生活一帆风顺，也没有谁的红尘一直岁月静好，有的是一路坎坷，一路磨难，和一路的成长。只是当你撑不下去的时候，请保留内心最真实的温柔。想起看过的一幅漫画，一个人从十楼跳下，当她经过每一层邻居的窗口，她看见了每一家、每个人不为人知的那一面，也看见了别人的不易和自己生活的幸福。可是，当她坠地，她又成了所有不幸之人深思自己幸福的模板。只是她的幸福已经完结，别人照样经历着各种生活的不堪和不幸。这个世界就是这样，你以为的幸福从来都是在别人的眼睛里，而每个人真正的幸福或者不幸，往往都藏在心里。或许，我们在外人面前光鲜靓丽，却在某个时候，会被一句话或一首歌打动了心扉，触动了自己内心深处的柔软，让你再也控制不住情绪的波动。或许，生活的艰难在某一刻让你泪流满面，却也会让你在哭过痛过之后，擦干眼泪依旧前行。人活在这世上，没有人能够真正体会你经历了怎样的生活、心灵的折磨，他们看到的只是一个人的表面。而生活的真实，却让你不得不一边崩溃着大哭，一边拼命地活着。是的，就是活着。一个人只有经历了生死之间的纠缠和折磨，才会懂得：活着，才是一种苦苦撑下去的坚持。没有人可以帮到你，只有你自己才是自己躲雨的那个屋檐。所以最难熬的日子里，你要学会一个人扛起所有的艰辛，一个人去面对生活所有的刁难，哪怕路途遥远，哪怕是一个个漆黑的长夜，你也要咬紧牙关地走下去，不负初心，不忘自己最初的本真……你知道吗？有时候当你以为生活走到尽头的时候，总是会峰回路转；当你孤苦无依的时候，总有一个人默默地帮助你，帮你走出生命的关口，帮你走过那些泥泞的路途。所以，千万不要放弃，只要活着，一切皆有可能。疲于奔命的时候，多想想那些比你还困难的人；情感失意的时候，多想可能会遇上的幸福，曾经得到的温暖和爱；走投无路的时候，多想到这是人生另一种方式的拐弯……人生没有重来的机会，生活却有让你重新选择活法的机缘。拨开乌云见太阳，最重要的是你要有坚持下来的信心、勇气和执着。其实，你只要有一颗坚持不懈的灵魂，你的脚下就有一片坚实的土地。那些难捱的时光，生活里过不下去的艰难，情感里滋生出来的失望，工作上无法摆脱的困顿，无论你怎样想放弃，你都要坚持走下去，走出生命的低谷，塑造出独一无二的自己。哪怕多年后提及，也要变成风轻云淡地过去。其实，人这一生的所有，都是一种坚持。坚持让自己快乐，坚持让生活变好，坚持让自己不断地提升，坚持让生命变得丰富，让心灵变得富足……X