关于搜索论介绍

[拼音]：sousuolun

[外文]：search theory

关于在资源和探测手段受到限制的情况下，如何设计寻找某种特定目标的方案，并如何加以实施的理论和方法，目的是希望以最大的可能或（和）最短的时间找到该目标。它是运筹学初期的重要研究对象之一。第二次世界大战期间盟军为了克服敌方潜艇对海上交通的严重威胁，建立了反潜战运筹小组从事搜索水下潜艇的数学分析。当时成果发表于1951年由P.M.莫尔斯和G.E.金布尔合著的《运筹学方法》一书中，1953～1957年B.O.库普曼在美国《运筹学》杂志上撰文“搜索论”，对之作了系统的理论综合。至今，搜索论的发展已超出了传统的军事领域、在地下或海域的资源勘探、海上捕鱼、边防巡逻、搜捕逃犯、检索书籍、寻找故障等非军事领域中也得到了应用。

搜索过程的目的，首先是在用于搜索的资源和手段已经给定之下查明特定目标有多大可能存在于某个区域内，并以最大的可能或最短的时间找到它，通常用发现目标的概率、期望个数、期望面积、体积或期望搜索时间来描述；其次在于测量目标的状态参数，如速度、位置等，用适当的测量准确度来描述。搜索论主要研究前者。

搜索要素

实现搜索目的依赖于三个搜索要素。

（1）目标特性 包括目标的几何形状、大小、个数，被发现的特征以及位置或运动的变化规律等。在搜索论中，通常把目标的存在看作离散空间或连续空间中的点（有些特定目标则需要用有限区域来描述），它对搜索者而言，是不能预知的，如果目标是静止的，一般用均匀的、正态的或其他合适的概率分布函数(简称分布)来描述；如果目标是运动的，则当目标运动与搜索者行动无关时，可用马尔可夫过程、维纳过程来描述，当目标运动依赖于搜索者的行动策略时称为对抗搜索，可用对策论来描述。

（2）探测特性 包括搜索者（或被搜索目标）所使用的探测手段发现目标存在信息的概率特征。在离散观察中，假设探测手段一次观察发现位于x点的目标的概率为gx，则在各次观察独立的假设下，n次观察发现它的概率为。在连续观察中，设在时间t(≥0)内没有发现位于x点的目标条件下，而在t以后单位时间内发现它的概率为rx(t)，则在时间T>0内发现目标的概率为

式中gx或rx亦称探测手段的发现率，可由试验数据经过统计处理获得。上述两种发现目标的概率表示式中蕴涵着探测发现规律的如下一般特性，即发现目标概率既是目标相对位置又是搜索时间的函数，而且它虽是搜索时间T或观察次数n的递增函数，但是，这种递增的变化率却是严格递减的。在搜索论中，把具有以上性质的发现概率函数称为正规的，即若记它为b(x，z)，则它满足：b(x，0)＝0。b对z的偏导数是连续的、正的和严格递减的，其中x表示目标位置，z表示在x上使用的某种搜索力。

（3）搜索力分配方式 包括探测手段数量、所耗费的搜索时间在空间上的分配。从而构成为搜索策略，可以搜索者的运动轨迹或搜索区间序列、搜索时间序列、搜索力密度等表示。

主要内容

可分为两类：一类是描述性问题，即根据已知的目标（静止和运动的）位置分布、发现概率函数和特定的搜索策略（搜索力分配计划）构成搜索模型，计算发现目标的效果；一类是最优化问题，即根据已知的目标（静止或运动的）位置分布或行动策略、发现概率函数，对于给定的总搜索力，求解搜索效果达到最大的搜索策略，或者对于给定的搜索效果求解代价最小的搜索策略。下面是这两类问题的一些典型结果。

假设在平面上有一批运动速度为 u、位置与搜索者的航向差角都服从均匀分布的目标；搜索者以等速υ按直线运动，所使用探测手段对目标的作用距离为R。目标进入以搜索者为中心、半径为R的圆域内时，称为搜索者遭遇目标。现求搜索者在不同方向角β下遭遇目标的概率。对此，B.O.库普曼最早利用几何概率，推导了著名的遭遇概率公式，它可以用图形概略地表示。

图

中，用浅绿色标注的辐线表示目标方向角β 取值～360°，用黑色标注的闭曲线表示速度比参数m＝υ/u取值0～∞，用红色标注的同心圆表示遭遇目标概率 Pm(β)取值0～0.5。搜索者位于图的中心，且航向为0°。

B.O.库普曼的推导原理:搜索者遭遇目标的概率，等于目标出现在被搜索者可能发现的区域内的概率。这一原理为解决一大类描述性搜索效果的计算问题奠定了基础，得到了许多的推广应用。

即考虑对静止目标的搜索。假设在面积为S的区域D 内的目标位置服从均匀分布；搜索者在D中进行了N 次随机的不重叠探测，每次探测的面积为α，且Nα=A，A/S┚1，则搜索者发现目标的概率为称为随机搜索公式，其中A/S为覆盖系数。在此模型中，目标位置服从均匀分布的假设，说明搜索者所了解的目标信息最小；搜索者采用随机探测方式的假设，说明寻找行动的盲目性最大。如果搜索者能获得目标位置分布的更多信息，并且采取适应于该分布的搜索方式，则必能增大发现概率。因此，随机搜索的发现概率是一切搜索方式的发现概率的下界。

考虑对运动目标的搜索，假设目标在平面R 2上的位置x=x(t)是一个扩散过程，这过程取决于目标在时刻t位于x 条件下到时刻τ(τ≥t)位于y的转移概率密度ψ(x，t；y，τ)。搜索者知道目标的初始位置x0=x(t0)服从某个分布ρ(x0)，且使用一种马尔可夫型的探测手段进行搜索，该手段的发现概率γ(x，t)与t以前发现目标的经历无关。令p(y，t)表示搜索者直到t前没有发现目标，且目标位于y的联合概率密度。A.R.西尔沃证明了p(y，t)满足下列积分方程

初始条件为p(x0，0)=ρ(x0)，从而给出搜索者在时刻t发现目标概率为。马尔可夫搜索为估计搜索运动目标效率提供了解析计算方法。

通常在某平面区域D 内搜索目标时，投入的总搜索力是限定的，它是时间t的函数，且随t递增。搜索者在时刻t对D内每一点处的单位面积上分配搜索力，在上述搜索力的约束条件之下，求一个搜索计划使得时刻t前总的发现目标概率为最大，这计划就称为最优一致搜索计划。

它起源于第二次世界大战中如何组织飞机在海峡中的巡逻，以阻止敌方潜艇从水下偷渡的问题。假设甲、乙两方对峙，在长度为L的直线段S两侧。在S的每一点x上，甲方按照总兵力的百分率(巡逻密度)ψ(x)部署巡逻兵力：乙方按照概率密度φ(x)安排偷越地点:φ(x)≥0，x∈S，。已知乙方偷越者在 x点遭遇巡逻兵条件下偷越失败的概率为p(x)，那么甲方如何部署有利的巡逻密度ψ(x)。作为对策来处理，可以定义如下的平均巡逻成功率F作为甲方的赢得

甲方力图选择ψ使F最大，乙方力图选择φ使F最小。甲方巡逻成功意味着乙方偷越的失败，故可证明最优混合策略为，其中甲方赢得为

实际的搜索问题是多种多样的，可以应用规划论、对策论、马尔可夫决策论或其他的运筹学方法来解决，对于复杂情况，还需利用电子计算机的模拟技术求得近似的最优搜索策略。

参考书目

1. P.M.Morse and G.E.Kimball，Methods of Operations Research，John Wiley & Sons， New York， 1951.
2. L.D.Stone，Theory of OptiMal Search，Academic Press， New York， 1975.