平地矩形区域上的地面搜索问题-论文

《平地矩形区域上的地面搜索问题-论文》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、平地矩形区域上的地面搜索问题-论文平地矩形区域上的地面搜索问题2008年5月12日汶川发生里氏8.0级特大地震，使得震区地面交通和通讯系统严重瘫痪。如何制定搜救队伍的行进路线，在最短的时间内对预定区域进行快速的全面搜索是在此紧急情况下需要解决的重要问题之一。本文旨在研究在一平地矩形区域上的地面搜索问题。在问题一中，我们首先给出了20人一组的搜索队伍,搜索完整个区域至少需要个小时这样一个有利的结论。我们先采用圆滚动模型，但会出现队员与组长联系不到的缺点；经分析，采用图论中的赋权连通图法可以改进圆滚动模型的缺点，组长在任何位置都可以联系到所有队员，搜索中不存在重叠现象，

2、且搜索用的时间最短，在赋权连通图用算法找到最小生成树，在此生成树中采用扩环策略、增环策略、换枝策略的思想，经过调整，采用拐弯、不拐弯两种搜索方法，寻找到20人一组的最佳搜索路线。按此方式，我们得到这样几个结果：(1)搜索完整个平面矩形区域所用的时间为小时。(2)在小时以内不能完成搜索任务。(3)在问题二中，我们采用第一、二组各20人，第三组10人的分组方式，给出了分组的均衡度，说明分组的均衡度很好。我们根据最小生成树分解原则进行分区域，再次采用扩环策略、增环策略、换枝策略的思想，给出了第一、二组搜索完需要的时间是，第三组搜索完需要的时间是。即50人三组搜索完整个平面

3、矩形区域需要。最后，给出了一个双层非线性规划，将其内层目标函数、约束条件构造了条件，从规划的角度分析了此模型。图论中的赋权连通图法，将图论，规划，算法有机地结合在一起。关键词：最小生成树；均衡度；规划；圆滚动模型一、问题重述1.1背景2008年5月12日汶川大地震中，震区地面交通和通讯系统严重瘫痪。大家知道救助灾民的黄金时间是72小时，能在短时间内搜索到需要救助的人员得位置，并更快的进行救助是我们的首要任务。救灾指挥部紧急派出多支小分队，到各个指定区域执行搜索任务，以确定需要救助的人员的准确位置。在这种紧急情况下需要解决的重要问题之一是：制定搜索队伍的行进路线，对预

4、定区域进行快速的全面搜索。1.2简化的搜索问题我们有一个平地矩形目标区域，需要进行全境搜索。出发点在区域中心；搜索完成后需要进行集结，集结点在左侧短边中点。每个人带有GPS定位仪、步话机。搜索队伍若干人为一组,有一个组长，组长还拥有卫星电话。每个人搜索到目标，需要用步话机及时向组长报告，组长用卫星电话向指挥部报告搜索的最新结果。1.3我们需要解决的问题（）若搜索队伍人，一组,台卫星电话。设计耗时最短的搜索方式并求出搜索完整个区域的时间。若在小时内不能完成搜索任务，需要增加到多少人才可以完成。（2）若搜索队伍人，三组，台卫星电话。每组可独立将搜索情况报告给指挥部门。设

5、计耗时最短的搜索方式并求出搜索完整个区域的时间。二、模型假设假设搜索目标区域为长米，宽米的平地矩形区域，需要进行全境搜索。假设每个搜索队员搜索时的可探测半径为米，搜索时平均行进速度为米/秒；不需搜索只行进时,平均速度为米/秒。假设步话机通讯半径为米。假设在出发点部署时，等到所有队员都到自己的位置后所有人在同一时间出发。假设搜索队员一旦发现目标，直接向组长报告，组长立即向指挥部报告，报告时间为秒，且不影响搜索工作。假设搜索队员一旦发现目标，能够直接定位彼此的相对坐标，并根据自己的定位仪得到的自身坐标，定出目标的坐标，花费时间为秒。三、符号说明与概念3.1符号说明---

6、-------赋权连通图；-----------------赋权连通图的第个子图；------------------子图中的最佳回路；----------------边的边权；------------------点的边权；-----------------最佳回路的各边权之和；------------------的各点权之和；---------------------搜索每块区域的时间增加到人，在47.41小时内可以完成搜索任务。3.2概念均衡度：为该分组的实际时间均衡度，显然，越小，说明分组的均衡度越好；最大容许均衡度：；均衡分组：取定一个后，和满足条件（其中）

7、的分组时一个均衡分组。四、模型分析4.1搜索队员为人时的思路4.1.1圆滚动性模型圆滚动模型是以组长为圆心，为半径的圆以一定速度向前滚动。用类比的方法就可以得到人一起以同一速度向前搜索，覆盖整个矩形区域。我们还给出了一些数据，见附录一。我们在表中取每个人到各点的时间，绘成每个人的时间——地点图。为了描述方便我们取1号，2号，20号人员的图在同一图中以不同颜色显示，命令为：Show[p1,p2,p20]由离散图联线得到的图证明随着每人路程的增加，图形大致有两两之间距离增加的趋向。而且增加只出现在拐弯处，所有人的时间差成扇形分布，且外侧时间叫大，当到了直行时，时差不