警察救人质问题分析.doc

警察救人质问题分析.doc警察救人质问题分析劫匪绑架C城件富,勒索天价赎金,并扬言只耍看见警察就撕票。然而魔高一尺、道高—丈。警方准备用新式武器对付这帮匪徒。这个新式武器使警察能在其可视范I韦I内发现障碍物后方的日标,并准确击屮日标。警方卧底侦获了匪徒企图转移人质的时间和路线,一队特警待命执行抓捕行动。你的任务是根据警方提供的地图为特警制定行动方案。在输入信息中,你将获得匪徒的逃跑信息和城市地图,地图为简化的格子形式(长宽最人值为40格),每个格子代表一个地点,格子为单位边长的正方形。匪徒或特警在每个单位时间移动1个格子。若匪徒发现特警就会杀死人质,则任务失败;若匪徒到达其日的地,则任务失败;输入:输入中包含多个样例,每个样例的首行有两个整数和一个浮点数分别为地图的高度R、宽度C和最佳标准权重alpha0后跟R行字符,每行C个数字,为地图信息。不同的数字有不同的含义:0为道路或空地,1为匪徒逃跑的起点,2为特警的待命地点,4为障碍物(如房屋或河流),9为匪徒的日的地。每个样例的最后一行的字符串代表匪徒转移人质的行动路线,从左至右每个字符代表单位时间内匪徒将依次采取的行动,其屮u代表向上走一格d代表向下走一格r代表向右走一格1代表向左走一格s代表原地停留—•次。已知匪徙的可视范囤为以匪徙所在格子为中心的边长为7个格子的正方形区域,特警的可视范围为以特警所在格子为屮心的边长为5个格子的正方形区域。匪徒一旦发现特警将杀死人质,而特警若发现匪徒则能即刻(在肖前单位时间内)开枪将其缉拿归案。如果双方所在格子的小心点(格子的对角线交点)连线与障碍物格子相交或相切(连线与障碍物格子有交点),则匪徒无法发现特警,但装备了新式武器的特警可以发现并击小匪徒。输出:针对每个输入样例,如果特警无法成功缉拿匪徒,则输出”bil”:否则输出特警的最佳行动策略开销cost(小数点后保留3位有效数字)。最佳行动策略的衡暈标准是使开销cost最小,cost的定义为:cost=alpha*Nstep+(1-alpha)*T0其中alpha为最佳标准权重,Nstep和T分别为特警自第一个单位时间开始到成功开枪缉拿匪徒所移动的格子数和消耗的单位时间数。特警在单位时间内可能采取的行动包括:向上走一格、向下走i格、向右走i格、向左走一格、原地停留一次或开枪缉拿。每个样例的输出占一行。示例::1、 警察、劫匪每个冋合做一个动作,劫匪的动作则是延周定的输入方向移动,而警察的动作可以是5个方向走一步(上、下、左、右、原地);2、 冋合是育限的,冋合的最人次数,为劫匪从出发地方格到日的地方格移动的步骤数,也就是劫匪行动路线的字符串长度;3、 在每个冋合内,警察执行移动以前,要判断在视线范围的方格内能否发现劫匪,一旦发现劫匪,警察解救人质,警察赢,而劫匪在执行移动以前,要判断在视线范围的方格内能否发现警察,如果在视线范围内令警察,而劫匪和警察之间的连线上没右障碍物,则劫匪撕票,警察输;4、 冋合数有限制,如果时间到了最后一个冋合,劫匪能按照行动路线到达终点,警察失败,所以警察必须在最后一个冋合的前-•个冋合以内发现劫匪才能成功;5、 警察的视野范围和劫匪的视野范I韦I不一样,劫匪是7*7个格子,而警察是5*5个格子;6、 如果劫匪出现在警察的视线内,不管警察与劫匪的连线有没有障碍物,警察都能解救人质,警察赢,而如果警察出现在劫匪的视线内,但警察与劫匪的连线没有障碍物,则劫匪撕票,警察输。分析难点:1、 每一个冋合开始以前,都要做相应的判断,各自都是什么判断?(三个判断:劫匪有没有到达终点、劫匪会不会撕票、警察能否干掉劫匪)2、 每个冋合屮,劫匪的行动方向是L1知的,而警察却有5个方向(上、下、左、右、原地)选择,如何处理?(可以考虑冋溯法)3、 如何判断哪些方格处于警察与劫匪的连线上?(警察与劫匪所在的两点可以确定一个直线方程,理论上,如果某个方格的屮心点距离这个直线方程的距离小于或等于sq讥(2)/2,则可以认为在这条连线上。那么如何考虑精度问题?用放人法。)4、 这是典型的NP问题,如果用冋溯法,如何明枝?(注意cost会随着冋合数的递增而增加,每一个冋合,先计算出当前的cost,如果人于或者等于以前的搜索过程屮找到的最小代价,则剪枝)5、 对于一•些特殊情况,可以直接判断无解,哪些情况?(1、劫匪行动路线屮距离障碍的最近距离也人于了警察的视线范I韦I,则无解;2、警察在当前的最人活动范围内不存在障碍物,也无解)6、 警察有5个方向(上、下、左、