平地矩形区域上的地面搜索问题
2008年5月12日汶川发生里氏8.0级特大地震，使得震区地面交通和通讯系统严重瘫痪。如何制定搜救队伍的行进路线，在最短的时间内对预定区域进行快速的全面搜索是在此紧急情况下需要解决的重要问题之一。本文旨在研究在一平地矩形区域上的地面搜索问题。
在问题一中，我们首先给出了20人一组的搜索队伍,搜索完整个区域至少需要 个小时这样一个有利的结论。我们先采用圆滚动模型，但会出现队员与组长联系不到的缺点；经分析，采用图论中的赋权连通图法可以改进圆滚动模型的缺点，组长在任何位置都可以联系到所有队员，搜索中不存在重叠现象，且搜索用的时间最短，在赋权连通图用 算法找到最小生成树，在此生成树中采用扩环策略、增环策略、换枝策略的思想，经过调整，采用拐弯、不拐弯两种搜索方法，寻找到20人一组的最佳搜索路线。按此方式，我们得到这样几个结果：
(1)搜索完整个平面矩形区域所用的时间为 小时。
(2)在 小时以内不能完成搜索任务。
(3)在问题二中，我们采用第一、二组各20人，第三组10人的分组方式，给出了分组的均衡度 ，说明分组的均衡度很好。我们根据最小生成树分解原则进行分区域，再次采用扩环策略、增环策略、换枝策略的思想，给出了第一、二组搜索完需要的时间是 ，第三组搜索完需要的时间是 。即50人三组搜索完整个平面矩形区域需要 。最后，给出了一个 双层非线性规划，将其内层目标函数、约束条件构造了 条件，从规划的角度分析了此模型。
图论中的赋权连通图法，将图论，规划，算法有机地结合在一起。
关键词 ：最小生成树 ；均衡度；规划；圆滚动模型
一、 问题重述
1.1背景
2008年5月12日汶川大地震中，震区地面交通和通讯系统严重瘫痪。大家知道救助灾民的黄金时间是72小时，能在短时间内搜索到需要救助的人员得位置，并更快的进行救助是我们的首要任务。救灾指挥部紧急派出多支小分队，到各个指定区域执行搜索任务，以确定需要救助的人员的准确位置。在这种紧急情况下需要解决的重要问题之一是：制定搜索队伍的行进路线，对预定区域进行快速的全面搜索。
1.2简化的搜索问题
我们有一个平地矩形目标区域，需要进行全境搜索。出发点 在区域中心；搜索完成后需要进行集结，集结点 在左侧短边中点。每个人带有GPS定位仪、步话机。搜索队伍若干人为一组,有一个组长，组长还拥有卫星电话。每个人搜索到目标，需要用步话机及时向组长报告，组长用卫星电话向指挥部报告搜索的最新结果。
1.3我们需要解决的问题
（ ）若搜索队伍 人，一组, 台卫星电话。设计耗时最短的搜索方式并求出搜索完整个区域的时间。 若在 小时内不能完成搜索任务，需要增加到多少人才可以完成。
（2）若搜索队伍 人，三组， 台卫星电话。每组可独立将搜索情况报告给指挥部门。设计耗时最短的搜索方式并求出搜索完整个区域的时间。
二、模型假设
假设 搜索目标区域为长 米，宽 米的平地矩形区域，需要进行全境搜索。
假设 每个搜索队员搜索时的可探测半径为 米，搜索时平均行进速度为 米/秒；不需搜索只行进时,平均速度为 米/秒。
假设 步话机通讯半径为 米。
假设 在出发点部署时，等到所有队员都到自己的位置后所有人在同一时间出发。
假设 搜索队员一旦发现目标，直接向组长报告，组长立即向指挥部报告，报告时间为 秒，且不影响搜索工作。
假设 搜索队员一旦发现目标，能够直接定位彼此的相对坐标，并根据自己的 定位仪得到的自身坐标，定出目标的坐标，花费时间为 秒。
三、符号说明与概念
3.1符号说明
---------- 赋权连通图；
----------------- 赋权连通图 的第 个子图；
------------------ 子图 中的最佳回路；
---------------- 边 的边权；
------------------ 点 的边权；
----------------- 最佳回路 的各边权之和；
------------------ 的各点权之和；
--------------------- 搜索每块区域的时间
增加到 人，在47.41小时内可以完成搜索任务。
3.2概念
均衡度： 为该分组的实际时间均衡度，显然 ， 越小，说明分组的均衡度越好；
最大容许均衡度： ；
均衡分组：取定一个 后， 和 满足条件 （其中 ）的分组时一个均衡分组。
四、模型分析
4.1 搜索队员为 人时的思路
4.1.1圆滚动性模型
圆滚动模型是以组长为圆心， 为半径的圆以一定速度向前滚动。
用类比的方法就可以得到 人一起以同一速度向前搜索，覆盖整个矩形区域。我们还给出了一些数据，见附录一。
我们在表中取每个人到各点的时间，绘成每个人的时间——地点图。
为了描述方便我们取1号，2号，20号人员的图在同一图中以不同颜色显示，命令为：
Show[p1,p2,p20]
由离散图联线得到的图证明随着每人路程的增加，图形大致有两两之间距离增加的趋向。而且增加只出现在拐弯处，所有人的时间差成扇形分布，且外侧时间叫大，当到了直行时，时差不变。
在过程中我们可发现1号和20号有时调换位置，当完成一次调换时，时差变化为0。在1-2-3-4、4-5-6-7-8、12-13-14-15出现一次完整调换。
由于20号人员在运动中大多数时间在外侧拐弯，因而造成速度上有较大变化。
同理1号人员速度有较小变化。从地点7-8-9-10-11-12处20号人员一直跑外圈，而1号跑内圈。我们在离散图中得到20号发生巨变（离散图特性造成）。
在16-17-18期间速度发生变化（个人距离安排不同），同样引起巨变。且所有人的时差最小。18-19上直线前进，时差不变。19-20上以1.2米每秒速度在短距离上快速集合，时差变化微弱。
运用此方法可能会出现联系不上组长的情况。可以调节，但是需要很大的工作量，所以我们给出下面的思路。
4.1.2图论模型
在第一问中搜索队只有一组，搜索路线从出发点 出发，沿预定路线遍历全境，最后到集合点 集合。把该问题抽象为赋权连通图问题，即：将探测范围的内切正方形作为研究点，又将以研究点组成的通信范围的内切正方形为研究点 。经过大体运算可以得到沿矩形长分布 个，宽分布 个；得一无向连通图 ， ,两点之间的长度，即为无向图的边权 ，寻找一条最佳路线，即在图 中，找到一条由 点到 点的路，它至少经过所有顶点 一次，使总时间（总路程）最小。
搜索队员为 人时的思路
如果搜索人员分成三组，每组搜索部分区域，且所有区域都搜索到，如果把这些区域都搜索到，即图 中把图分成若干个连通的子图 ，每个子图 中寻找一条包含 的回路 。
完成搜索的时间应是各组搜索时间中最长的时间。故为使搜索效率高，因尽量使各组搜索时间接近，反映在图 中分块使尽量均衡。
五、模型建立与求解
5.1 搜索队伍为 人时的模型
5.1.1一个有利的结论
命题： 人一组的搜索队伍,搜索完整个区域至少需要 个小时。
证明：在不考虑部署、聚集等非搜索行为的情况下， 人为一组部署在矩阵的左上角，沿左侧短边以间距 米的距离一字排开，离最靠近上边的一人距上边为 米，即搜索范围长为 米。由左到右开始搜索，达到最右边时所有人员向下方平移 米，以此类推。由矩形宽度得
可划分为 块地区。
如图1：
图1 不考虑非搜索行为的情况下，分成的9块区域及搜索顺序
由搜索速度和矩形长度得，每块区域需要搜索时间：
秒
搜索完 块区域需要的时间为
秒 秒 小时。
因为这个结论是在绝对理想状态下得到的最下限，现实中是不可能出现的。故模型结果一定大于该极限值 小时。
5.1.2模型建立
把通过各区域的时间示意图抽象为一赋权连通图 ，在赋权图 中， 对应示意图中搜索人员所在地， 表示出发点所在地， 对应示意图中的位置，如果相邻，则边权 =0；如果不相邻，则边权 为间距之差。
建立的数学模型如下：
， ， ，求 中回路 ，使得满足：
（1） ，
（2） ；
（3） （目标为搜索时间最短）
5.1.3模型求解
将平面矩形区域平均分割成数个 的小正方形，得到平面矩形区域长边有 个小正方形，宽边上有 个小正方形。然后将小正方形压缩成一个位于小正方形中心的点。平面矩形图中形成 个点。为了计算方便，我们将在出发点左侧的 个点，先不与考虑。就形成了如图2(a) 的点图。
图2(a) 图G的点集
图2(b) 图G
将图2(a)中的点作为图的顶点，做一图 ，其点与边的关系如图2(b)，因为最小生成树能包含图G中所有顶点 ，考虑最小生成树。根据最小生成树求解 算法：
Step1 将 的 条边按排序， 。取 ， ，
Step2 边 的端点 的标号是否相等？
是：取 ，转Step2； 否：取
Step3 对一切满足 的 ，取
Step4 中的边数 ？
是：算法终止； 否：取 ，转Step2。
我们找到图的最小生成树T如下：
图 最小生成树T
现要对已得到的最小生成树T，变换图形以获得便于解的方案。
(a)扩环策略：
如果在图 中的路径 中，有孤立的枝存在，如图4所示代表1，2，3三个顶点，若 ，则应考虑扩环。
扩环策略还可扩展到多个顶点的情况，如图4所示：扩环后比扩环前其权和变化为 。若 ，则应扩环。当 时，扩环后总时间更少，可进行扩环调整。
(a) 3点扩环图
(b) 多点扩环图
图4 扩环图
(b)增环策略：
若环路上某顶点处长出两条枝，且存在可使两枝成环的边，可考虑增环。增环前后其权和变化为 。若 ，则应增环。当 时，增环后总时间更少，可进行增环调整。
我们对图5进行分析，发现扩环策略条件完全满足，故则两种策略完全适用。
图5 增环图
(c)换枝策略：
若环路上某顶点长出一条枝，而该枝末梢同环路中另一顶点距离接近，可考虑换枝。如图6所示，若
则应考虑换枝。换枝的结果是使被重复的路减少。
图6 换枝图
根据以上的优化策略及分块结果，在 ， 中分别寻找一条从出发点出发，遍历整个区域的最短时间。
在图 中，求三条从出发点回到出发点的路 ，满足 为 中经过点的集合，使得 最小，且 与 相差不大。
结合圆滚动模型调整可得最优图为图7。
图7 搜索路线
搜索分析：当以 人为一组搜索时， 人在中间以间隔为 米纵向分开，即 人的搜索范围为 米，且 人在到达各自的位置上后， 人在同一时刻向前搜索，在拐弯处 人同时搜索到边上，然后再平移 米到下一个要搜索的正方形上。
搜索时搜索方法可分为两种：一种为不拐弯时的搜索方法；另一种为拐弯时的搜索方法。
(一)不拐弯时的搜索方法为：不拐弯时把正方形分为三部分，左右各 米，中间为 米，搜索时左边 米以 米/秒的速度行进，中间 米以 米/秒的速度行进，右边的 米以 米/秒的速度行进。搜索图为图8(a)。
(二) 拐弯时的搜索方法为：在第一个正方形按不拐弯的搜索方法搜到矩形的边界然后把 人按次序不变的方法平移到下一个正方形的边界上，然后再按不拐弯的方法进行搜索。搜索图为图8(b)。由返回点到出发点的图为图9。
(a)
(b)
图8 搜索图
图9 返回图
5.1.4模型结果
结论一：搜索完整个平面矩形区域所用的时间为 小时。
搜索时间的计算分成如下几步：
(1)在出发点的部署时间：把 人按纵向以间距为 米的平均距离分开，时间 秒；
(2)在不拐弯时搜索完一个正方形所用的时间： 秒；
(3)在拐弯时搜索完一个弯所用的时间： 秒；
(4)搜索完除出发点左侧 个点外的点后回到出发点的时间：
秒；
(5)在回到集结点的那条边上时再回到集结点所用的时间： 秒；
(6)由图 可得，除去出发点左侧的 个点后，图上有 个拐弯处，有 个不拐弯的正方形。所以除去出发点左侧的 个点后由出发点再回到出发点所用的时间为 ；
(7) 搜索完成出发点左侧的 个点再回到集结点所需的时间为 ；
(8)所以搜索完整个矩形区域所用的时间为 小时。
结论二：在 小时以内不能完成搜索任务。
由于在假设 中假设所有队员在同一时间出发，在这其中离出发点近的队员到达自己的位置后，离出发点远的队员还没到达自己的位置，所以离出发点近的队员就有一段时间在等离出发点远的队员，所以如果没有假设 的话，我们上边做的时间 小时还可以缩小，但是在出发点出最近的队员与最远的队员出发的时间间隔不到 秒，所以上边算法得出的时间无论怎么缩小也不会小于 小时。
而且我们的算法算出的时间是最小的时间，所以在 小时以内不能完成搜索任务。
结论三：增加到 人，在47.41小时内可以完成搜索任务。
20人搜索完整个矩形区域需要48.47小时，若要在48个小时内完成工作，则至少需要增加1人即21 人，命名增加的人为圈内自由人，他先在1轨道以 米/秒的速度前进，搜索人员以 米/秒的速度搜索，自由人行进到 的路程时开始搜索，恰好与1轨道的搜索人员在该区域边界处相遇，然后自由人转向2轨道，以 米/秒的速度前进，以后的运动路线与前一个轨道相同，按照上述方法自由人依次补完20个人的路线，然后再从20轨道依次补向前一个轨道，总共补6次，而且中间不会出现与队长失去联系的情况，每次补380米，省时 秒，即1.06小时，所以21人可以用47.41小时搜索完整个区域。
5.2 搜索队伍为 人时的模型
5.2.1 模型建立
50人搜索7200米宽的矩形区域，每人可以搜索宽度为40米，则平均每人搜索的趟数为 ，因为最后一名搜索队员完成任务的时间决定最终搜索时间，所以每人搜索的趟数越接近3.6越省时，若按18，18，14或16，16，18的方案分组，则会导致误工现象，若按既横向搜索也纵向搜索，则一定至少会有一组距离集合点远，这样有效工作效率就会降低，导致耗时增加，综上分析可得按第一组20人，第二组20人，第三组10人的方法分组横向搜索会比较合理。
按以 人为一组搜索时的数据整个大矩形可分为 个小正方形，即为 个点，由上述分析， 人以 的分法分为三组，这 个点可以按 的比例分给这三个组，每组可分 ， ， ，分区域时把 人组分在离出发点近的那一个区域，由于 人组与 人组搜索相同距离时 人组所用的时间要长，所以这 个点就分为 ，按生成树分解原则分区域，
(1)分解点为出发点或尽可能接近出发点。
(2)分解所得的三个子图所包含的顶点数尽可能接近 ，
尽量使分解所得子图为连通图，尽量使子图与出发点最短路上的点在该子图内，尽量使各子图的点在子图内部形成环路。
再经过上面所用的扩环策略，增环策略和换枝策略等有效优化原则再结合圆滚动模型得到的分图如下所示：
图10 三组的搜索方式
5.2.2 模型求解
第一，二组搜索所用时间
由图 可知 人组是上下对称的，所以 人组的时间算一个就可以了，则由图可得拐弯处有 个，其余的 未拐弯，所以在图中搜索所用时间为：
搜索完回到途中路线后回到集结点所用的时间为：
；
在出发点部署所用时间为：
；
所以 人组从出发点到集结点所用的总时间为：
。
第三组搜索所用时间 毕业论文http://www.youerw.com/
人组搜索时的模型和 人组的模型一样，把 人组的区域分为 个 的小正方形。可以用第一问的方法找到一个用时最短的树。
搜索完一个不拐弯的小正方形所用的时间为：
搜索完一个拐弯的小正方形所用的时间为：
中间以 米每秒的速度行进的时间为：
所以 人组所用总时间为：
人搜索完所用时间
小时。
5.2.3 均衡度分析
均衡度 ，给定最大容许均衡度 ；显然 。
比 小很多，说明分组的均衡度很好；这样的分组是一个均衡分组。
5.2.4用规划模型分析
设非线性规划 和线性规划 的可行解集合分别为 ， 。
利用规划 的内层目标函数和约束条件，设拉格朗日函数 ，构造 条件，得到非线性规划
其可行解集合为 。
根据最优化理论 ，可以得到如下命题：
(a) ；
(b) 规划 的最优值不超过规划 的最优值；
(c) 规划 的Pareto最优值不超过规划 的最优值。
以上结论来自文献[1][5][7]，我们构造此搜索问题的规划模型，将搜索区域分成上下对称的两部分，先考虑上部分的搜索情况，下部分的与上部分的相同。上部分的搜索情况规划为
其中 ，
变量 是指编号为 的人，占了多少条道，且这些道均相连。这是 非线性规划，约束条件是线性的，可行解集合为凸集。
将规划 变形得到
这是非线性规划，其中约束条件中含有线性约束，以及由二次函数开平方根形成的非线性约束。由命题 可知，规划 的可行解集合是规划 的可行解集合的子集合，且前者的Pareto最优值不超过后者的最优值。
利用规划 中内层目标函数和约束条件，得到 条件
计算 ，构造规划
规划 的可行解集合是非线性规划 可行解集合的子集合，规划 的Pareto最优值不超过规划 的最优值。
优 、模型的评价与扩展
6.1 模型评价
本问题从实际出发，分析了多种情况，将矩形分成若干小区域，结合圆滚动思想，将搜索示意图转化为赋权连通图，建立了最小生成树的模型，并进行了理论论证和实例论证。还利用均衡度判定出合理的人数组合，进而达到了优化设计的目的。除此之外又用到规划模型，有成熟的理论基础和相应的专业软件支持，可信度高。而且在整个搜索过程中，每位搜索人员都能够直接与队长联系，及时将情况报告给队长，并且20个人中队长位置无限制，从而保证了信息传递的快速性和高效性。
6.2 模型扩展
上述解法是解决简化的搜索问题，如果考虑到实际问题就不适合了。如果把上面的采用圆滚动的方法改进为每个人从一个圆的圆心以 米/秒前进到另一个圆的圆心，然后就在圆内判断并停留若干秒，其速度为 米/秒。 毕业论文http://www.youerw.com/
此方法的好处为：
（一） 这样就可以很好的利用两个速度 米/秒和 米/秒。
（二） 可以和实际的问题联系起来。在实际问题中，任务管理员可以根据建筑物和场地来判断需要救助的人的数量，不同场所幸存人数不同，我们可以将美国和新西兰的研究成果综合后得表 ，表 。
建筑类型 幸存者数量/平方米 安全幅度/平方米
公共集会场所 人
或
学校 人
或
医院 人
或
商业 人
或
办公室/政府机关 人
或
公共安全 人
或
住宅区 人
或
工业 人
或
仓储 人
或37.1~83.6
表 各建筑类型中的幸存者数量和安全幅度
建筑物用途 人的数量
学校 人/教室
医院 人/床位
住宅 人/居室
其他 人/停车位
表 建筑物用途及里面人的数量
（三）可以把三文空间简化为二文空间来求解，这里可以把建筑物压为平地，把人压人也看为平地。
（四）可以缩短搜索时间。