[计算机]2008C___地震搜索优化问题分析与评述.doc
《[计算机]2008C___地震搜索优化问题分析与评述.doc》由会员分享,可在线阅读,更多相关《[计算机]2008C___地震搜索优化问题分析与评述.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小时不能完成搜索搜索时,需要增加人数,增加
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 2008 C_ 地震 搜索 优化 问题 分析 评述
链接地址:https://www.31doc.com/p-1990499.html