地面搜索

地面搜索（精选四篇）

地面搜索 篇1

下面是一个简化的搜索问题。有一个平地矩形目标区域,大小为11200米×7200米,需要进行全境搜索。假设:出发点在区域中心;搜索完成后需要进行集结,集结点(结束点)在左侧短边中点;每个人搜索时的可探测半径为20米,搜索时平均行进速度为0.6米/秒;不需搜索而只是行进时,平均速度为1.2米/秒。每个人带有GPS定位仪、步话机,步话机通讯半径为1000米。搜索队伍若干人为一组,有一个组长,组长还拥有卫星电话。每个人搜索到目标,需要用步话机及时向组长报告,组长用卫星电话向指挥部报告搜索的最新结果。假定有一支20人一组的搜索队伍,拥有1台卫星电话。请设计一种你认为耗时最短的搜索方式。按照你的方式,搜索完整个区域的时间是多少?

2 模型的建立与求解。

本问题是在最短的时间内,因为每个人的可探测区域是以自己为圆心,半径为20米的圆形,而当两个圆相切的时候,重复的搜索区域是最小的,因此我们可以设计一种简单的地毯式搜索方案,最少需要47.6个小时。但是否地毯式搜索真正的重复搜索最少的呢?在研究进行地毯式搜索的过程中发现,虽然队员间没有重复搜索,但是对每个队员自己来说,他都是沿直线不停的向搜索前进,因此搜索范围会有很多的重,怎样才能减少自己的重复搜索面积?因为只要队员是在搜索中前进,就不可避免的在重复自己的搜索过的区域。所以我们提出一种新的方案,即以不搜索的行进速度到达某些指定定点搜索,并且保证在所有定点搜索总区域覆盖了整个灾区。这样我们就减少了单个队员重复搜索面积,并且搜索面积覆盖了整个灾区。比如在80*80的区域内进行搜索,我们以不搜索的行进速度,按照给定的路线行进并且在经过图中点A.B.C.D…M点时停下搜索,当指定的行进路线走完后或者这些点被经过并停下搜索之后,我们就能保证我们就搜索完了80*80的小区域。如图1所示。

2.1 模型的建立。

我们把矩形区域模块化,分为边长大小都等于20米的小正方形,这样可以把矩形区域划分成5600*3600个正方形,只要每个小正方形区域中一条对角线上的两个点有队员经过的话,整个矩形区域就会被搜索完成。将区域模块化后,取任一小正方形中一条对角线上两点,并连接两点画出对角线,简化的部分区域如图2。将短边以2*r为间隔,从右下脚开始,依次编号1,2..181。长边以2*r为间隔,从右下脚开始,依次编号为1,2…281。以长边为x轴,短边为y轴,建立坐标轴,从右下角开始对斜线进行编号为Dj(j=1,2…461),部分图形如图3所示:

2.2 模型的求解。

所以方案总的耗时用matlab编程计算得t=41.89小时。

摘要：建立了地面搜索的优化模型。先算出两两队员搜索圆相切时地毯式搜索消耗的最少时间为47.6小时。但进一步分析得到,将区域划分为若干个20*20的小正方形,只要有队员以某种路程走完区域中的所有定点并搜索完时,其搜索范围就会覆盖整个正方形区域,并且耗时较少。

关键词：相切,区域,搜索

参考文献

[1]姜启源.数学模型(第三版)[M].北京:高等教育出版社,2005

地面搜索问题最优模式研究 篇2

地面搜索问题最优模式研究

基于一个假设的搜索问题,采用一种完全遍历算法,通过路径规划寻求若干条连接起始点到终点的运动轨迹,即最优或次优有效路径,并通过把要搜索的区域环境分解成为路径带,然后建立全局最优路径规划模型,力求在这个分块区域环境中寻找一种搜索时间最短的最优路径.

作 者：汤志浩 余小飞 孙叶平TANG Zhi-hao YU Xiao-fei SUN Ye-ping  作者单位：河南工业职业技术学院,河南,南阳,473009 刊 名：河北能源职业技术学院学报 英文刊名：JOURNAL OF HEBEI ENERGY INSTITUTE OF VOCATION AND TECHNOLOGY 年，卷(期)：2009 9(3) 分类号：P622+.1 关键词：地面搜索   完全遍历算法   多目标规划   时间均衡函数  

地面搜索的数学模型 篇3

搜索问题:有一个平地矩形目标区域, 大小为11200米×7200米, 需要进行全境搜索.假设:出发点在区域中心;搜索完成后需要进行集结, 集结点 (结束点) 在左侧短边中点;每个人搜索时的可探测半径为20米, 搜索时平均行进速度为0.6米/秒;不需搜索而只是行进时, 平均速度为1.2米/秒.每个人带有GPS定位仪、步话机, 步话机通讯半径为1000米.搜索队伍若干人为一组, 有一个组长, 组长还拥有卫星电话.每个人搜索到目标, 需要用步话机及时向组长报告, 组长用卫星电话向指挥部报告搜索的最新结果.现在有如下问题需要解决:假定有一支20人的搜索队伍, 拥有1台卫星电话.请设计一种你认为耗时最短的搜索方式.按照你的方式, 搜索完整个区域的时间是多少?能否在48小时内完成搜索任务?如果不能完成, 则需要增加到多少人才可以完成?

二、模型的建立与解答

假设个人同时去平地矩形目标区域的右边缘向左边缘搜索, 这个人不均匀的分布在目标区域的右边缘, 如图1所示, 以平地矩形目标区域的中心为坐标原点, 长边方向为x轴, 短边方向为y轴建立直角坐标系, 且设第i个人在右边缘开始搜索时的坐标为 (5600, yi) , i=1, 2, …, 10.为了节省搜索时间, 让搜索人员完成任务后同时到达集结点, 我们使这i个人不均匀的分布在目标区域的右边缘, 并且他们搜索的区域大小不同, 靠x轴越近的人员搜索范围越大 (因这些人员花在不搜索而只是行进上的时间少) .基于这一思想, 建立如下数学模型: (只考虑x轴上方的区域, 因x轴下方和上方完全对称) .

其中y0=0, y10=3600 i=1, 2, …, 10.T为搜索完全程的总时间.

取整函数表示第i个人完成他所搜索的区域所走来回的个数, 若搜索人员在目标区域的右边缘完成搜索任务, 则该搜索人员沿直线 (最短路) 返回集结点;若搜索人员在目标区域的左边缘完成搜索任务, 则该搜索人员沿目标区域的左边缘返回集结点.

利用MATLAB对非线性方程 (1) 式在给定的初值下迭代求解.

下面是运算的部分结果.

经迭代计算出T=55.978.虽然在此模型中考虑了最优 (让每个搜索人员在T=55.978小时中最大限度的忙碌) 和搜索人员间1000m的通信限制, 但从表1中不难看出, 搜索中重复搜索的区域过大, 浪费了时间, 并且在搜索过程中用了大量时间徒劳行进, 从而此模型需要在减少重复区域搜索和徒劳行进所需时间上做如下优化.

消极策略:以出发点为中心, 将场地平分为5600m×7200m的两部分, 平均分割中线为20份, 每份360m.又搜索可探测半径为20m, 故其直径为40m.将半径为20m的圆域沿直线走过的路径覆盖宽为40m的长方形.

现将20人平均分配到20个区域. 由于上下两部分10人搜索是对称的, 故只计算上面10人对其10个领域搜索用时即可, 令自底向上编号为1, 2, …, 10. 第10个人到达第10个区域用时为:, 在此期间, 其余9人均已到位, 并不进行搜索, 直到第10个人到位, 则每个人搜索其所在区域用时相同, 均为.搜索完成, 10人均位于区域右端, 以1.2m/s的速度穿过区域到达所在区域的顶端, 其间用时为.以同样的方式对左半区域搜索, 搜索用时为84300s, 并且第1人到达终点, 而且其余到达所在区域的底部左端点出, 此时沿沿左边宽向下行至终点, 以第10人用时最多, 为.

由此最终完成搜索任务用时为:

从此搜索法可以看出此方法的局限性在于搜索的消极等待所造成的时间损失这一点与方法二的弊端类似, 为此方法四是对此缺陷的弥补.

三、模型的优缺点分析

基于对本文提出模型及对其产生的数据的分析, 方程 (1) 中给出了一种对个人均适用的递推关系式, 虽然此关系利用迭代易于求解, 在实际生活中有较强的应用价值, 但是大量的数据分析发现该方法容易产生徒劳行进和大量重叠搜索, 造成时间浪费, 达不到最优.而方案四在继承方案二, 方案三在搜索过程中具有徒劳行进少, 重复少的优点上, 弥补了它们消极等待的缺陷, 使得问题求解趋于最优, 但推广性较弱.

参考文献

[1]张德富.算法设计与分析.北京:国防工业出版社, 2001.

[2]姜启源.数学模型.北京:清华大学出版社, 2000.

[3]赵静, 但琦.数学建模与数学实验.北京:高等教育出版社, 2003.

[4]沈继红.数学建模精解精练.哈尔滨:哈尔滨工程大学, 2007.

[5]周义仓, 赫孝良.数学建模实验.西安:西安交通大学, 2007.

[6]陈东彦, 李冬梅, 王树忠.北京:科学出版社, 2007.

基于网络通信的震区地面搜索研究 篇4

为了达到搜索耗时最短, 我们应该尽量使得单位时间探测的面积最大, 重复探测的面积最少, 而且必须保证搜索队通信畅通。从而, 考虑采用单列前行的探测方法。由于队伍的长度较长, 转弯的方法就至关重要, 选择不同的转弯方案, 其转弯时间差距会较大。探测时间只和人数及探测速度有关, 从而转弯时间是节约耗时的关键点。

二、单组队伍单区域搜索

单列行进最少弯路搜索:在此种搜索法中, 单组队伍排成一列进行搜索, 队员的间隔距离为2r, 其足够可以保证步话机的通讯, 亦可保证队员与组长之间的通讯。

由于搜索终点所在位置会随着格子行数的改变而相应地发生变化, 当格子行数为奇数时且l≥h ( 如果l < h, 我们可以将l看成是h) , 其终点出现在集结点的右上方或者右下方且交替出现, 此时集结所需时间最少, 但分散时间所用最多。当格子行数为偶数时且l > h, 其终点出现在起始点的左侧相邻格子内, 此时分散时间最少, 集结时间最长。

三、单列队伍“回”字路径搜索

“回”字路径搜索, 顾名思义, 用一环套一环的回环覆盖目标区域, 在此搜索法中, 由于各回环间可以用一条路径进行连接, 那么, 搜索的方向可以采用顺时针、逆时针交替的方式进行。采用一种边探索边转弯的无缝连接转弯法, 顺时针、逆时针交替进行搜索, 从而可以抵消掉内圈与外圈的时间差, 可有效的利用模型一中的等待时间, 使得该模型的等待时间尽可能的小, 能保证队员们通讯畅通。

四、多组队伍并行分区搜索

有多组队伍参与搜索时, 须对目标区域进行分块, 每组搜索一个区域, 则此时是一个并行的搜索过程, 且互相独立 (每组可独立将搜索情况报告给指挥部门) 。故区域划分的好坏直接影响到搜索耗时。

命题1. 区域只能是纵向划分。

证明:因为探测时间只由探测半径和参与搜索的人数相关, 转弯时间是个定值 (转弯方式确定的情况下) 。由于集结点在短边左侧中心位置, 那么, 无论是采用最少弯路搜索还是“回”字路径搜索, 其终点都会落在离集结点较近的区域。那么如果横向划分区域, 就是直接增加了其集结时间。从而增加其搜索时间。故只能是纵向划分区域。一般说来, 区域的纵、横向划分与其集结点相关。

队伍分组进行搜索的目的是为了让所有组的搜索并行化, 从而减少整个区域的搜索时间。那么最理想状态下, 所有组对整个区域的搜索时间应等于单个组搜索其所在区域的时间 (分组人数相同) 。当然这种情况在实际中是不可能存在的。根据以上算法可以得出以下区域搜索路径, 如图8。图8中, 1号区域的图形高度比目标区域高度稍大, 三个图形的合的长度也比目标区域长度稍大。

五、后记

模型有严格的数学推导过程, 并给出了算法的具体步骤及Matlab程序, 模型具有较好的实用性及通用性。只需修改较少的几个参数便可将其推广到任意目标区域的搜索。模型使用图形仿真的方式对其进行检验, 以保证其可靠性。

摘要：地震使震区地面交通和通讯系统严重瘫痪。救灾指挥部紧急派出多支小分队, 到各个指定区域执行搜索任务, 以确定需要救助的人员的准确位置。本文讨论在目标区域内如何制定全境搜索路径, 使得所耗时间最短。运用Matlab编制文中两种搜索算法程序, 其可自动进行全境搜索并绘制出详细的搜索路径图。