最優區域搜索模型

魏東平 趙洪雅

深圳職業技術學院，廣東深圳 218055

最優區域搜索模型

魏東平 趙洪雅

深圳職業技術學院，廣東深圳 218055

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

矩形區域搜索；最大通訊距離；時間均衡度；工作量均衡度

1、矩形區域搜索覆蓋問題

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

2、搜索區域網格化

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

圖1 搜索區域網格化

每個搜索人員都從區域的中心點S出發，按照路線，一格一格地搜索，最后到達集結點E。那么，搜索完整個區域的最短時間取決于最后一個到達集結點的人，即T＝maxTi，則有最短時間目標函數：

3、最優區域搜索模型

3.1、最優區域搜索問題約束條件

由于每個人身上都有步話機，步話機的通訊半徑為1000米，當搜索到目標時，用步話機向組長及時報告的強條件是每個人都與組長的最大距離不大于1000米，即

圖2

3.2、最優區域搜索模型

綜上所述，可以建立目標函數和給定的約束條件為：

特殊的，當排成一排時，每個隊員之間的距離為40米，保證了兩人距離小于1000（米），而到達終點的時間差也會越小，同樣的每個隊員檢測的面積也盡可能的相等。那么，通過計算，可得到目標函數

[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] 蘭瑞平. 耗時最短的搜索方式．數學學習與研究，2010.

[4] 熊偉.運籌學.機械工業出版社[M]，2004.11.78～90.

[5] 熊梅，馬銳.地面固定區域搜索法的優化數學模型. 云南財經大學學報(社會科學版)，2009年06期.

10.3969/j.issn.1001-8972.2012.16.021

國家自然科學基金《大規模微陣列數據組的Mata-analysis方法研究》，（編號：31100958）