世界名画陈列馆问题
Description:
世界名画陈列馆由m´n个排列成矩形阵列的陈列室组成。为了防止名画被盗,需要在陈列室中设置警卫机器人哨位。每个警卫机器人除了监视它所在的陈列室外,还可以监视与它所在的陈列室相邻的上、下、左、右4 个陈列室。试设计一个安排警卫机器人哨位的算法,
使得名画陈列馆中每一个陈列室都在警卫机器人的监视之下,且所用的警卫机器人数最少。
设计一个优先队列式分支限界法,计算警卫机器人的最佳哨位安排,使得名画陈列馆中每一个陈列室都在警卫机器人的监视之下,且所用的警卫机器人数最少。
Input:
第一行有2 个正整数m和n (1≤m,n≤20)
Output:
将计算出的警卫机器人数及其最佳哨位安排输出。第一行是警卫机器人数;接下来的m行中每行n个数,0 表示无哨位,1 表示哨位。
Sample Input:
4 4
Copy
Sample Output:
4
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0
!!!在各大OJ都提交了,均为超时,不是AC代码。仅作为学习参考。!!!
当y[i][j+1]==1时,以q为根的子树的解,不优于以p为根的子树的解,
当y[i][j+1]==1且y[i][j+2]==1时,以r为根的子树的解,不优于以p为根的子树的解。
搜索时应按照p、q、r或p、r、q的顺序来扩展结点。
剪枝策略:
- 放置的机器人个数不会超过n*m/3+1个(按每个机器人仅辐射左右或上下考虑,堆叠这样的小长条可得)。以n*m/3+2为初始最优值,当放置的个数超过当前最优值时,剪去。
- (当前最优值ans-当前已放置个数p)5(最多能增加5个监视点)。如果小于未监视的格点数(nm-spys),则一定达不到比当前最优值更好的情况,剪去。
回溯法:
#include <stdio.h>
#include <string.h>
int n,m,f[5][2]={{0,0},{0,1},{0,-1},{1,0},{-1,0}}; //自己本身+上下左右
int anx[30][30],ans; //最优结果 ans-警卫个数 anx-警卫位置
int put[30][30],p; //暂时存储 p-警卫个数 put-警卫位置
int spy[30][30],spys; //spy-被监视的展柜位置 spys-被监视的展柜个数
void puta(int x,int y,int p,int q);
void search(int i,int j)
{
if(p>=ans) return;
while(i<=n&&spy[i][j]) //已放置的不再被搜索
{
j++;
if(j>m) i++,j=1; //换行
}
if(i>n) //更新答案
{
ans=p;
memcpy(anx, put, sizeof(put)); //把put内容复制给anx
return;
}
//剪枝
if((ans-p)*5<=n*m-spys) return;
if(i<n) puta(i+1,j,i,j);
if(spy[i][j+1]==0) puta(i,j,i,j);
if(j<m&&(spy[i][j+1]==0||spy[i][j+2]==0)) puta(i,j+1,i,j);
}
void puta(int x,int y,int c,int d)
{
put[x][y]=1;
p++;
for(int i=0;i<5;i++)
{
int xx=x+f[i][0];
int yy=y+f[i][1];
spy[xx][yy]++;
if(spy[xx][yy]==1) spys++;
}
search(c,d+1);
put[x][y] = 0;
p--;
for(int i=0;i<5;i++)
{
int xx=x+f[i][0];
int yy=y+f[i][1];
spy[xx][yy]--;
if(spy[xx][yy]==0) spys--;
}
}
int main()
{
scanf("%d%d",&n,&m);
ans=n*m/3+2;
p=0;
//设置边界
for(int i=0;i<=n+1;i++)
spy[i][0]=spy[i][m+1]=1;
for(int i=0;i<=m+1;i++)
spy[0][i]=spy[n+1][i]=1;
search(1,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");
}
}
分支限界法:
#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)
{
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");
}
}
版权归原作者 TheWise_lzy 所有, 如有侵权,请联系我们删除。