数学建模中的地面搜索问题

ｔＲｓ）时小（

第３０卷第８期湖南科技学院学报

Ｖｂｌ＿３０ＮＯ．８２００９年８月

ＪｏｕｒｎａｌｏｆＨｕｎａｎＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇ

Ａｕｇ．２００９

数学建模中的地面搜索问题

力石’搿

（湖南工学院基础课部，湖南衡阳４２１０００）

摘要：本文根据２００８年全国大学生数学建模竞赛ｃ题提出了紧急情况下地面搜索任务的搜索路线设计思想，并建立了单组搜索队伍完成搜索任务的时间计算模型及其改进模型．同时，推广到分组搜索队伍情况下完成搜索任务的时间计算模型及其改进模型，这也是对单纽搜索队伍完成搜素任务时间模型的又一改进．

关键词：地毯式搜索；盲区；交换路径中图分类号：０１４

文献标识码：Ａ

文章编号：１６７３－２２１９（２００９）０８－０００８－０４

１

模型假设Ｓ括：小组中搜索队员ｆ在搜索过程中。地毯式”搜索的１．搜索区域全境无障碍物；

路程；

２．每个ＧＰＳ地位仪能精准显示每个搜索队员的位置，且每个队员能严格按照规定路径搜索；

３问题分析

３．当搜索人员搜索到目标时，通过步话机直接或间接向要实现搜索人员对平地矩形目标区域进行快速全面搜组长汇报结果，汇报时间不计入完成任务搜索时间；

索，搜索路线图的设计应满足两个要求：（１）避免对目标区４．当搜索人员搜索到目标时，搜索人员的滞留时间不计域的重复搜索；（２）每个搜索人员所搜索的面积相等。显然，入完成任务搜索时间；

完全满足以上两个要求搜索路线图是不可能的，是一种理想５．搜索人员都从同始点。同时”出发（不考虑出发时间状况。基于此种理想状况，针对一个面积足Ｓ的目标区域差），并回到同一终点。

派遣Ⅳ人对它进行搜索，理论上完成搜索任务的时间模型为：

２符号说明

Ｌ

‘。

。‘

Ｖｂ：搜索队员的步行速度１．２彩秒；

ｖ。：搜索队员的步行速度０．６米／秒；在问题一中．针对２０人的搜索队伍，理论上完成搜索

』，一一Ｉ，Ｊ、Ⅱ１，

瓦＝—２ｒ二ＮＬｖ一

ｒ：每个搜索队员的搜索半径２０米；Ｒｔ：时间换算常数６０ｘ６０；任务的时间是瓦＝虿忑面１忑１２石００丽ｘ五７２聂００丽＝４６．６７（小时）

Ｔ：完成搜索任务的实际时间；在问题二中，针对５０人的搜索队伍，理论上完成搜索任瓦．：理想状况下完成搜索任务的时间；务的时间是

ｆ：小组中搜索队员ｆ，取值为ｌ、２、…、２０；

瓦＝夏蕊１Ｌ

’’

’’

２ｘ２０×５０×Ｏ．６ｘ６０×６０

正：小组中搜索队员ｆ完成搜索任务的时间；１丽２００而ｘ７蕊２００＝１８．６７（小时）

所以，按任何一个搜索路线图执行搜索任务，完成搜索

瓦：搜索过程中搜索队员ｉ的步行时间；

乃：搜索队员ｉ与搜索队员【２１一ｆ）的“交换路径”时

任务的时间丁应满足Ｔ≥瓦。换句话说，实际完成搜索任务的时间Ｔ越靠近理论上完成搜索任务的时间瓦．，搜索

问；

路线图的设计就越好。’

瓦ｌ：搜索过程中搜索队员ｉ的“地毯式”搜索时间；瓦２：搜索过程中搜索队员ｉ的。盲区”搜索时间；４问题一：２０人小组搜索乙：单个盲区的搜索时问；

，

１１２００×７２００的矩形区域

ｎ：单个搜索队员在搜索过程中需要搜索盲区的个数；４．１模型分析

Ｓ曲：小组中搜索队员ｉ在搜索过程中步行的路程；

首先为保证２０人小组在搜索过程中能正常通讯。并且无重复搜索。让２０人小组形成“地毯式”搜索。所谓。地

收稿日期：２００９－－０３一１８

毯式”搜索，将２０人分别编号为第１人、第２人、……、作者简介：万云涛（１９７８一），湖北云梦人，硕士，湖第２０人，他们同时从始点水平向右以１．２ｒｒｄｓ速度步行（如南工学院讲师，研究方向为数学应用。

图一），当第１人步行２０米时再向上以０．６ｒｒｄｓ搜索；当第２

８

人步行６０米时再向上以０．６ｍ／ｓ搜索；当第３人步行１００米时再向上以Ｏ．６ｍ／ｓ搜索；……当第２０人步行７８０米时再向上以０．６ｍ／ｓ搜索。如此，一方面可以避免重复搜索；另一方面，２０人的搜索区域相邻，形成“地毯式”的搜索带。

当然，２０人中的每个人均是形成以２０米为半径的“地毯式”的搜索带。根据矩形搜索区域的长、宽及小组搜索带的宽度（８００米），在搜索区域不重复的情况下。设计如图一所示的搜索路径。

———・擅索队员１的路径

…・－◆搜索队员２０的％径

图一

…ｊ－…２０人组搜索带

其次，在“地毯式”搜索过程中，每个队员定会遇到拐弯，左（或右）上角会出现一个“盲区”（如图二），即留下一个区域没有搜索。

４．３．１步行时间％的计算

搜索队员ｆ在搜索过程中的步行时间由两段路程决定：第一段路程是搜索队员从任务开始的出发点步行到自己搜索区域的出发点，在。地毯式”搜索区域的最初边界上；第二段路程是搜索队员从自己搜索区域的终点步行到最后的集结点，在。地毯式”搜索区域的走后边界上。显然，２０个搜索队员的步行路程均为Ｓ曲＝８００（米），所以

拐点盲区

％＝西而８００而＝０．．１８５ｌ（小时）

４．３．２。地毯式”搜索时间正。ｌ的计算

在图一中，可计算得Ｓｌ，＝９９２８０（米）。Ｓ２０，＝１０２３２０（米）；且容易发现２０个搜索队员的搜索路程呈公差为ｄ＝１６０（米）的等差数列。所以

最后，。地毯式”搜索完，他们不会同时到达以终点为左端点的长度为８００米的搜索带边。任何成员一旦搜索到最后的搜索带边，便以１．２ｍ／ｓ的速度步行到终点。

４．２模型建立

从以上分析可知：（１）小组完成任务的时间应以２０个队员中任务完成时间最长的为准；（２）单个队员完成任务的时间可分为三个部分计算：步行时间、。地毯式”搜索时间、“盲区”搜索时间。因此，小组完成任务的时间模型（模型一）为：

耻等等

ｃ删

４．３．３。盲区”搜索时间瓦２的计算

对“盲区”搜索，作如下处理：搜索队员沿拐弯点左（或右）上方４５。以Ｖ，搜索（√２一１）ｒ米，然后以Ｖ６步行返回拐弯点继续“地毯式”搜索。因此，单个“盲区”搜索时间为

丁＝毒（ｚ）＝ｎ蓦２０ｘ（瓦＋瓦。＋瓦：）

其中

乙＝等＋等仆ｍ

由图一可得每个搜索员在搜索过程中共有ｎ＝５０个拐

弯点，所以“盲区”搜索时间为

毛＝去，耻ｖＳ万ｉｓ

４．３模型求解

Ｔ扫２－＂ｇｌＬ

枷监等产一ｏ．２８７６仆咖

所以，２０人小组完成任务的时间为

９

７’＝冒２０亿）＝Ｈ兽２０ｘ（瓦＋瓦－＋瓦ｚ）

丁＝田警亿）＝田警阢＋死－丁：田２警Ｏ亿）：田２警０阢＋死。＋Ｔ／ｓ２＋乃）Ｉ＝１

Ｉ＝ｌ

＋乃）

其中

＝％＋ｍａｘ（ｒ／￥１）＋瓦２

Ｓ曲

％Ｒ’

经计算得２０人小组快速全面搜索矩形区域的完成时间为

Ｔ＝‰＝４７．８４３ｌ

（小时）

曩２Ｉ一）』

：—８００－２（—２ｉ－１）ｒ，

瓦－＝鲁，Ｔ厶２＝ｎ乙，（ｆ＝ｌ、２、…、２０）

Ｄ：１、２、．．．、ｌｏ）

、

Ｖｂ

Ｒｔ

故２０人小组可以按如图一所示搜索路径在４８小时内完成。

４．４模型改进

即Ｔ＝瓦Ｊ＋瓦２＋吧挚‰＋巧Ｊ

在模型一中，搜索区域虽无重复，但搜索成员的搜索面经计算得：

积不相等。本模型采用“交换路径”的方法来改建，以期用－Ｔ＝‰＝４７．４９１３

（小时）

更短的时间来完成搜索任务。

即小组完成全面搜索任务的时间为４７．４９１３小时。比不交换

“交换路径”又称为“中途交换搜索路径”。根据２０路径要节约０．３５１８小时。

个成员的。地毯式”搜索路程成等差数列（即搜索面积也成等差数），可以找到他们“地毯式”搜索路程的“中点”在ＡＢ５问题二：５０人分３组搜索

上（见图一）。在上述模型的基础上，让搜索队员ｆ（ｆ＝ｌ、Ｉ

１２００ｘ７２００的矩形区域

２、…、１０）和搜索队员（２ｌ—ｆ）分别搜索到自己“中点”时，５．１模型分析

沿Ａ曰步行到对方的“中点”，完成对方剩下的一半搜索路以２０人组为基础，根据要求将５０人的搜索队伍分成Ａ程。显然，“交换路径”后，每个队员的“地毯式”搜索路（２０人组）、Ｂ（２０人组）、Ｃ（１０人组）三组，三个小组的程均为Ｓ打＝１００８００

（米）；

步行路程为

搜索任务满足以下要求：（１）搜索面积比以２：２：ｌ最为理Ｓ西＝２【ｒ＋２ｒ“一１）】（米）；“盲区”搜索时间仍为

想；（２）Ａ、Ｂ两组的搜索任务优先分配，搜索面积相等且

瓦２＝Ｏ．２８７６（小时）；每个搜索队员多了“交换路径”时

９

，’

间，并且搜索队员ｆ（ｉ＝ｌ、２、…、１０）和搜索队员（２ｌ—ｆ）

不少于总面积的詈（以詈为佳），搜索路线具有对称性；（３）

３

）

的。交换路径一时间相等为Ｉｆ：—８０—０—－２—（２＿ｉ一－１）ｒ（小时）。每个小组的搜索任务同问题一的解决方案。于是，可得搜索％Ｋ｜

路线图（图三）。

由此可得改进模型（模型－－）：

图三

５．２模型建立、求解

当Ａ（Ｂ）组队员搜索到朋Ｗ（Ｍ’Ｎ’）段时步行到

根据图三可建立模型（模型－－）为：

终点；当Ｃ组队员搜索到ＥＦ段时向始点步行４００米再向下Ｔ＝ｍａｘ（Ｌ，瓦，砭）

继续地毯式搜索。按模型一可计算三组完成任务的时间分别其中瓦、瓦、砭分别是Ａ、Ｂ、Ｃ三组完成搜索任务的时

为：

间。

Ｌ＝瓦＝％

ｌＯ

一．Ｌ～

７８０＞＜２＋１２００１．２ｘ６０ｘ６０

＝１９．７９２２

４１１６０

６模型评论

０．６ｘ１．２ｘ６０ｘ６０

０．６ｘ６０ｘ６０

虽然模型一所计算时间比理论完成搜索任务的时间要多Ｉ．１７３ｌ小时，但搜索小组还是能在４８小时内完成任务，问题一“勉强”得到解决。模型一的改进模型（模型二）计算

（小时）

％＝互。

＝一十一１ｒ—‘——————————————————————————————‘

８００

．４０２０

．【√２一ｉ／ｘ５４ｘ２０ｘ（Ｏ．６＋１．２）

０．６ｘ１．２６０ｘ６０

所得全面搜索完成任务的时间更为接近理论完成搜索任务的时间，使问题一得到更完美的解决。模型三不但是对模型一和模型二的改进，更是一种推广。另一要关注的是在Ｃ组完成任务的时间计算上，并没有采用。交换路径”。不难发现小组中队员的搜索路程差距越大，交换路径越管用。至于在什么情况下使用交换路径的定量计算值得深入地探讨。

１．２ｘ６０ｘ６０

０．６ｘ６０ｘ６０

＝１９．０２３６（小时）

故全面搜索完成任务的时间是Ｔ＝１９．７９２２小时。

按模型二可计算Ａ、Ｂ两组完成任务的时间均为：

Ｌ＝瓦＝正＝％

＝：～－．・一１‘ＪＬ————————‘———————————————————————－－——二

８００＋１２００

３９６００

（√２—１）ｘ１７ｘ２０ｘ（Ｏ．６＋１．２１

０．６ｘ１．２ｘ６０ｘ６０

１．２ｘ６０ｘ６００．６ｘ６０ｘ６０

参考文献：

【】】阮沈拥，等．ＭＡＴＬＡＢ程序设计【Ｍ】．北京：电子工业出版社，２００４．

。！鱼堕

＝１９．３０８８

１．２ｘ６０ｘ６０

（小时）

【２】姜启源。等．数学建模【Ｍ】．北京：高等教育出版社，２００６．【３】苏金明，阮沈勇，等．ＭＡＴＬＡＢ实用教程【Ｍ】．北京：电子工业出版社，２００３．

【４】赵静．数学建模与数学试验【Ｍ】．北京：高等教育出版社，２００３．

【５】张志勇，徐彦琴，等．ＭＡＴＬＡＢ教程【Ｍ】．北京：北京航空航天出版社，２００１．

对Ｃ组，在不交换路径时，搜索队员１的路程为比搜索队员ｌＯ的路程只少２０米，并且１０个搜索队员完成任务的时间差就只在。地毯式”搜索时间。如果交换路径，增加交换路径时间的同时也增加了步行时间。相比之下，不交换

路径时完成任务的时问更短。此时我们取砟＝１９．０２３６小

时。

故全面搜索完成任务的时间是Ｔ＝１９．３０８８小时。比不交换路径要节约０．４８３４小时。

【６】周义仓，赫孝良．数学建模实验【Ｍ】．西安：西安交通大学出版社，１９９９．

（责任编校：何傻华）

ＴｈｅＧｒｏｕｎｄＳｅａｒｃｈ

ＷＡＮ

Ｑｕｅｓｔｉｏｎ

Ｙｕｎ－ｔａ０’

（ＢａｓｉｃＣｏｕｐｅｓＤｅｐａｒｔｍｅｎｔｏｆＨｕｎａｎＩｎｓｔｉｔｕｔｅｏｆＴｅｃｈｎｏｌｏｇｙ．Ｈｅｎｇｙａｎｇ４２１００１，Ｃｈｉｎａ）

Ａｂｓｔｒａｃｔ：Ａｃｃｏｒｄｉｎｇ

ｔｏ

ｑｕｅｓｔｉｏｎＣｉｎＣＵＭＣＭ，ｔｈｉｓｐａｐｅｒｐｕｔｓｆｏｒｗａｒｄｔｈｅｄｅｓｉｇｎｉｄｅａｏｆｓｅａｒｃｈ

ｒｏｕｔｅ

ｆｏｒｇｒｏｕｎｄｓｅａｒｃｈｔａｓｋｓ

ｉｎｅｍｅｒｇｅｎｃｙ．Ａｌｓｏ，ｔｈｉｓｐａｐｅｒａｃｃｏｍｐｌｉｓｈｅｓｔｈｅｍｏｄｅｌｌｉｎｇａｎｄｉｍｐｒｏｖｅｄｍｏｄｅｌｉｎｇｏｆｃａｌｃｕｌａｔｉｎｇｔｈｅｔｉｍｅｓｐｅｎｄｅｄｂｙｓｉｎｇｌｅｓｅａｒｃｈｇｒｏｕｐ

ｔｏ

ｃｏｍｐｌｅｔｅｔｈｅ

ｓｅａｒｃｈｔａｓｋｓ．Ｍｅａｎｗｈｉｌｅ，ｔｏｉｍｐｒｏｖｅｔｈｅｐｒｅｖｉｏｕｓｍｏｄｅｌｉｎｇ，ｔｈｉｓｐａｐｅｒｆｉｎｉｓｈｅｓｔｈｅｍｏｄｅｌｉｎｇａｎｄｉｍｐｒｏｖｅｄ

ｇｒｏｕｐｓ

ｔｏ

ｍｏｄｅｌｉｎｇｏｆｃａｌｃｕｌａｔｉｎｇｔｈｅｔｉｍｅｓｐｅｎｄｅｄｂｙｓｅｖｅｒａｌｓｅａｒｃｈｃｏｍｐｌｅｔｅｔｈｅｓｅａｒｃｈｔａｓｋｓ．

Ｋｅｙｗｏｒｄｓ：ｒｕｇｔｙｐｅｓｅａｒｃｈ；ｂｌｉｎｄｓｐｏｔ；ｅｘｃｈａｎｇｅｗａｙ

数学建模中的地面搜索问题

作者：作者单位：刊名：英文刊名：年，卷(期)：被引用次数：

万云涛， WAN Yun-tao

湖南工学院,基础课部,湖南,衡阳,421000

湖南科技学院学报

JOURNAL OF HUNAN UNIVERSITY OF SCIENCE AND ENGINEERING2009，30(8)0次

参考文献(6条)

1. 阮沈拥 MATLAB程序设计 20042. 姜启源 数学建模 2006

3. 苏金明. 阮沈勇 MATLAB实用教程 20034. 赵静 数学建模与数学试验 20035. 张志勇. 徐彦琴 MATLAB教程 20016. 周义仓. 赫孝良 数学建模实验 1999

本文链接：http://d.g.wanfangdata.com.cn/Periodical_llxyxb200908003.aspx

授权使用：复旦大学图书馆(fddxtsg)，授权号：7d559f1d-6300-4418-8b97-9dda017a5cac

下载时间：2010年8月22日