《[计算机]C地震搜索优化问题分析与评述.doc》由会员分享，可在线阅读，更多相关《[计算机]C地震搜索优化问题分析与评述.doc（6页珍藏版）》请在三一办公上搜索。
1、地震搜索优化问题分析与评述 肖华勇(西北工业大学应用数学系，西安，710072)摘要：本文介绍2008年高教社杯全国大学生数模竞赛C题“地面搜索”题的评卷情况，首先概括地介绍了这个问题的背景、评卷要点、问题的解决方法和答卷中存在的问题。最后给出了解决这个问题的一种优化路线和计算结果。关键词：地面搜索；一笔画；横向搜索；纵向搜索1.地面搜索问题的综合评述1.1 问题的背景2008年的5.12汶川大地震震惊了中国，也震惊了世界。在地震发生后，一个重要的问题就是搜索和求援。特别是山村被掩埋后，与外界的通讯中断，更需要进行全面搜索和救援。如5.12大地震中，15名空降兵在茂县灾区从5000米高空成功空
2、降后，连续个昼夜冒着多次余震，翻越了4座3000多米高的山峰，徒步220公里，先后在7个乡55个村庄侦察灾情，向上级报告重要灾情30多批次，为指挥部指挥部队开进和部署抗震救灾提供了科学的信息依据。地震中的搜索问题是一个很复杂的问题，因为实际的地形很复杂，有河流、山川，峡谷，有的地方还没有现成的道路，因此搜索难度很大。但在我们的竞赛中，不可能把问题搞得如此复杂，只是借助地震的背景，提出优化路线的搜索问题。在实际的搜索中，只要人力足够，通常采用的是地毯式搜索，这样可以保证把每一片地方都搜索到。因此我们的搜索问题主要基于地毯式的搜索，要求排成一排，把每一个地方都搜索到。1.2评卷的基本要点 地面搜索
3、问题对于乙组的参赛学生来说，是一个易懂，好下手，方法灵活，越做越有味的题目，因此选择该题的学生较多，这也说明不少学生对该题的喜爱吧。但对该问题的最优路线与结果却又不是那么容易获得，有一定难度。在全国评卷过程中主要给出了以下的评判要点：对问题1，为了使搜索时间短,可以综合考虑三个因素：按一笔画原则尽量不走重复路; 尽量不空走; 尽量少改变队形(每次改变队形要空走)。解题中应交待清楚具体的搜索方式(如一字并排前进,每人搜索宽度为220=40米)、具体的行进路线、算出完成搜索的时间(空走与改变行进队形均需要时间)。行进路线的选择可以不同。对自己的方案是否是好方案, 应有可信的讨论。应有明确的计算,说
4、明方案可行。最好对不同情况进行比较。对问题2，在问题一的基础上适当分配人员，分区搜索。要看其分区及行进线路是否合理。应有明确的计算, 并给出解答。两个问题在解答过程中，要注意讨论的完善性，数学表达的清晰性。1.3 问题的解决方法概述该题目有做头，每个参赛者有很大的发挥空间。这也许是该题的魅力所在。论文中发现做法千奇百怪，其搜索方式也很多，有从内向外搜索的，有横向进行搜索的，有纵向进行搜索的，有横向纵向结合搜索的，有先从中心点行进到边界，然后横向或纵向进行搜索的。有的直接进行数字计算，有的针对一般问题进行计算。有的建立一般的优化模型，然后LINGO进行优化计算。这说明参赛者都广开思路，发挥了自己
5、的智慧，得到了锻炼和提高。1.4 存在的问题有的队审题太偏，把人分开独自去搜索，这样不能保证发现目标后立刻向队长报告，不符合题意。有的队把整个平面区域分成几个村庄，然后搜索这几个村庄，这样把整个区域的搜索变成对几个离散点的搜索，把题目简化得太离谱了，显然也违背题意。还有一种解法，是把问题考虑成如何用最少个数的半径为20米的小圆来覆盖矩形区域，搜索路线变成沿小圆之间的连心线进行，每人执行完搜索任务后再沿直线路径行进至集结点。把整个问题变成一个圆的完全覆盖问题，导致搜索过程不能保证题中要求每个人搜索到目标，就用步话机及时向组长报告。这里的报告是直接报告，而不是通过他人间接报告。因此每个人和队长的距
6、离不能超过1000米，而不是每个人1000米内有一个人就可以了。该种解法获得的结果在第一问中增加的人数远远超过最优人数，第二问中完成任务的最少时间也远大于最优时间。尽管这种解法的一些论文数学表达严谨细致，但因题目理解偏离实际，没能获得一个好奖，实在有些遗憾。2 地面搜索问题的优化路线2.1 问题分析与假设 从实际中的搜索问题出发，我们需要假定队伍排成一排进行搜索，每次搜索形成一个矩形（带形）区域。由于整个区域是矩形，因此搜索方式可采用横向或纵向进行搜索，而不要采用斜向搜索。对每个小矩形区域，队伍搜索方式是从头搜索到尾，每个部分都搜索到，搜索的宽度为，为队伍人数。而且要保证每个队员搜索到目标后立
7、刻报告给对长，不能通过其它队员传递，因此对每个队伍的人数是有限制的。 在搜索过程中，我们的目标是尽量快速搜索完整个区域，因此在搜索中尽量不走重复路线，尽量不空走，尽量少拐弯。在搜索过程中，采用横向或纵向搜索，并尽可能将二者结合起来，使搜索完成的时间尽量少。至于倒底采用横向还是纵向，需要根据实际的数据分别进行计算，最后确定出最优路线。在第1问中，通过计算可以得到当采用横向并结合一次纵向搜索，可使搜索完成的时间尽量少。另外，要注意的是，整个区域搜索完成的时间，不会超过队伍没有任何空走和拐弯的理想情况下的时间，该时间是搜索完成时间的下限。当计算出20人在48小时不能完成搜索搜索时，需要增加人数，增加
8、人数后需要重新考虑搜索方式。 对第2问，将50人分成3组。分组后涉及两个问题，一个是考虑三个组的人数如何分配，另一个是考虑每个组搜索的区域如何划分。总的原则是三个组分配的人数如果多则区域较大，人数少则区域较小。各组在自己区域里类似问题1采用尽量不走重复路线，尽量不空走，尽量少拐弯的原则，以达到尽量早搜索完自己的区域。而最后的目标是把整个区域搜索完才算完成任务，因此我们应该尽量使三个组同时搜索完。为了分析求解问题需要给出如下假设：（1）假设区域是连续的，每个地方都要搜索。 (2）假设每个队员搜索到目标后都直接用布话机报告给队长，而不是间接报告。 (3) 假定每次转弯都需要行走一个队长.。 (4)
9、 假定每个人的行走或搜索速度完全一样。（5）假定搜索队伍能够完全按照设计路线搜索或行走。（6）假定队伍都是排成一排搜索，而不管是横向搜索还是纵向搜索。 (7) 假定分组后各组独立搜索，互不影响。 2.2 问题解答概要问题1队伍排成一排搜索，由于每个队员的搜索半径为20米，相邻两个队员的距离则为40米。20人搜索的矩形区域宽度为米搜索完所有区域的最少人数估计：k=总面积/(每人搜索速度搜索宽度时间)(人)20人队伍搜索外所有区域的最少时间为：T=总面积/(每人搜索速度搜索宽度时间)(小时)任何方式的搜索，其所花时间都不能少于该时间。为了使搜索时间短,我想应考虑综合三个原则:按一笔画原则尽量不走重
10、复路;尽量不空走;尽量少拐弯（每拐一次弯就空走一个队长）。 20人的一种最佳搜索路线见图1。 队伍所花时间包括搜索时间，拐弯时间和空走时间。 横向搜索的矩形为7200/800=9个，矩形长度为11200-800=10400米。纵向搜索一个矩行区域，长度为7200米。矩形宽度都为队伍长度800米。搜索所花时间为：小时拐弯10次，所花时间为：小时 空走时间为小时总时间为小时在计算过程中可不考虑队伍打开和收拢所花时间。无论采用何种方式，21人在48小时内完成搜索任务。而22人采用图2所示方式在48小时可以完成任务。 图1 20人的一种最佳搜索路线图图2 22人的一种最佳搜索路线图 纵向搜索的矩形为1
11、1200/880=13个，矩形长度为7200-880=6320米，宽度为880米。最后一个(标号为18)的矩形长度为米。横向搜索一个矩形，长度为11200米，宽度880米。搜索完11号矩形进入 12号矩形需要行走的距离为：DA=米。但在18号矩形空走返回时，不需要走最后80米，因此DA段的80米被抵消，实际空走距离恰好为宽的一半（3600米）。 搜索的距离为：米搜索所花时间为：小时拐弯17次，所花时间为：小时 空走时间为小时总时间为小时因此22人在48小时内可完成任务。问题2 将50人成3组，三组人数为20:10:20。三组搜索路线图如图3所示。第1组20人，搜索第1区，搜索路线从A点出发，依
12、此搜索I1、I2、I3、I4、I5，搜索完直接到达集结地B。第2组10人，搜索第2区，搜索路线从A点出发，依此搜索1,2,8，回到A点后行进到集结地B。第3组20人，搜索第3区，搜索路线从A点出发，依此搜索S1、S2、S3、S4、S5，搜索完直接到达集结地B。 图3 三组最优分区图第1组20人，队长800米，搜索的距离为：米搜索所花时间为：小时拐弯4次，所花时间为：小时空走只有开始进入第1个矩形这段，时间为小时总时间为19.72小时 第3组与第1组完全相同。第2组10人，队长400米，搜索的距离为：米搜索所花时间为：小时拐弯7次，所花时间为：小时 空走为最后从A到B这段，时间为小时总时间为小时
13、由于第1组和第3组搜索完所花时间为19.72小时，第2组搜索完所花时间为20.46小时。因此搜索完整个区域所花时间为20.46小时。另外，由于第2组比第1组多花时间0.74小时，因此还可以优化。可让第2组中间6个小矩形左移一段距离，让I1和S1横向距离增大一些，这样第2组搜索距离减少一点，第1组和第3组搜索距离增大一点，使得三组同时搜索完，这样可使总的时间再减少一些。可将第2组的6个矩形左移距离为优化变量，目标为三个小组同时搜索完。可解得米，三个小组搜索完所花时间都为19.82小时。这样三个小组分工搜索后，可在20小时内完成搜索。 参考文献：1运筹学教材编写组，运筹学M。北京：清华大学出版社，
14、2001。2 姜启源，谢金星，叶俊.数学模型M。北京：高等教育出版社，2003。The Optimal Route of the Problem of Ground-based Searching and Its CommentsXiao Hua-yong （Department of Mathematics. Northwestern Polytechnical university.Xian 710072）Abstract:In this paper,according to the grading process of problem C of 2008 HIGHER EDUCATION
15、 PRESS cup CUMCM,the background of the problem of ground-based searching，the outline grading,the solution methods and existing problems are introduced.Finally,a kind of optimal route and its calculating result is given.Keywords:ground-based searching;unicursal;horizontal searching;vertical searching
