算法设计与分析：世界名画陈列馆问题（可重复监视） (回溯法 & 分支限界法)

r囧r小猫 2022-12-29 04:45 195阅读 0赞

# 世界名画陈列馆问题 #

## 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代码。仅作为学习参考。！！！ ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RoZVdpc2VfbHp5_size_16_color_FFFFFF_t_70][]

当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的顺序来扩展结点。

### 剪枝策略: ###

1.  放置的机器人个数不会超过n\**m/3+1个(按每个机器人仅辐射左右或上下考虑，堆叠这样的小长条可得*)。以n\*m/3+2为初始最优值，当放置的个数超过当前最优值时，剪去。
2.  (当前最优值ans-当前已放置个数p)\*5（最多能增加5个监视点）。如果小于未监视的格点数（n\*m-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");
    	}	
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RoZVdpc2VfbHp5_size_16_color_FFFFFF_t_70]: /images/20221120/3491629d5c264b91bc210f3f215407b2.png