最优搜索问题的一个模型

叶文敏

【摘 要】研究了离散时间和空间中运动目标最优搜索问题，给出了使得成功探测到搜索目标的可能性达到最大值的一个模型及其算法。

【关键词】最优搜索；模型

1.搜索理论简介

最优搜索理论是关于如何以一种“最佳”的方式寻找某个事先己确定的对象（通常被称之为“搜索目标”）的理论。通常最优搜索问题由下面三个基本的要素 所构成：

1.1目标的位置和移动路径的概率分布函数

对搜索目标在某个时刻的初始位置以及它在随后所做的各种运动的可能性大小等信息进行量化即可获得目标的概率分布函数。

1.2探测函数

探测函数的定义为：设Z（t）是搜索者在时刻t的位置，则有：

b（x，t，z，v，）Δt=p在（t，t+Δt）中找到目标|X（t）=x，Z（t）=z，V（t）=v+0（Δt）

一般情况下用b（x，t，z）表示探测函数，第四个变量V不需要写出来。

探测函数给出了将投入到某个区域的搜索资源（如时间）的数量与给定搜索目标位于该区域时成功探测到该目标的可能性大小联系起来的函数关系，它与目标的运动模型紧密相关。

1.3对可用资源的约束条件

一般情况下搜索者可用于搜索目标的资源（或者能力）是有限的。

给出了探测函数和目标位置的概率分布函数之后，我们就可以计算出针对搜索空间的各个区域中的搜索资源的每一种分配方法，所对应的成功探测到搜索目标的概率是多大。所以最优搜索问题的解就是找到一种对于搜索资源（比如搜索时间）的最佳分配方法，使得成功探测到搜索目标的可能性达到最大值，或者使得成功探测到目标所需的代价（即资源的消耗）的期望值达到最小值，本文仅仅讨论离散时间和空间中使得成功探测到搜索目标的可能性达到最大值的情形。

2.问题的模型

2.1静止目标的最优搜索问题

静止目标的最优搜索问题其实就是求解一个最优化问题：

D（f）=b（x，f（x））p（x）dx

约束条件：f（x）dx≤C（f）

即求解使得D（f）最大的f（x）

这里X是搜索空间（比如平面），F表示平面上的全体非负可积函数的集合，fF为搜索资源分配函数，p（x）表示目标的概率分布，D（f）是发现目标的探测概率，C（f）是关于f的成本函数。通常b（x，z）=1-e-Rz，R为扫描频率，表示搜索的实施时间间隔。

2.2运动目标的最优搜索问题

假设目标在m个盒子中运动，把T分为n个时间间隔，目标在每一个时间间隔内占据一个盒子，则令搜索空间为 C=1，2，...，m，T=1，2，...，n，C和T为σ-有限可测集，测度分别为v和τ，目标的运动是一个随机过程 X=Xt：t≥0，其中一条样本路径表示为ω=（ω，ω，...，ω）∈C；p：C→0，1。p（ω）为路径ω的概率分布，令Ω=ω∈

C：p（ω）>0 （n=1时，这就是一个静止目标最优搜索问题）。假定目标的运动与搜索者的行为之间相互独立，不同时间间隔内搜索相互独立。

定义=ξ（c，i）：c∈C，i=1，2，...，n为一个搜索策略，并且假定探测函数b为指数型函数[2]，即：

b（c，i，ξ）=1-exp（-W（c，i）ξ（c，i））

b（c，i，ξ）表示按照ξ这种搜索策略i时刻目标在c盒子中能被找到的概率，W（c，i）表示当目标在i时刻位于c盒子中时的搜索能力（比如扫描宽度）。一般情况下，搜索资源的投放速度是有限制的，也即存在一个与i有关的搜索资源上限L（i）

所以在整个搜索过程中没有搜索到目标的概率为：f（ξ）=E

exp=p（ω）exp

………………………………①

约束条件为：ξ（c，i）≥0，ξ（c，i）≤L（i） ………………………………………②

要求解使得f（ξ）最小的ξ.

3.模型的求解

选择一个时刻i并且确定除了时刻i以外的其他所有时间的搜索均为失败的，那么相应的最优搜索问题就转化成了在这些条件下导致的静止目标搜索问题。

假设η：C→[0，∞） 为一个v可测函数，对∶?c∈C，令

rep（ξ，η，i）=η（c）.........j=i

ξ（c，j）......j≠i

如果选择一组满足η（c）≥0（c∈C）和η（c）≤L（i）的η，使得：

prep（ξ，

η

，i）minprep（ξ，η，i）

则称η是ξ在时间i的再分配函数[3]。

引入再分配函数的意义在于沟通随机运动目标问题与静止目标问题的关系。

令p（c，i，ξ）表示在除i时刻以外的任何其它时刻均搜索不到目标，且目标在i时刻位于盒子c中的概率，则：

p（c，i，ξ）=exp

-W（ω

，j）ξ（ω

，j）

这样①就变成了：

f（rep（ξ，η，i））=E（rep（ξ，η，i））=P（c，i，ξ）exp（-W（c，i）η（c））

………………③

③显然可以看作是分布函数为p（?，i，ξ）的静止目标搜索问题。

由上面的讨论可以给出一个迭代算法：

E（ξ）=rep（ξ，η，i）

ξ=E（ξ） i=1，2，...，n j=0，1，2，......

具体的步骤为：

给定充分小的正数ε；

①j=0；从i=1到i=n

计算 ξ=i（ξ）

②如果f（

ξ）-f（ξ

）<ε，则停止，最优分配就是ξ（n+1）j。

③j=j+1，回到步骤①。

这样就会得到一个迭代序列（ξ，ξ，...） ，可以证明这个序列是收敛的，利用这个算法可编制计算机程序解决实际问题。

【参考文献】

[1]StoneLD.Theory of OptimalSearch[M].Mathematics in Science and Engineering，New York：Academic Press，1975，118.

[2]朱清新.最优搜索理论及其应用[J].科学出版社，2005，27（4）：39-49.

[3]Brown S S.Optimal Search for a Moving Target in Discrete Time and Space[J].Operations Research，1980，28：1275-1289.