最优区域搜索模型

魏东平 赵洪雅

深圳职业技术学院，广东深圳 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）