魏東平 趙洪雅

深圳職業(yè)技術(shù)學(xué)院，廣東深圳 218055

最優(yōu)區(qū)域搜索模型

魏東平 趙洪雅

深圳職業(yè)技術(shù)學(xué)院，廣東深圳 218055

本文最小化搜索人員最大搜索時(shí)間和最大搜索距離,并根據(jù)搜索人員搜索能力、裝備等實(shí)際情況建立一系列的約束條件包括最大通訊距離條件,時(shí)間均衡度條件，工作量均衡度條件，搜索全覆蓋遍歷條件，最終建立最優(yōu)區(qū)域搜索模型解決矩形區(qū)域搜索覆蓋問題。

矩形區(qū)域搜索；最大通訊距離；時(shí)間均衡度；工作量均衡度

1、矩形區(qū)域搜索覆蓋問題

有一個(gè)平地矩形目標(biāo)區(qū)域，大小為11200米×7200米，需要進(jìn)行全境搜索。假設(shè)：出發(fā)點(diǎn)在區(qū)域中心；搜索完成后需要進(jìn)行集結(jié)，集結(jié)點(diǎn)（結(jié)束點(diǎn)）在左側(cè)短邊中點(diǎn)；每個(gè)人搜索時(shí)的可探測(cè)半徑為20米，搜索時(shí)平均行進(jìn)速度為0.6米/秒；不需搜索而只是行進(jìn)時(shí),平均速度為1.2米/秒。每個(gè)人帶有GPS定位儀、步話機(jī)，步話機(jī)通訊半徑為1000米。搜索隊(duì)伍若干人為一組,有一個(gè)組長，組長還擁有衛(wèi)星電話。每個(gè)人搜索到目標(biāo)，需要用步話機(jī)及時(shí)向組長報(bào)告，組長用衛(wèi)星電話向指揮部報(bào)告搜索的最新結(jié)果。本文將建立尋找一種耗時(shí)最短的搜索方式。

2、搜索區(qū)域網(wǎng)格化

我們根據(jù)每個(gè)人搜索時(shí)可探測(cè)半徑為20米的條件，把矩形的區(qū)域劃分成50400個(gè)40米×40米的方格并建立直角坐標(biāo)系，這些格子成為搜索人員搜索的目標(biāo)，讓每一個(gè)人去尋找未被搜索的格子，如果遇到已搜索的格子則轉(zhuǎn)向另一方向，如果未被搜索則進(jìn)去搜索，搜索完并標(biāo)識(shí)為已搜索，一直搜索到離集結(jié)點(diǎn)距離最近的格子為止，停止搜索行進(jìn)到集結(jié)點(diǎn)集合。以區(qū)域中心為原點(diǎn)，區(qū)域的長為X軸，區(qū)域?qū)挒閅軸，建立直角坐標(biāo)系，坐標(biāo)系中單位長度等于實(shí)際長度40m。如圖1，則將11200*7200m2的區(qū)域分成了280*180=50400個(gè)40*40m2的正方形格子，每個(gè)格子記作（x，y），那么-140

圖1 搜索區(qū)域網(wǎng)格化

每個(gè)搜索人員都從區(qū)域的中心點(diǎn)S出發(fā)，按照路線，一格一格地搜索，最后到達(dá)集結(jié)點(diǎn)E。那么，搜索完整個(gè)區(qū)域的最短時(shí)間取決于最后一個(gè)到達(dá)集結(jié)點(diǎn)的人，即T＝maxTi，則有最短時(shí)間目標(biāo)函數(shù)：

3、最優(yōu)區(qū)域搜索模型

3.1、最優(yōu)區(qū)域搜索問題約束條件

由于每個(gè)人身上都有步話機(jī)，步話機(jī)的通訊半徑為1000米，當(dāng)搜索到目標(biāo)時(shí)，用步話機(jī)向組長及時(shí)報(bào)告的強(qiáng)條件是每個(gè)人都與組長的最大距離不大于1000米，即

圖2

3.2、最優(yōu)區(qū)域搜索模型

綜上所述，可以建立目標(biāo)函數(shù)和給定的約束條件為：

特殊的，當(dāng)排成一排時(shí)，每個(gè)隊(duì)員之間的距離為40米，保證了兩人距離小于1000（米），而到達(dá)終點(diǎn)的時(shí)間差也會(huì)越小，同樣的每個(gè)隊(duì)員檢測(cè)的面積也盡可能的相等。那么，通過計(jì)算，可得到目標(biāo)函數(shù)

[1]Dongping Wei, Tianli Lei, "The Simple and Equal Algorithm in Graph Coloring Problem of Gerrymandering", JCIT: Journal of Convergence Information Technology, Vol. 6, No. 7, pp.260～267, 2011.

[2]Dongping Wei, Tianli Lei，Hongya Zhao, "Electric vehicles Composite Impacts Index Model", JDCTA:International Journal of Digital Content Technology and its Applications, Vol. 6, No. 10, pp. 326～335,2012

[3] 蘭瑞平. 耗時(shí)最短的搜索方式．?dāng)?shù)學(xué)學(xué)習(xí)與研究，2010.

[4] 熊偉.運(yùn)籌學(xué).機(jī)械工業(yè)出版社[M]，2004.11.78～90.

[5] 熊梅，馬銳.地面固定區(qū)域搜索法的優(yōu)化數(shù)學(xué)模型. 云南財(cái)經(jīng)大學(xué)學(xué)報(bào)(社會(huì)科學(xué)版)，2009年06期.

10.3969/j.issn.1001-8972.2012.16.021

國家自然科學(xué)基金《大規(guī)模微陣列數(shù)據(jù)組的Mata-analysis方法研究》，（編號(hào)：31100958）