周小玩

【摘要】 地震使震區(qū)地面交通和通訊系統(tǒng)嚴(yán)重癱瘓。救災(zāi)指揮部緊急派出多支小分隊(duì)，到各個(gè)指定區(qū)域執(zhí)行搜索任務(wù)，以確定需要救助的人員的準(zhǔn)確位置。本文討論在目標(biāo)區(qū)域內(nèi)如何制定全境搜索路徑，使得所耗時(shí)間最短。運(yùn)用Matlab編制文中兩種搜索算法程序，其可自動(dòng)進(jìn)行全境搜索并繪制出詳細(xì)的搜索路徑圖。

【關(guān)鍵詞】 “回”字路徑搜索 無縫連接轉(zhuǎn)彎 并行搜索

一、網(wǎng)絡(luò)搜索問題分析

為了達(dá)到搜索耗時(shí)最短，我們應(yīng)該盡量使得單位時(shí)間探測(cè)的面積最大，重復(fù)探測(cè)的面積最少，而且必須保證搜索隊(duì)通信暢通。從而，考慮采用單列前行的探測(cè)方法。由于隊(duì)伍的長(zhǎng)度較長(zhǎng)，轉(zhuǎn)彎的方法就至關(guān)重要，選擇不同的轉(zhuǎn)彎方案，其轉(zhuǎn)彎時(shí)間差距會(huì)較大。探測(cè)時(shí)間只和人數(shù)及探測(cè)速度有關(guān)，從而轉(zhuǎn)彎時(shí)間是節(jié)約耗時(shí)的關(guān)鍵點(diǎn)。

二、單組隊(duì)伍單區(qū)域搜索

單列行進(jìn)最少彎路搜索：在此種搜索法中，單組隊(duì)伍排成一列進(jìn)行搜索，隊(duì)員的間隔距離為2r，其足夠可以保證步話機(jī)的通訊，亦可保證隊(duì)員與組長(zhǎng)之間的通訊。

由于搜索終點(diǎn)所在位置會(huì)隨著格子行數(shù)的改變而相應(yīng)地發(fā)生變化，當(dāng)格子行數(shù)為奇數(shù)時(shí)且l ≥h（如果lh，其終點(diǎn)出現(xiàn)在起始點(diǎn)的左側(cè)相鄰格子內(nèi)，此時(shí)分散時(shí)間最少，集結(jié)時(shí)間最長(zhǎng)。

三、單列隊(duì)伍“回”字路徑搜索

“回”字路徑搜索，顧名思義，用一環(huán)套一環(huán)的回環(huán)覆蓋目標(biāo)區(qū)域，在此搜索法中，由于各回環(huán)間可以用一條路徑進(jìn)行連接，那么，搜索的方向可以采用順時(shí)針、逆時(shí)針交替的方式進(jìn)行。采用一種邊探索邊轉(zhuǎn)彎的無縫連接轉(zhuǎn)彎法，順時(shí)針、逆時(shí)針交替進(jìn)行搜索，從而可以抵消掉內(nèi)圈與外圈的時(shí)間差，可有效的利用模型一中的等待時(shí)間，使得該模型的等待時(shí)間盡可能的小，能保證隊(duì)員們通訊暢通。

四、多組隊(duì)伍并行分區(qū)搜索

有多組隊(duì)伍參與搜索時(shí)，須對(duì)目標(biāo)區(qū)域進(jìn)行分塊，每組搜索一個(gè)區(qū)域，則此時(shí)是一個(gè)并行的搜索過程，且互相獨(dú)立（每組可獨(dú)立將搜索情況報(bào)告給指揮部門）。故區(qū)域劃分的好壞直接影響到搜索耗時(shí)。

命題1.區(qū)域只能是縱向劃分。

證明：因?yàn)樘綔y(cè)時(shí)間只由探測(cè)半徑和參與搜索的人數(shù)相關(guān)，轉(zhuǎn)彎時(shí)間是個(gè)定值（轉(zhuǎn)彎方式確定的情況下）。由于集結(jié)點(diǎn)在短邊左側(cè)中心位置，那么，無論是采用最少彎路搜索還是“回”字路徑搜索，其終點(diǎn)都會(huì)落在離集結(jié)點(diǎn)較近的區(qū)域。那么如果橫向劃分區(qū)域，就是直接增加了其集結(jié)時(shí)間。從而增加其搜索時(shí)間。故只能是縱向劃分區(qū)域。一般說來，區(qū)域的縱、橫向劃分與其集結(jié)點(diǎn)相關(guān)。

隊(duì)伍分組進(jìn)行搜索的目的是為了讓所有組的搜索并行化，從而減少整個(gè)區(qū)域的搜索時(shí)間。那么最理想狀態(tài)下，所有組對(duì)整個(gè)區(qū)域的搜索時(shí)間應(yīng)等于單個(gè)組搜索其所在區(qū)域的時(shí)間（分組人數(shù)相同）。當(dāng)然這種情況在實(shí)際中是不可能存在的。根據(jù)以上算法可以得出以下區(qū)域搜索路徑，如圖8。圖8中，1號(hào)區(qū)域的圖形高度比目標(biāo)區(qū)域高度稍大，三個(gè)圖形的合的長(zhǎng)度也比目標(biāo)區(qū)域長(zhǎng)度稍大。

五、后記

模型有嚴(yán)格的數(shù)學(xué)推導(dǎo)過程，并給出了算法的具體步驟及Matlab程序，模型具有較好的實(shí)用性及通用性。只需修改較少的幾個(gè)參數(shù)便可將其推廣到任意目標(biāo)區(qū)域的搜索。模型使用圖形仿真的方式對(duì)其進(jìn)行檢驗(yàn)，以保證其可靠性。