| 词条 | 搜索论 |
| 释义 | 搜索论 search theory 研究寻找目标的计划与实施过程的理论与方法的学科。目的是以最大的可能或最短的时间找到特定的目标。第二次世界大战期间，为了满足军事上有效使用飞机和军舰来寻找敌方潜艇的紧迫需要，开始形成搜索论这门独特的学科。 简介战后，B.C.库普曼发表了《搜索论》，总结了一些方法和理论。现在除了军事上的应用之外，搜索方法还用到资源勘探、海上捕鱼、边防巡逻、搜捕逃犯、检索、排障等方面。搜索一般由3个要素组成：①目标的特征，如目标的几何形状，尺寸大小、个数及位置等；②探测特征，如探测手段所获得的信息和概率特征；③搜索力的分配形式，如数量、时间、空间的分配等。根据所获有关信息和概率特征构造相应的模型和策略。常用的搜索方法有随机搜索、马尔可夫搜索、最优一致搜索、滞后搜索、箱盒搜索等。此外还有一些新方法正处于起步阶段，例如主动回避目标的对抗搜索方法，虽然尚未进入实用阶段，却表现出极大的潜力和崭新的思想。 关于在资源和探测手段受到限制的情况下，如何设计寻找某种特定目标的方案，并如何加以实施的理论和方法，目的是希望以最大的可能或(和)最短的时间找到该目标。它是运筹学初期的重要研究对象之一。第二次世界大战期间盟军为了克服敌方潜艇对海上交通的严重威胁，建立了反潜战运筹小组从事搜索水下潜艇的数学分析。当时成果发表于1951年由P.M.莫尔斯和G.E.金布尔合著的《运筹学方法》一书中，1953～1957年B.O.库普曼在美国《运筹学》杂志上撰文“搜索论”，对之作了系统的理论综合。至今，搜索论的发展已超出了传统的军事领域、在地下或海域的资源勘探、海上捕鱼、边防巡逻、搜捕逃犯、检索书籍、寻找故障等非军事领域中也得到了应用。 搜索过程的目的首先是在用于搜索的资源和手段已经给定之下查明特定目标有多大可能存在于某个区域内，并以最大的可能或最短的时间找到它，通常用发现目标的概率、期望个数、期望面积、体积或期望搜索时间来描述；其次在于测量目标的状态参数，如速度、位置等，用适当的测量准确度来描述。搜索论主要研究前者。 搜索要素实现搜索目的依赖于三个搜索要素。 目标特性包括目标的几何形状、大小、个数，被发现的特征以及位置或运动的变化规律等。在搜索论中，通常把目标的存在看作离散空间或连续空间中的点(有些特定目标则需要用有限区域来描述)，它对搜索者而言，是不能预知的，如果目标是静止的，一般用均匀的、正态的或其他合适的概率分布函数(简称分布)来描述；如果目标是运动的，则当目标运动与搜索者行动无关时，可用马尔可夫过程、维纳过程来描述，当目标运动依赖于搜索者的行动策略时称为对抗搜索，可用对策论来描述。 探测特性包括搜索者(或被搜索目标)所使用的探测手段发现目标存在信息的概率特征。在离散观察中，假设探测手段一次观察发现位于x点的目标的概率为g，则在各次观察独立的假设下，次观察发现它的概率为。在连续观察中，设在时间(≥0)内没有发现位于x点的目标条件下，而在以后单位时间内发现它的概率为()，则在时间>0内发现目标的概率为 式中g或亦称探测手段的发现率，可由试验数据经过统计处理获得。上述两种发现目标的概率表示式中蕴涵著探测发现规律的如下一般特性，即发现目标概率既是目标相对位置又是搜索时间的函数，而且它虽是搜索时间或观察次数的递增函数，但是，这种递增的变化率却是严格递减的。在搜索论中，把具有以上性质的发现概率函数称为正规的，即若记它为(x，)，则它满足：(x，0)＝0。对的偏导数是连续的、正的和严格递减的，其中x表示目标位置，表示在x上使用的某种搜索力。 搜索力分配方式包括探测手段数量、所耗费的搜索时间在空间上的分配。从而构成为搜索策略，可以搜索者的运动轨迹或搜索区间序列、搜索时间序列、搜索力密度等表示。 主要内容可分为两类：一类是描述性问题，即根据已知的目标(静止和运动的)位置分布、发现概率函数和特定的搜索策略(搜索力分配计划)构成搜索模型，计算发现目标的效果；一类是最优化问题，即根据已知的目标(静止或运动的)位置分布或行动策略、发现概率函数，对于给定的总搜索力，求解搜索效果达到最大的搜索策略，或者对于给定的搜索效果求解代价最小的搜索策略。下面是这两类问题的一些典型结果。 随机遭遇假设在平面上有一批运动速度为 、位置与搜索者的航向差角都服从均匀分布的目标；搜索者以等速v按直线运动，所使用探测手段对目标的作用距离为。目标进入以搜索者为中心、半径为的圆域内时，称为搜索者遭遇目标。现求搜索者在不同方向角下遭遇目标的概率。对此，B.O.库普曼最早利用几何概率，推导了著名的遭遇概率公式，它可以用图形概略地表示。 图 遭遇概率公式的图示 中，用浅绿色标注的辐线表示目标方向角 取值～360°，用黑色标注的闭曲线表示速度比参数＝v/取值0～∞，用红色标注的同心圆表示遭遇目标概率 P ()取值0～0.5。搜索者位于图的中心，且航向为0°。 B.O.库普曼的推导原理：搜索者遭遇目标的概率，等于目标出现在被搜索者可能发现的区域内的概率。这一原理为解决一大类描述性搜索效果的计算问题奠定了基础，得到了许多的推广应用。 随机搜索即考虑对静止目标的搜索。假设在面积为的区域 内的目标位置服从均匀分布；搜索者在中进行了 次随机的不重叠探测，每次探测的面积为，且=，/1，则搜索者发现目标的概率为称为随机搜索公式，其中/为覆盖系数。在此模型中，目标位置服从均匀分布的假设，说明搜索者所了解的目标信息最小；搜索者采用随机探测方式的假设，说明寻找行动的盲目性最大。如果搜索者能获得目标位置分布的更多信息，并且采取适应于该分布的搜索方式，则必能增大发现概率。因此，随机搜索的发现概率是一切搜索方式的发现概率的下界。 马尔可夫搜索考虑对运动目标的搜索，假设目标在平面 2上的位置x=x()是一个扩散过程，这过程取决于目标在时刻位于x 条件下到时刻(≥)位于的转移概率密度(x，；，)。搜索者知道目标的初始位置x0=x(0)服从某个分布(x0)，且使用一种马尔可夫型的探测手段进行搜索，该手段的发现概率(x，)与以前发现目标的经历无关。令(，)表示搜索者直到前没有发现目标，且目标位於的联合概率密度。A.R.西尔沃证明了(，)满足下列积分方程 初始条件为(x0，0)=(x0)，从而给出搜索者在时刻发现目标概率为。马尔可夫搜索为估计搜索运动目标效率提供了解析计算方法。 最优一致搜索计划通常在某平面区域 内搜索目标时，投入的总搜索力是限定的，它是时间的函数，且随递增。搜索者在时刻对内每一点处的单位面积上分配搜索力，在上述搜索力的约束条件之下，求一个搜索计划使得时刻前总的发现目标概率为最大，这计画就称为最优一致搜索计画。 突防对策它起源於第二次世界大战中如何组织飞机在海峡中的巡逻，以阻止敌方潜艇从水下偷渡的问题。假设甲、乙两方对峙，在长度为的直线段两侧。在的每一点x上，甲方按照总兵力的百分率(巡逻密度)(x)部署巡逻兵力：乙方按照概率密度(x)安排偷越地点：(x)≥0，x，。已知乙方偷越者在 x点遭遇巡逻兵条件下偷越失败的概率为(x)，那么甲方如何部署有利的巡逻密度(x)。作为对策来处理，可以定义如下的平均巡逻成功率作为甲方的赢得 甲方力图选择使最大，乙方力图选择使最小。甲方巡逻成功意味著乙方偷越的失败，故可证明最优混合策略为，其中甲方赢得为 实际的搜索问题是多种多样的，可以应用规划论、对策论、马尔可夫决策论或其他的运筹学方法来解决，对於复杂情况，还需利用电子计算机的模拟技术求得近似的最优搜索策略。 参考书目P. M. Morse and G. E. Kimball， Methods of Operations Research，John Wiley & Sons，New York，1951. L. D. Stone，Theory of Optimal Search，Academic Press，New York，1975. http://140.128.103.1/web/Content.asp?ID=43444 |
| 随便看 |
百科全书收录4421916条中文百科知识，基本涵盖了大多数领域的百科知识，是一部内容开放、自由的电子版百科全书。