關(guān)于地面搜索問題的簡化模型關(guān)于地面搜索問題的簡化模型

趙宇杰 周玲 梁曄 王哲慧 李志乾

【摘要】本文建立了關(guān)于“地面搜索”問題的簡潔數(shù)學(xué)模型。將平地矩形區(qū)域劃分成小的矩形帶狀，綜合最大流思想進(jìn)行分析推理，得到了搜索隊(duì)員能夠采用的最短路徑搜索方式。此模型原理簡單，方法實(shí)用。

【關(guān)鍵詞】最大流問題；最短路徑；帶狀區(qū)域

地面搜索問題對現(xiàn)實(shí)的防災(zāi)抗災(zāi)工作,起著不可忽視的作用。在抗災(zāi)救災(zāi)的緊急情況下，制訂搜索隊(duì)伍的行進(jìn)路線，對預(yù)定區(qū)域進(jìn)行快速的全面搜索顯得尤為重要。

本文建立了關(guān)于“地面搜索”問題的數(shù)學(xué)模型：首先采用圖解法對所給平地矩形區(qū)域劃分成小的矩形單元；其次，對每個(gè)搜索隊(duì)員的搜索面積做了分析，區(qū)域劃分的原則是將總長與總寬按照隊(duì)員組合所得的最大搜索距離的整數(shù)倍進(jìn)行分解，把整個(gè)區(qū)域劃分成相互不重疊的帶狀（矩形）區(qū)域；再次，綜合最大流思想進(jìn)行分析推理，得到了搜索隊(duì)員的最佳組合就是并排搜索；最后利用最短路徑方法，得出最優(yōu)的結(jié)果。依據(jù)這個(gè)結(jié)果為“地面搜索”提供了一個(gè)比較清晰直觀的最短路徑安排方式。

問題敘述：對于一個(gè)平地矩形目標(biāo)區(qū)域，大小為11200 m×7200 m，需要進(jìn)行全境搜索。搜索時(shí)要求如下：出發(fā)點(diǎn)在區(qū)域中心；搜索完成后需要進(jìn)行集結(jié)，結(jié)束點(diǎn)在左側(cè)短邊中點(diǎn)；每個(gè)人搜索時(shí)的可探測半徑為20 m，搜索時(shí)平均行進(jìn)速度為0。6 m/s；不需搜索而只是行進(jìn)時(shí),平均速度為1。2 m/s。每個(gè)人帶有GPS定位儀、步話機(jī)，步話機(jī)通訊半徑為1000 m。搜索隊(duì)伍若干人為一組,有一個(gè)組長，組長還擁有衛(wèi)星電話。每個(gè)人搜索到目標(biāo)，需要用步話機(jī)及時(shí)向組長報(bào)告，組長用衛(wèi)星電話向指揮部報(bào)告搜索的最新結(jié)果。

現(xiàn)在有如下問題需要解決：假定有一支20人一組的搜索隊(duì)伍,擁有1臺(tái)衛(wèi)星電話。請?jiān)O(shè)計(jì)一種耗時(shí)最短的搜索方式，求出搜索完整個(gè)區(qū)域的時(shí)間，看能否在48小時(shí)內(nèi)完成搜索任務(wù)；如果不能完成，需要增加到多少人才可以完成。

模型的建立與算法：

一、模型假設(shè)

搜索人員的通訊良好,每個(gè)人單獨(dú)向組長匯報(bào)無干擾；搜索人員的身體素質(zhì)及搜索能力相同；不考慮余震帶來的其他干擾,如道路中斷或阻塞；該區(qū)域中天氣對搜索任務(wù)無明顯影響；每個(gè)搜索人員所帶食物及生活用品等充足；該搜索組在搜索途中無滯留。

二、模型的建立

1。最大流問題的基本假設(shè)為:

(1)網(wǎng)絡(luò)中所有流起源于一個(gè)節(jié)點(diǎn),這個(gè)節(jié)點(diǎn)叫做發(fā)點(diǎn)S(也稱為源或始點(diǎn))；所有的流終止于另一個(gè)節(jié)點(diǎn),這個(gè)節(jié)點(diǎn)叫做收點(diǎn)E(也稱為匯或終點(diǎn))；

(2)其余所有的節(jié)點(diǎn)叫做轉(zhuǎn)運(yùn)點(diǎn)；

(3)通過每一段弧的流只允許沿著弧的箭頭所指的方向流動(dòng)。由發(fā)點(diǎn)發(fā)出的所有弧背向發(fā)點(diǎn),而所有終結(jié)于收點(diǎn)的弧都指向收點(diǎn)；

(4)最大流問題的目標(biāo)是使得從發(fā)點(diǎn)到收點(diǎn)的總流量的大小可以用兩種等價(jià)的方法來衡量,分別叫做從出發(fā)點(diǎn)出發(fā)的流量和進(jìn)入收點(diǎn)的流量。

2。根據(jù)最大流的定義，與本題目對比，可以將人數(shù)的多少與流量的大小相類比，讓所有的搜索人員在劃分的區(qū)域內(nèi)并排搜索，保證搜索區(qū)域不重復(fù)并且搜索時(shí)間盡可能的少。搜索人員的路徑是一個(gè)有向的流動(dòng)，單位時(shí)間內(nèi)通過的人數(shù)不可能超過最多人數(shù)，每個(gè)拐點(diǎn)處通過的人數(shù)也應(yīng)相等，流入的流量應(yīng)等于流出的流量，即為實(shí)際的人數(shù)。

三、模型的分析與求解

以20人為一組的搜索隊(duì)伍，最短搜索路徑為圖1所示。