基于哈密顿通路解决的地面搜索模型

1、基于哈密顿通路解决的地面搜索模型作者：董爱卿（女）计算机应用技术08-4钟 瑞 计算机应用技术08-3崔 涛 计算机应用技术08-3 摘要本文针对地面搜索问题关于队员安排和路线选择问题，建立了优化模型。在确保地面搜索不遗漏以及路线尽量不重复情况下，使得搜索的时间尽量少。具体结果如下：问题一的求解中，我们模拟了三种方案。方案1，为了在搜索到人员后能尽快联系到组长，我们认为20个人应该并排走，按照s的路线搜索完，虽然避免了地面搜索不遗漏的情况，但却走了重复的路线（具体路线见图1），并且最终求出，搜索任务完成后需要50.01小时。方案2，为了确保不走重复路线，我们又想到了哈密顿通路解法（具体路线见图

2、2），这样就解决了路线重复问题，但在拐角处会浪费很多时间，这种方案完成搜索任务需要50.28小时。方案3, 每一种方案都避免不了过两种拐角所浪费的时间和队伍分散与集合所需要的时间，第一种拐角是90度弯的拐角，第二种拐角是0度或180度的拐角，第一种拐角处需要10.8分钟整理队型，第二种拐角处需要11.1分钟平移整个队伍；而队伍分散与集合所需时间为10.6分钟。因此，在方案2的问题上我们进行了优化，即尽可能大的削减拐角数量，我们有方案2上的18个拐角削减到15个拐角，这样，搜索任务完成需要49.80小时。由以上可知，我们无法在48小时内完成搜索任务，我们需要增加人手。首先需要解决一个小应用题：2

3、0个人完成一任务耗时49.8小时，那么，在48小时内完成同样的任务至少需要多少人？答案是49.8*20/48=20.75即至少要21人。同理可证，我们需要增加1位搜索人员。问题二的求解中，根据问题一的优化方案，我们继续用哈密顿通路的方法解决。为了便于路线的安排，我们确定了三个小组的人数，即20,20,10人。暂且按顺序分别叫做小组1，小组2，小组3。为了使任务平均分配，我们认为小组1应搜索此块矩形的目标区域，小组2应搜索此块矩形的目标区域，小组3应搜索此块矩形的目标区域。也就将此块矩形分成了三块。我们根据哈密度通路原则确定三个小组的通路后，三个小组所花费的时间分别为20.16小时、20.16小

4、时、20.08小时，从而搜索完整个区域所需的时间是 20.08小时。关键词： 哈密顿通路 最短路径 弯道策略 图论一、 问题重复与分析·5.12汶川大地震使震区地面交通和通讯系统严重瘫痪。救灾指挥部紧急派出多支小分队，到各个指定区域执行搜索任务，以确定需要救助的人员的准确位置。在其它场合也常有类似的搜索任务。在这种紧急情况下需要解决的重要问题之一是：制定搜索队伍的行进路线，对预定区域进行快速的全面搜索。通常，每个搜索人员都带有GPS定位仪、步话机以及食物和生活用品等装备。队伍中还有一定数量的卫星电话。GPS可以让搜索人员知道自己的方位。步话机可以相互进行通讯。卫星电话用来向指挥部报告

5、搜索情况。下面是一个简化的搜索问题。有一个平地矩形目标区域，大小为11200米×7200米，需要进行全境搜索。假设：出发点在区域中心；搜索完成后需要进行集结，集结点（结束点）在左侧短边中点；每个人搜索时的可探测半径为20米，搜索时平均行进速度为0.6米/秒；不需搜索而只是行进时,平均速度为1.2米/秒。每个人带有GPS定位仪、步话机，步话机通讯半径为1000米。搜索队伍若干人为一组,有一个组长，组长还拥有卫星电话。每个人搜索到目标，需要用步话机及时向组长报告，组长用卫星电话向指挥部报告搜索的最新结果。现在有如下问题需要解决：1假定有一支20人一组的搜索队伍, 拥有1台卫星电话。请设计

6、一种你认为耗时最短的搜索方式。按照你的方式，搜索完整个区域的时间是多少? 能否在48小时内完成搜索任务? 如果不能完成，需要增加到多少人才可以完成。2为了加快速度，搜索队伍有50人，拥有3台卫星电话，分成3组进行搜索。每组可独立将搜索情况报告给指挥部门。请设计一种你认为耗时最短的搜索方式。按照你的搜索方式, 搜索完整个区域的时间是多少?该问题来源于实际，我们认为合理的方案需要考虑如下因素：1尽可能少走重复路线2由于是搜救伤员，应该把所有区域搜索一遍3尽可能让每组和每位搜救人员的工作量相等4过拐角时，搜索人员行走路程尽量相同，尽可能少走问题分析和拟解决思路：从题目要求出发，主要解决以下两个大问题

7、：1一支20人的搜索队伍, 拥有1台卫星电话，为了保证他们及时向组长报告情况，他们要同时进行搜索任务；为了不重复搜索某一区域，且任务同时进行，搜救人员应一字排开，组长在队伍中间；确定区域搜索通道，确定搜索路线，计算搜索时间，若所用时间大于48小时，还要确定需要增加多少人才能在48小时以内完成此任务。250人分成三组，确定每组人员的数量，确定确定区域搜索通道，根据每组人员比例分配搜索任务，确定搜索路线，计算出每组所用时间。二、模型假设1. 搜索可一直进行，中途不会因任何情况而停止；2. 不考虑搜索目标区域是否平地、仪器的准确度，人员的个人因素等；3. 所给的数据，如搜索的平均速度都准确，不影响搜

8、索所需的时间；4. 搜索的区域盲点搜索没有忽略；5. 定位仪与通信工具一直正常使用；6. 无论什么天气，无论白天黑夜，搜索半径保持20米；7. 先拐完弯并站好阵型的队员要等最后一个站好阵型的队员后，同时搜索；三、数据分析与建模：问题一问题一是求解问题二的前提，首先应该确保搜索的范围包括全部的矩形区域，其次尽量不要走重复路线，走重复路线很费时间。因为只有一个卫星电话，所以组长要与队员同时一块行走。队伍一字排开。搜索的宽度为800米，长和宽正好是800的整数倍。这样我们就确定了，基本的路线。队伍最后留一个通道到达左边中点处，由一个方向搜索到距离尽头800米处折回。模型一（图一）队伍行进(绿色线的时

9、间tt=5546.9271.2+876.581.2=5352.84s这个人搜索的时间为tt=1498000.6=168000s此人经过拐角的时间tt=108001.2=6666.67s从而得出搜索完毕后所需总时间为180019.5067s,即50.01小时不过这样，需要走重复的路线。为了减少重复搜索所费的时间，我们认为路线不能左右方向来回搜索，所以经过进一步修改后，我们设计出了另一种方案。即模型2 （图二）这个人搜索的时间为tt=1498000.6=168000s拐弯所耗费的时间为tt=178001.2+7801.2=11983.333s集合与分散的时间为tt=3801.2+1.2=1042.

10、666s模型二完成任务所花费的总时间为181025.0s，即50.28小时模型二中我们发现在拐角处，队伍分散与集合大概需要11分钟，而且此模型有18个拐角，队伍在拐角处就要浪费198分钟。我们对模型二进行了优化，尽量减少拐角，我们设计了模型三，如下图。（图三）搜索时间为tt=1498000.6=168000s队伍通过拐角所浪费的时间为tt=148001.2+78021.2=10633.333s集合与分散所需时间为tt=3801.2+3801.2=633.333s完成任务所需的总时间为179266.666s，即49.796小时。这样模型三少了2个拐角，即省了33分钟。问题2在问题1的前提下，主要

11、考虑尽量缩短搜索时间。首先，我们考虑了如何将50个人分到三个小组里，如果小组中的人数不是10的整数倍，队伍一字排开后的宽度将不会被7200和11600整除， 经过商讨后，我们确定了三个小组的人数分别为20,20,10。这样就避免了，人员浪费问题。根据人数，我们认为，三个小组的搜索范围，分别为矩形面积的， 。为了降低问题的难度，我们假设组员为20人的两个小组所走路线对称，所以我们拟出模型一（图四）小组1和小组2完成任务所需要的时间为tt=50.58000.6+38001.2+7801.2+7801.2+11801.2=70966.67s即19.71小时。小组3完成任务所需要的时间为tt=2544

12、000.6+144001.2+33801.2+3801.2+1.2=73638.29s，即20.455小时三个小组完成任务所需的时间分别为19.71小时，19.71小时，20.455小时。即整个任务完成所需时间为20.455小时。先完成任务的队员需要等后来的队员44.7分钟。说明10人一组的小组搜索任务较重，我们想到可以由先前两个小组分担一批任务，这样既缩短了等待时间，也缩短了整个任务完成的时间，于是我们优化设计出了模型二。（图五）小组1和小组2完成任务需要的时间为tt=518000.6+7801.2+7801.2+38001.2+27801.2=72600s即20.16小时。小组3完成任务需

13、要的时间为tt=2444000.6+144001.2+33801.2+3801.2+1.2+21.2=72304.96s,即20.08小时模型二中10人小组比模型一10人小组少用了大约22.5分钟，比20人小组的两个小组多用了大约27分钟。从而完成整个任务所需要的时间缩短到20.08小时。四，模型的评价与改进1模型的评价模型的优点由简单到复杂,但重复的越来越少,完成搜索任务所用时间越来越少；能够保证通讯畅通。该模型避免了队员盲目搜索，遇到突发事情，可以在第一时间通知到指挥部，也比较好统一指挥，特别适合于大面积的搜索范围。路线规则，覆盖了全部的搜索区域，队员分散与集合速度较快，模型的缺点方案拐弯较多,拐弯处耗时较多，搜索死板，队伍成员搜索耗时不等，在分散，集合，经过拐角时，先完成的队员需要等待后完成的队员，拖缓了任务进程，问题二中的20人小组与10人小组无法在同一时刻完成所分配的任务。2模型的推广以上几种方案的思想都可以地面搜索领域应用.3模型