5.12汶川大地震使震区地面交通和通讯系统严重瘫痪.救灾指挥部紧急派出多支小分队,到各个指定区域执行搜索任务,以确定需要救助的人员的准确位置.在其它场合也常有类似的搜索任务.在这

Question

5.12汶川大地震使震区地面交通和通讯系统严重瘫痪.救灾指挥部紧急派出多支小分队,到各个指定区域执行搜索任务,以确定需要救助的人员的准确位置.在其它场合也常有类似的搜索任务.在这种紧急情况下需要解决的重要问题之一是：制定搜索队伍的行进路线,对预定区域进行快速的全面搜索.通常,每个搜索人员都带有GPS定位仪、步话机以及食物和生活用品等装备.队伍中还有一定数量的卫星电话.GPS可以让搜索人员知道自己的方位.步话机可以相互进行通讯.卫星电话用来向指挥部报告搜索情况.
下面是一个简化的搜索问题.有一个平地矩形目标区域,大小为11200米×7200米,需要进行全境搜索.假设：出发点在区域中心；搜索完成后需要进行集结,集结点（结束点）在左侧短边中点；每个人搜索时的可探测半径为20米,搜索时平均行进速度为0.6米/秒；不需搜索而只是行进时,平均速度为1.2米/秒.每个人带有GPS定位仪、步话机,步话机通讯半径为1000米.搜索队伍若干人为一组,有一个组长,组长还拥有卫星电话.每个人搜索到目标,需要用步话机及时向组长报告,组长用卫星电话向指挥部报告搜索的最新结果.
现在有如下问题需要解决：
1．假定有一支20人一组的搜索队伍,拥有1台卫星电话.请设计一种你认为耗时最短的搜索方式.按照你的方式,搜索完整个区域的时间是多少?能否在48小时内完成搜索任务?如果不能完成,需要增加到多少人才可以完成.
2．为了加快速度,搜索队伍有50人,拥有3台卫星电话,分成3组进行搜索.每组可独立将搜索情况报告给指挥部门.请设计一种你认为耗时最短的搜索方式.按照你的搜索方式,搜索完整个区域的时间是多少?

Answer 1

要求严格意义下的最优解几乎是不可能的,只能求满意解.可以先做一个假设：在搜索过程中所有人排成一条直线,这样问题就相当于一个搜索半径400的“人”进行搜索,然后把整个地区划成28*18个400m见方的网格,再假设搜索队...