博物馆守卫问题

发表于 | 分类于 |
字数统计: 1.1k | 阅读时长 ≈ 5

博物馆守卫问题/世界名画陈列馆问题

在某博物馆中摆放了非常重要的文物，为了节省人力，该博物馆专门购买了警卫机器人来看管这些文物。该博物馆的房间排列整齐，房间的大小相同。每个警卫机器人能够巡查的范围除本身所在房间外，还包括其起始安放的房间的上下左右四个房间。为了减少摆放的机器人的数量，请你设计一种最佳的摆放方案，使得摆放的机器人数量最少。

输入：

输入一行，有两个整数m,n,分别表示该博物馆每行的房间数和每列的房间数。博物馆总房间数即为m*n。

输出：

输出的第一行表示需要的机器人的数量，其后m行，每行有n个元素，每个元素的值为0或1，分别表示对应的房间是否摆放机器人。0表示不摆放，1表示需要摆放。

样例输入：

4 4

样例输出：

4
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0

这题的原名叫世界名画陈列馆问题，网上找着看了下，还是有点东西的。 这种问题分为，可重复坚守和不可重复坚守两类。 首先看看可重复坚守。

下面这种方法是分支限定法，这种方法复杂度太高。

思路：找到一个未被监视的格子[i][j]则想要[i][j]被监视的话，我们可以在[i][j],[i-1][j],[i+1][j],[i][j-1],[i][j+1]这五个位置放置机器人，然后就更具界限函数放入有限队列对于每个状态继续找空位放置就行，中间需要根据约束条件和目标函数限界进行剪枝。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
int n,m,f[5][2]={{0,0},{0,1},{0,-1},{1,0},{-1,0}}; //自己本身+上下左右 
int anx[30][30],ans; //最优结果 ans-警卫个数 anx-警卫位置 
 
struct Node{
	int pu[30][30];//pu-警卫位置 
	int spy[30][30]; //spy-被监视的展柜位置
	int i,j,k,t; //(i,j)为当前坐标 k-警卫数 t-被监视的展柜个数 
};
 
struct cmp{ //重写比较函数
    bool operator() (Node a, Node b)
    {
        return a.t > b.t; //小顶堆
    }
};
//priority_queue<Node> q; //优先队列 
priority_queue<Node, vector<Node>, cmp> q;
Node init(Node node){
	memset(node.pu,0,sizeof(node.pu)); 
	memset(node.spy,0,sizeof(node.spy)); 
	node.i=1;node.j=1;
	node.k=0;node.t=0;
	for(int i=0;i<=n+1;i++)node.spy[i][0]=node.spy[i][m+1]=1;
	for(int i=0;i<=m+1;i++)node.spy[0][i]=node.spy[n+1][i]=1;
	return node;
}
void puta(Node p,int x,int y){
	if(p.pu[x][y]) return;
	Node node;
	node=init(node);
	node.i=p.i;
	node.j=p.j;
	node.k=p.k+1;
	node.t=p.t;
	memcpy(node.pu, p.pu, sizeof(p.pu));
	memcpy(node.spy, p.spy, sizeof(p.spy));
	node.pu[x][y]=1;
	for(int d=0;d<5;d++){
        int xx=x+f[d][0];
        int yy=y+f[d][1];
        node.spy[xx][yy]++;
        if(node.spy[xx][yy]==1) {
			node.t++;
		}
    }
    while(node.i<=n&&node.spy[node.i][node.j]){ //已放置的不再被搜索
		node.j++;
		if(node.j>m)node.i++,node.j=1; //换行 
	}
	q.push(node);
	return;
}
int main(){
	scanf("%d%d",&n,&m);
	ans=n*m/3+2;
	Node node;
	node=init(node);
	q.push(node);
	while(!q.empty()){//队列非空 
        Node p=q.top();
        q.pop();
        if(p.t>=n*m){
        	if(p.k<ans){
	        	ans=p.k;
				memcpy(anx, p.pu, sizeof(p.pu)); //把put内容复制给anx 
	        }	
        }
        else{
			if(p.i<n) puta(p,p.i+1,p.j);
			if((p.i==n&&p.j==m)||p.spy[p.i][p.j+1]==0) puta(p,p.i,p.j);
			if(p.j<m&&(p.spy[p.i][p.j+1]==0||p.spy[p.i][p.j+2]==0)) puta(p,p.i,p.j+1);
        }
        	
    }
	printf("%d\n",ans);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)
			printf("%d ",anx[i][j]);
        printf("\n");
	}	
}

其它的后面有空再补。

目标函数：min robot c>=mn , 使用最小的机器人监视完mn的矩阵。
目标函数的界限：（mn/3）+1 ，最多使用（mn）/3+1个机器人就能够完全监视。
约束条件：robot[i][j]==0 没有放置机器人
限界函数：robot+(mn-c)/5 最少一共需要robot+(mn-c)/5个机器人就能够完全监视完。

0%