java优先队列的世界名画陈列馆问题 算法设计与分析课程设计

内容需要下载文档才能查看 内容需要下载文档才能查看

算法设计与分析课程设计

学院：计算机科学与工程学院

班级：120608

小组成员：120608114 郑凯

120608101 蔡君君

120608116 周王帆

时间：2014-6-23

一、算法问题描述

世界名画陈列馆问题的优先队列式分支限界法。

世界名画陈列馆由m×n个排列成矩形阵列的陈列室组成。为了防止名画被盗，需要在陈列室中设置警卫机器人哨位。每个警卫机器人除了监视它所在的陈列室外，还可以监视与它所在的陈列室相邻的上、下、左、右4 个陈列室。试设计一个安排警卫机器人哨位的算法，使得名画陈列馆中每一个陈列室都在警卫机器人的监视之下，且所用的警卫机器人数最少。

二、算法设计 设计一个优先队列式分支限界法，计算警卫机器人的最佳哨位安排，使得名画陈列馆中每一个陈列室都在警卫机器人的监视之下，且所用的警卫机器人数最少。

三、数据输入和输出

数据输入：

通过图形界面输入 数据输出：

将计算出的警卫机器人数及其最佳哨位安排输出。第一行是警卫机器人数；接下来的m行中每行n个数，0 表示无哨位，1 表示哨位。

四、算法分析与步骤描述

分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在搜索问题的解空间树时，每一个活结点只有一次机会成为扩展结点，活结点一旦成为扩展结点，就一次性产生其所有儿子结点，在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃。其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。优先队列式分支限界法按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点 。

首先先说一下监控安置的策略：

基本思想是安置监控的数量由少到多的策略，然后用一维数组来记录监控的安装位置。

4*4矩阵相应的一维数组就是array[16]一共16个空间，转换成矩阵坐标也比较简单如在array数组中坐标array[8]则对应的矩阵坐标是Matrix[8%4][8/4]所以完全可以用一维数组来替代矩阵；然后根据一维数组来计算所有安置的可能情况。

如2*3矩阵共6个空间，假如我要在6个空间安置3个监控则相当于离散数学中组合的概念即C(6,3) = 20;

1.111000 2.110100 3.101100 4.011100 5.110010

6.101010 7.011010 8.100110 9.010110 10.00111

11.110001 12.101001 13.011001 14.100101 15.01010

16.001101 17.100011 18.010011 19.001011 20.000111

内容需要下载文档才能查看

因此我利用prem算法稍加修改则可得到当前状态下的所有组合,再根据该组合计算当前监控摆放的位置是否符合。

计算所有组合的数组Prem_Modify，但是在此思想上空间实在太庞大，4*4矩阵相当于计算C（16，1）+C（16，2）+C（16，3）+C（16，4） = 16+120+560+1820 所以针对以上问题采取了4种剪枝策略4种的策略所在的位置在程序中已标明，下面讲解一下4种剪枝策略。

策略一

首先1个监控可以监控5个位置，4*4矩阵一共16个房间，则最少监控数应该是4，所以C（16，1）+C（16，2）+C（16，3）直接剪掉。

策略二

下面比较麻烦点需要图文说明啦

下面的策略需要2个参数，当前监控，和上一个监控，这个可以这么理解01001坐标2可以认为是当前监控，第5个坐标是上一个监控，把着2个参数设置为now,top。

now = 6,top = 25;

则now的横坐标+2，一直遍历到top的横坐标，如果在这区间内有0则剪枝。 now的横坐标+2则到了16这个位置从此位置开始到25这行全部遍历包括,16,17,18,... ... 23,24,25;

策略三

5*5矩阵 加入当前一维数组11100 10000 00000 00000 00001

now = 6,top = 25则在now的右下角坐标和top的左上角坐标之内如果有0（监控没有触及到的地方）则剪枝,这2个坐标是12，19之间所有的房间编号12,13,14,17,18,19也就是说这6个房间如果在当前状态下为0则剪枝。

因为如果6坐标都无法触及到的地方。那么更不用指望1，2，3，4，5坐标能触及的到了，可能有些迷糊对了开请看一下C(6,3)所有解的输出过程，因为按照Prem_Modify函数的策略，在当前监控之前的所有监控的范围是不会超过当前监控的，如now监控的范围就是6-24是不会超过25的，所以此剪枝策略成立。 策略四

1000000100000000000111110

now = 20;Surplus = 2;

now是当前监控，Surplus代表在now之前的监控个数，则剩下2个监控。策略4的思想就是从当前监控和剩下的监控计算总共能监视多少房间则3*5=15；而在上述组合中10000001000000000001共20个房间，则不满足基本要求则剪枝。

五、源代码

import javax.swing.JOptionPane;

public class Sjmhss {

}

class Monitor {

int m,n; //矩阵的大小 //矩阵 //监控所放置的位置 public static void main(String[] args) { } String nn,mm; nn=JOptionPane.showInputDialog("请输入陈列馆的规格:\n n="); mm=JOptionPane.showInputDialog("m="); int m,n; n=Integer.parseInt(nn); m=Integer.parseInt(mm); Monitor M=new Monitor(m,n); char [][]Matrix; int []Place; Monitor(int m,int n){ int i,j,room,x,y; this.m = m;

this.n = n;

Matrix = new char [n][m]; for(i = 0; i < m; i++)

{ Matrix[i] = new char [n]; } room = m * n;

Place = new int [room]; for(i = 0; i < m; i++) for(j = 0; j < n; j++)

{ Matrix[i][j] = 0; } i = room / 5; if(room % 5!=0)

i++; for(; i < room; i++){

for(j = 0; j < i; Place[j++] = 1) SetMonitor(-4,j); while(j < room) Place[j++] = 0;

if(Prem_Modify(i - 1,room)) break;

for(x = 0; x < m; x++) for(y = 0; y < n; y++) Matrix[x][y] = 0; //i是在此矩阵内所需要的最少监控数量//剪枝策略1 //-4表示没有监控需要拆除 //将房间清零