c题地面搜索模型

《c题地面搜索模型》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2008年C题地面搜索模型如何制定搜救队伍的行进路线，在最短的时间内对预定区域进行快速的全面搜索是在此紧急情况下需要解决的重要问题之一。本文旨在研究在一平地矩形区域上的地面搜索问题。　　地面搜索模型山东电力高等专科学校班艺瀚闫忠伟韩丽萍丁梅指导论文点评:本文根据实际问题的实际背景应用图论建立了搜索数学模型,分析了搜索过程中路径选择策略问题，对20人搜索问题提出有效的整体搜索方案和路径选择，计算了完成全面搜索所需要的时间，并研究了完成搜索人物所需要的人数，得到了较好的结果。对50人搜索问题提出了分组和分

2、区域方案。本文的创新之处在于文章对种方案的均衡性进行了较为深入的讨论。中国石油大学数学与计算科学学院王子亭教授2008/09/25摘要2008年5月12日汶川发生里氏8.0级特大地震，使得震区地面交通和通讯系统严重瘫痪。如何制定搜救队伍的行进路线，在最短的时间内对预定区域进行快速的全面搜索是在此紧急情况下需要解决的重要问题之一。本文旨在研究在一平地矩形区域上的地面搜索问题。在问题一中，我们首先给出了20人一组的搜索队伍,搜索完整个区域至少需要个小时这样一个有利的结论。我们先采用圆滚动模型，但会出现队员

3、与组长联系不到的缺点；经分析，采用图论中的赋权连通图法可以改进圆滚动模型的缺点，组长在任何位置都可以联系到所有队员，搜索中不存在重叠现象，且搜索用的时间最短，在赋权连通图用算法找到最小生成树，在此生成树中采用扩环策略、增环策略、换枝策略的思想，经过调整，采用拐弯、不拐弯两种搜索方法，寻找到20人一组的最佳搜索路线。按此方式，我们得到这样几个结果：(1)搜索完整个平面矩形区域所用的时间为小时。-18-/18(2)在小时以内不能完成搜索任务。(3)增加到人，在47.41小时内可以完成搜索任务。在问题二中，

4、我们采用第一、二组各20人，第三组10人的分组方式，给出了分组的均衡度，说明分组的均衡度很好。我们根据最小生成树分解原则进行分区域，再次采用扩环策略、增环策略、换枝策略的思想，给出了第一、二组搜索完需要的时间是，第三组搜索完需要的时间是。即50人三组搜索完整个平面矩形区域需要。最后，给出了一个双层非线性规划，将其内层目标函数、约束条件构造了条件，从规划的角度分析了此模型。图论中的赋权连通图法，将图论，规划，算法有机地结合在一起。关键词：最小生成树；均衡度；规划；圆滚动模型一、问题重述1.1背景2008

5、年5月12日汶川大地震中，震区地面交通和通讯系统严重瘫痪。大家知道救助灾民的黄金时间是72小时，能在短时间内搜索到需要救助的人员得位置，并更快的进行救助是我们的首要任务。救灾指挥部紧急派出多支小分队，到各个指定区域执行搜索任务，以确定需要救助的人员的准确位置。在这种紧急情况下需要解决的重要问题之一是：制定搜索队伍的行进路线，对预定区域进行快速的全面搜索。1.2简化的搜索问题我们有一个平地矩形目标区域，需要进行全境搜索。出发点在区域中心；搜索完成后需要进行集结，集结点在左侧短边中点。每个人带有GPS定位

6、仪、步话机。搜索队伍若干人为一组,有一个组长，组长还拥有卫星电话。每个人搜索到目标，需要用步话机及时向组长报告，组长用卫星电话向指挥部报告搜索的最新结果。1.3我们需要解决的问题（）若搜索队伍人，一组,台卫星电话。设计耗时最短的搜索方式并求出搜索完整个区域的时间。若在小时内不能完成搜索任务，需要增加到多少人才可以完成。-18-/18（2）若搜索队伍人，三组，台卫星电话。每组可独立将搜索情况报告给指挥部门。设计耗时最短的搜索方式并求出搜索完整个区域的时间。二、模型假设假设搜索目标区域为长米，宽米的平地矩

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

8、---------------赋权连通图的第个子图；------------------子图中的最佳回路；----------------边的边权；------------------点的边权；-----------------最佳回路的各边权之和；------------------的各点权之和；-18-/18---------------------搜索每块区域的时间为叙述方便起见，我们在文中不加说明的使用上述变量或符号的变形形式，它们的含义可通过上