浅谈矩形地面搜索区域搜索路径的优化方案

马翠玲

地震搜救主要是指迅速搜索与营救由于地震造成的建筑物破坏而被压埋人员的举动。地震发生后，展开救援的第一步是搜索及定位，即寻找被埋压人员并准确判断其位置的过程。对区域进行快速全面的搜索，以最短的时间或最大的可能找到搜索目标。在搜救队被分配到任务区后，面对大规模的建筑物倒塌区域，随机对所有的建筑物进行搜索行动显然有些盲目。为了能够达到搜索目的，搜索队员首先要明确搜索目标的特征，搜索区域，根据搜索装备的情况，进行力量的合理部署及制定队伍的行进路线。网格搜索属于常见的人工搜索方式，即将倒塌区域分成若干个网格区域，搜索人员由若干人组成一组，分配一个网格进行搜索。

下面对搜索过程中常见的单个矩形区域中搜索路线的行走方案进行讨论。

现有一搜索分队将对某一矩形区域进行搜索。假设搜索时平均行进速度为vl，不搜索时的平均行进速度为v2，搜索半径为r，搜索人员直行时搜索宽度为2r。

首先将该矩形区域以2r为边长划分为若干正方网格，不足2r的部分按照2r计算。取每个正方网格中心点为v将任意两中心点之间的距离看成相应正方网格的边长e。构成了网格图G(v，e)，如图1所示。

为简化问题，做如下假设。

对每个局部方格区域内部进行均匀搜索；将点阵中的点看成顶点，行进的起点和终点位量不受限制。

则搜索问题转化为寻找经过每点一次且仅一次的最短路径问题，即为求Hamilton回路问题。Hamilton回路问题是指给定n个点及n个点两两之间的距离(或权数)，求一条回路，使之经过所有的点。且经过每个点仅一次，而整条回路(也称路径或边界)的总距离(或总权数)最小。这是一个NP-完全问题，该问题的最优精确解法有许多种，常用的解法为启发式算法，即指从最优的必要条件出发，设计一个有效算法，使之求出的解满足这些必要条件。

假设搜索队员在某点处的搜索区域为圆形，为了避免复杂的计算及便于搜索方案的顺利实施，制定出如图2所示的“S”形路线搜索法。

搜索队员从起始点开始沿某一排网格直行搜索，搜索至边界处，180°折回，再沿下一排网格继续直行搜索，如此进行，直至搜索结束，形成“s”型往返搜索路线。

由图2可见，“S”形搜索路线简单，便于实施，但它也有其局限性。将局部方格区域放大，见图3，图中阴影部分无法被搜索，形成了搜索盲区。可见这种搜索方式并不能覆盖整个搜索区域。如何解决盲区的搜索问题经过研究。在180°折回处，做出如图4所示的修正方案。

一条直行路径的最后一个网格搜索完成后，不立即转入下一个网格，而是沿着对角线方向直行至A点(从网格中心至A点的距离为)，然后从点A直行到下一个网格的B点搜索，再由B点返回网格中心，转入下一条直行路径继续搜索。修正后，消除了搜索盲区，整个搜索区域可实现完全覆盖。

搜索队员在实际执行搜索任务时，经常会遇到要求搜索结束后返回出发点，以便于搜救力量的统筹安排。

假设从矩形区域的一角出发，结束后返回出发点，为了使搜索路径最短，可根据两个搜索方向上网格数的奇偶性，选择优先搜索方向。

(1)两个搜索方向上网格数均为偶数的矩形区域，优先搜索方向不受限制，可任选一方向先搜索，对另一个方向则保留一排网格留作最后返回时搜索。

(2)两个搜索方向上网格数一个为奇数，一个为偶数的矩形区域，选择网格数为奇数的方向为优先搜索方向，对网格数为偶数的方向保留一排网格留作最后返回时搜索。

(3)两个搜索方向上网格数均为奇数的矩形区域，则选择网格数较少的方向作为优先搜索方向。

以上搜索方案简浩明了，通俗易懂，在实际搜索操作中易于实施，同时也避免了复杂的優化计算。

在可用的人力、物力资源及手段有限的条件下，有效地利用现有资源、制定合理地搜救力量部署方案和搜索路线对提高搜救效率、在更短的时间内挽救更多灾民的生命有着重要的作用。