周小玩

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

【關鍵詞】 “回”字路徑搜索 無縫連接轉彎 并行搜索

一、網絡搜索問題分析

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

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

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

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

三、單列隊伍“回”字路徑搜索

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

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

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

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

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

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

五、后記

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