世界名画陈列馆问题(分支限界法)(共8页).doc

精选优质文档-倾情为你奉上算法设计与分析课程设计题目： 世界名画陈列馆问题(分支限界法) 专业： 网络工程 班级： 学号： 姓名： 计算机工程系 2012年 11 月 16 日一、算法问题描述世界名画陈列馆问题的优先队列式分支限界法。世界名画陈列馆由mn个排列成矩形阵列的陈列室组成。为了防止名画被盗，需要在陈列室中设置警卫机器人哨位。每个警卫机器人除了监视它所在的陈列室外，还可以监视与它所在的陈列室相邻的上、下、左、右4 个陈列室。试设计一个安排警卫机器人哨位的算法，使得名画陈列馆中每一个陈列室都在警卫机器人的监视之下，且所用的警卫机器人数最少。二、算法问题形式化表示本问题的m*n的陈列室的解可表示如下图所示。其中1代表在该陈列室设置警卫机器人哨位，0表示未在该陈列室