关于地面搜索问题的简化模型
关于地面搜索问题的简化模
地面搜索问题对现实的防灾抗灾工作,起着不可忽视的作用。在抗灾救灾的紧急情况
下，制订搜索队伍的行进路线，对预定区域进行快速的全面搜索显得尤为重要。
本文建立了关于“地面搜索”问题的数学模型：首先采用图解法对所给平地矩形区域划
分成小的矩形单元；其次，对每个搜索队员的搜索面积做了分析，区域划分的原则是将总
长与总宽按照队员组合所得的最大搜索距离的整数倍进行分解，把整个区域划分成相互不
重叠的带状（矩形）区域；再次，综合最大流思想进行分析推理，得到了搜索队员的最佳
组合就是并排搜索；最后利用最短路径方法，得出最优的结果。依据这个结果为“地面搜
索”提供了一个比较清晰直观的最短路径安排方式。
问题叙述：对于一个平地矩形目标区域，大小为 11200 m×7200 m，需要进行全境
搜索。搜索时要求如下：出发点在区域中心；搜索完成后需要进行集结，结束点在左侧短
边中点；每个人搜索时的可探测半径为 20 m，搜索时平均行进速度为 0。6 m/s；不需搜
索而只是行进时,平均速度为 1。2 m/s。每个人带有 GPS 定位仪、步话机，步话机通讯半
径为 1000 m。搜索队伍若干人为一组,有一个组长，组长还拥有卫星电话。每个人搜索到
目标，需要用步话机及时向组长报告，组长用卫星电话向指挥部报告搜索的最新结果。
现在有如下问题需要解决：假定有一支 20 人一组的搜索队伍,拥有 1 台卫星电话。请
设计一种耗时最短的搜索方式，求出搜索完整个区域的时间，看能否在 48 小时内完成搜
索任务；如果不能完成，需要增加到多少人才可以完成。
模型的建立与算法：
一、模型假设
搜索人员的通讯良好,每个人单独向组长汇报无干扰；搜索人员的身体素质及搜索能
力相同；不考虑余震带来的其他干扰,如道路中断或阻塞；该区域中天气对搜索任务无明
显影响；每个搜索人员所带食物及生活用品等充足；该搜索组在搜索途中无滞留。
二、模型的建立
1。最大流问题的基本假设为:
(1)网络中所有流起源于一个节点,这个节点叫做发点 S(也称为源或始点)；所有的流终
止于另一个节点,这个节点叫做收点 E(也称为汇或终点)；
(2)其余所有的节点叫做转运点；论文联盟
(3)通过每一段弧的流只允许沿着弧的箭头所指的方向流动。由发点发出的所有弧背向
发点,而所有终结于收点的弧都指向收点；
(4)最大流问题的目标是使得从发点到收点的总流量的大小可以用两种等价的方法来衡
量,分别叫做从出发点出发的流量和进入收点的流量。
2。根据最大流的定义，与本题目对比，可以将人数的多少与流量的大小相类比，让
所有的搜索人员在划分的区域内并排搜索，保证搜索区域不重复并且搜索时间尽可能的少
。搜索人员的路径是一个有向的流动，单位时间内通过的人数不可能超过最多人数，每个
拐点处通过的人数也应相等，流入的流量应等于流出的流量，即为实际的人数。
三、模型的分析与求解
以 20 人为一组的搜索队伍，最短搜索路径为图 1 所示
