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

本文主要是介绍算法设计与分析:世界名画陈列馆问题(可重复监视) (回溯法 分支限界法),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

世界名画陈列馆问题

Description:

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

使得名画陈列馆中每一个陈列室都在警卫机器人的监视之下,且所用的警卫机器人数最少。

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

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

剪枝策略:

  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");}	
}

 

这篇关于算法设计与分析:世界名画陈列馆问题(可重复监视) (回溯法 分支限界法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/858641

相关文章

Spring Boot中JSON数值溢出问题从报错到优雅解决办法

《SpringBoot中JSON数值溢出问题从报错到优雅解决办法》:本文主要介绍SpringBoot中JSON数值溢出问题从报错到优雅的解决办法,通过修改字段类型为Long、添加全局异常处理和... 目录一、问题背景:为什么我的接口突然报错了?二、为什么会发生这个错误?1. Java 数据类型的“容量”限制

关于MongoDB图片URL存储异常问题以及解决

《关于MongoDB图片URL存储异常问题以及解决》:本文主要介绍关于MongoDB图片URL存储异常问题以及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录MongoDB图片URL存储异常问题项目场景问题描述原因分析解决方案预防措施js总结MongoDB图

SpringBoot项目中报错The field screenShot exceeds its maximum permitted size of 1048576 bytes.的问题及解决

《SpringBoot项目中报错ThefieldscreenShotexceedsitsmaximumpermittedsizeof1048576bytes.的问题及解决》这篇文章... 目录项目场景问题描述原因分析解决方案总结项目场景javascript提示:项目相关背景:项目场景:基于Spring

解决Maven项目idea找不到本地仓库jar包问题以及使用mvn install:install-file

《解决Maven项目idea找不到本地仓库jar包问题以及使用mvninstall:install-file》:本文主要介绍解决Maven项目idea找不到本地仓库jar包问题以及使用mvnin... 目录Maven项目idea找不到本地仓库jar包以及使用mvn install:install-file基

MySQL重复数据处理的七种高效方法

《MySQL重复数据处理的七种高效方法》你是不是也曾遇到过这样的烦恼:明明系统测试时一切正常,上线后却频频出现重复数据,大批量导数据时,总有那么几条不听话的记录导致整个事务莫名回滚,今天,我就跟大家分... 目录1. 重复数据插入问题分析1.1 问题本质1.2 常见场景图2. 基础解决方案:使用异常捕获3.

usb接口驱动异常问题常用解决方案

《usb接口驱动异常问题常用解决方案》当遇到USB接口驱动异常时,可以通过多种方法来解决,其中主要就包括重装USB控制器、禁用USB选择性暂停设置、更新或安装新的主板驱动等... usb接口驱动异常怎么办,USB接口驱动异常是常见问题,通常由驱动损坏、系统更新冲突、硬件故障或电源管理设置导致。以下是常用解决

Mysql如何解决死锁问题

《Mysql如何解决死锁问题》:本文主要介绍Mysql如何解决死锁问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录【一】mysql中锁分类和加锁情况【1】按锁的粒度分类全局锁表级锁行级锁【2】按锁的模式分类【二】加锁方式的影响因素【三】Mysql的死锁情况【1

SpringBoot内嵌Tomcat临时目录问题及解决

《SpringBoot内嵌Tomcat临时目录问题及解决》:本文主要介绍SpringBoot内嵌Tomcat临时目录问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录SprinjavascriptgBoot内嵌Tomcat临时目录问题1.背景2.方案3.代码中配置t

SpringBoot使用GZIP压缩反回数据问题

《SpringBoot使用GZIP压缩反回数据问题》:本文主要介绍SpringBoot使用GZIP压缩反回数据问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot使用GZIP压缩反回数据1、初识gzip2、gzip是什么,可以干什么?3、Spr

Java程序进程起来了但是不打印日志的原因分析

《Java程序进程起来了但是不打印日志的原因分析》:本文主要介绍Java程序进程起来了但是不打印日志的原因分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java程序进程起来了但是不打印日志的原因1、日志配置问题2、日志文件权限问题3、日志文件路径问题4、程序