世界名画陈列馆问题分支限界法Word文档格式.doc
《世界名画陈列馆问题分支限界法Word文档格式.doc》由会员分享，可在线阅读，更多相关《世界名画陈列馆问题分支限界法Word文档格式.doc（4页珍藏版）》请在冰点文库上搜索。
一、算法问题描述
世界名画陈列馆问题的优先队列式分支限界法。
世界名画陈列馆由m×
n个排列成矩形阵列的陈列室组成。
为了防止名画被盗，需要在陈列室中设置警卫机器人哨位。
每个警卫机器人除了监视它所在的陈列室外，还可以监视与它所在的陈列室相邻的上、下、左、右4个陈列室。
试设计一个安排警卫机器人哨位的算法，使得名画陈列馆中每一个陈列室都在警卫机器人的监视之下，且所用的警卫机器人数最少。
二、算法问题形式化表示
本问题的m*n的陈列室的解可表示如下图所示。
其中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<
room;
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;
m;
i++）
for（j=0;
j<
n;
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>
=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（）。
升级会员 