世界名画陈列馆问题分支限界法.doc
- 文档编号:1295456
- 上传时间:2023-04-30
- 格式:DOC
- 页数:4
- 大小:57KB
世界名画陈列馆问题分支限界法.doc
《世界名画陈列馆问题分支限界法.doc》由会员分享,可在线阅读,更多相关《世界名画陈列馆问题分支限界法.doc(4页珍藏版)》请在冰点文库上搜索。
算法设计与分析
课程设计
题目:
世界名画陈列馆问题(分支限界法)
专业:
网络工程
班级:
学号:
姓名:
计算机工程系
2012年11月16日
一、算法问题描述
世界名画陈列馆问题的优先队列式分支限界法。
世界名画陈列馆由m×n个排列成矩形阵列的陈列室组成。
为了防止名画被盗,需要在陈列室中设置警卫机器人哨位。
每个警卫机器人除了监视它所在的陈列室外,还可以监视与它所在的陈列室相邻的上、下、左、右4个陈列室。
试设计一个安排警卫机器人哨位的算法,使得名画陈列馆中每一个陈列室都在警卫机器人的监视之下,且所用的警卫机器人数最少。
二、算法问题形式化表示
本问题的m*n的陈列室的解可表示如下图所示。
其中1代表在该陈列室设置警卫机器人哨位,0表示未在该陈列室设置警卫机器人哨位。
0
1
0
0
1
0
0
1
0
0
0
1
0
0
1
0
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
1
0
0
1
0
0
0
0
0
0
1
0
0
1
0
1
0
1
0
0
1
0
1
m*n陈列室的可能解
最为极端的情况是所有元素的值为1。
那什么情况下是最优解呢?
就是设置警卫机器人哨位数最少即为最优。
因为每个矩阵中的值都可以为1或0,有m*n个元素,有种可能满足约束条件的矩阵,要从种可能中遍历找到满足约束条件的1的个数最小的矩阵。
由此可见这是一个NP问题。
这里的约束条件就是当某一个元素为1时,相邻的4个方向上的元素值可以为0。
三、期望输入与输出
输入:
第一行有2个正整数m和n(1≤m,n≤20)
输出:
将计算出的警卫机器人数及其最佳哨位安排输出。
第一行是警卫机器人数;接下来的m行中每行n个数,0表示无哨位,1表示哨位。
样例输入:
44
样例输出:
4
0010
1000
0001
0100
四、算法分析与步骤描述
分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。
与回溯法不同,在搜索问题的解空间树时,每一个活结点只有一次机会成为扩展结点,活结点一旦成为扩展结点,就一次性产生其所有儿子结点,在这些儿子结点中,那些导致不可行解或导致非最优解的儿子结点被舍弃。
其余儿子结点被加入活结点表中。
此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。
这个过程一直持续到找到所求的解或活结点表为空时为止。
有两种常用的方法可用来选择下一个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 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;i for(j=0;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。 n>2容易验证 当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()。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 世界 名画 陈列馆 问题 分支 限界