世界名画陈列馆问题(回溯法).doc
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《世界名画陈列馆问题(回溯法).doc》由会员分享,可在线阅读,更多相关《世界名画陈列馆问题(回溯法).doc(21页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date世界名画陈列馆问题(回溯法)世界名画陈列馆问题(回溯法)算法设计与分析课程设计题目: 世界名画陈列馆问题(回溯法) 专业: 班级: 学号: 姓名: 计算机工程系 2012年 11 月 16 日一、算法问题描述世界名画陈列馆问题。世界名画陈列馆由mn个排列成矩形阵列的陈列室组成。为了防止名画被盗,需要在陈列室中设置警卫机器人哨位。每个警卫机器人除了监视它所在的陈列室外,
2、还可以监视与它所在的陈列室相邻的上、下、左、右4 个陈列室。试设计一个安排警卫机器人哨位的算法,使得名画陈列馆中每一个陈列室都在警卫机器人的监视之下,且所用的警卫机器人数最少。二、算法问题形式化表示本问题的m*n的陈列室的解可表示如下图所示。其中1代表在该陈列室设置警卫机器人哨位,0表示未在该陈列室设置警卫机器人哨位。01001001000100101000010000100001010010000001001010100101 m*n陈列室的可能解 最为极端的情况是所有元素的值为1。那什么情况下是最优解呢?就是设置警卫机器人哨位数最少即为最优。因为每个矩阵中的值都可以为1或0,有m*n个元素
3、,有种可能满足约束条件的矩阵,要从种可能中遍历找到满足约束条件的1的个数最小的矩阵。由此可见这是一个NP问题。这里的约束条件就是当某一个元素为1时,相邻的4个方向上的元素值可以为0。三、期望输入与输出输入:第一行有2 个正整数m和n (1m,n20)输出:将计算出的警卫机器人数及其最佳哨位安排输出。第一行是警卫机器人数;接下来的m行中每行n个数,0 表示无哨位,1 表示哨位。样例输入:4 4样例输出:40 0 1 01 0 0 00 0 0 10 1 0 0四、算法分析与步骤描述 从上到下、从左到右的顺序依次考查每一个陈列室设置警卫机器人哨位的情况,以及该陈列室受到监视的情况,用i,j表示陈列
![世界名画陈列馆问题(回溯法).doc_第1页](https://file2.taowenge.com/FileRoot3/2022-6/19/00440fab-634d-443f-8912-9c31890136cc/00440fab-634d-443f-8912-9c31890136cc1.gif)
![世界名画陈列馆问题(回溯法).doc_第2页](https://file2.taowenge.com/FileRoot3/2022-6/19/00440fab-634d-443f-8912-9c31890136cc/00440fab-634d-443f-8912-9c31890136cc2.gif)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 世界 名画 陈列馆 问题 回溯
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内