淺談矩形地面搜索區(qū)域搜索路徑的優(yōu)化方案

馬翠玲

地震搜救主要是指迅速搜索與營救由于地震造成的建筑物破壞而被壓埋人員的舉動(dòng)。地震發(fā)生后，展開救援的第一步是搜索及定位，即尋找被埋壓人員并準(zhǔn)確判斷其位置的過程。對(duì)區(qū)域進(jìn)行快速全面的搜索，以最短的時(shí)間或最大的可能找到搜索目標(biāo)。在搜救隊(duì)被分配到任務(wù)區(qū)后，面對(duì)大規(guī)模的建筑物倒塌區(qū)域，隨機(jī)對(duì)所有的建筑物進(jìn)行搜索行動(dòng)顯然有些盲目。為了能夠達(dá)到搜索目的，搜索隊(duì)員首先要明確搜索目標(biāo)的特征，搜索區(qū)域，根據(jù)搜索裝備的情況，進(jìn)行力量的合理部署及制定隊(duì)伍的行進(jìn)路線。網(wǎng)格搜索屬于常見的人工搜索方式，即將倒塌區(qū)域分成若干個(gè)網(wǎng)格區(qū)域，搜索人員由若干人組成一組，分配一個(gè)網(wǎng)格進(jìn)行搜索。

下面對(duì)搜索過程中常見的單個(gè)矩形區(qū)域中搜索路線的行走方案進(jìn)行討論。

現(xiàn)有一搜索分隊(duì)將對(duì)某一矩形區(qū)域進(jìn)行搜索。假設(shè)搜索時(shí)平均行進(jìn)速度為vl，不搜索時(shí)的平均行進(jìn)速度為v2，搜索半徑為r，搜索人員直行時(shí)搜索寬度為2r。

首先將該矩形區(qū)域以2r為邊長劃分為若干正方網(wǎng)格，不足2r的部分按照2r計(jì)算。取每個(gè)正方網(wǎng)格中心點(diǎn)為v將任意兩中心點(diǎn)之間的距離看成相應(yīng)正方網(wǎng)格的邊長e。構(gòu)成了網(wǎng)格圖G(v，e)，如圖1所示。

為簡化問題，做如下假設(shè)。

對(duì)每個(gè)局部方格區(qū)域內(nèi)部進(jìn)行均勻搜索；將點(diǎn)陣中的點(diǎn)看成頂點(diǎn)，行進(jìn)的起點(diǎn)和終點(diǎn)位量不受限制。

則搜索問題轉(zhuǎn)化為尋找經(jīng)過每點(diǎn)一次且僅一次的最短路徑問題，即為求Hamilton回路問題。Hamilton回路問題是指給定n個(gè)點(diǎn)及n個(gè)點(diǎn)兩兩之間的距離(或權(quán)數(shù))，求一條回路，使之經(jīng)過所有的點(diǎn)。且經(jīng)過每個(gè)點(diǎn)僅一次，而整條回路(也稱路徑或邊界)的總距離(或總權(quán)數(shù))最小。這是一個(gè)NP-完全問題，該問題的最優(yōu)精確解法有許多種，常用的解法為啟發(fā)式算法，即指從最優(yōu)的必要條件出發(fā)，設(shè)計(jì)一個(gè)有效算法，使之求出的解滿足這些必要條件。

假設(shè)搜索隊(duì)員在某點(diǎn)處的搜索區(qū)域?yàn)閳A形，為了避免復(fù)雜的計(jì)算及便于搜索方案的順利實(shí)施，制定出如圖2所示的“S”形路線搜索法。

搜索隊(duì)員從起始點(diǎn)開始沿某一排網(wǎng)格直行搜索，搜索至邊界處，180°折回，再沿下一排網(wǎng)格繼續(xù)直行搜索，如此進(jìn)行，直至搜索結(jié)束，形成“s”型往返搜索路線。

由圖2可見，“S”形搜索路線簡單，便于實(shí)施，但它也有其局限性。將局部方格區(qū)域放大，見圖3，圖中陰影部分無法被搜索，形成了搜索盲區(qū)。可見這種搜索方式并不能覆蓋整個(gè)搜索區(qū)域。如何解決盲區(qū)的搜索問題經(jīng)過研究。在180°折回處，做出如圖4所示的修正方案。

一條直行路徑的最后一個(gè)網(wǎng)格搜索完成后，不立即轉(zhuǎn)入下一個(gè)網(wǎng)格，而是沿著對(duì)角線方向直行至A點(diǎn)(從網(wǎng)格中心至A點(diǎn)的距離為)，然后從點(diǎn)A直行到下一個(gè)網(wǎng)格的B點(diǎn)搜索，再由B點(diǎn)返回網(wǎng)格中心，轉(zhuǎn)入下一條直行路徑繼續(xù)搜索。修正后，消除了搜索盲區(qū)，整個(gè)搜索區(qū)域可實(shí)現(xiàn)完全覆蓋。

搜索隊(duì)員在實(shí)際執(zhí)行搜索任務(wù)時(shí)，經(jīng)常會(huì)遇到要求搜索結(jié)束后返回出發(fā)點(diǎn)，以便于搜救力量的統(tǒng)籌安排。

假設(shè)從矩形區(qū)域的一角出發(fā)，結(jié)束后返回出發(fā)點(diǎn)，為了使搜索路徑最短，可根據(jù)兩個(gè)搜索方向上網(wǎng)格數(shù)的奇偶性，選擇優(yōu)先搜索方向。

(1)兩個(gè)搜索方向上網(wǎng)格數(shù)均為偶數(shù)的矩形區(qū)域，優(yōu)先搜索方向不受限制，可任選一方向先搜索，對(duì)另一個(gè)方向則保留一排網(wǎng)格留作最后返回時(shí)搜索。

(2)兩個(gè)搜索方向上網(wǎng)格數(shù)一個(gè)為奇數(shù)，一個(gè)為偶數(shù)的矩形區(qū)域，選擇網(wǎng)格數(shù)為奇數(shù)的方向?yàn)閮?yōu)先搜索方向，對(duì)網(wǎng)格數(shù)為偶數(shù)的方向保留一排網(wǎng)格留作最后返回時(shí)搜索。

(3)兩個(gè)搜索方向上網(wǎng)格數(shù)均為奇數(shù)的矩形區(qū)域，則選擇網(wǎng)格數(shù)較少的方向作為優(yōu)先搜索方向。

以上搜索方案簡浩明了，通俗易懂，在實(shí)際搜索操作中易于實(shí)施，同時(shí)也避免了復(fù)雜的優(yōu)化計(jì)算。

在可用的人力、物力資源及手段有限的條件下，有效地利用現(xiàn)有資源、制定合理地搜救力量部署方案和搜索路線對(duì)提高搜救效率、在更短的時(shí)間內(nèi)挽救更多災(zāi)民的生命有著重要的作用。