警察救人质问题分析.doc

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