9.5最优搜索策略本节研究在探测手段和探测搜索力的最优配置是现代搜索论中最活跃的研究课题之一资源受到限制的情况下，怎样获得最大的搜索效果，或为了达到一定的搜索效果，怎样才能最大限度地节约探测资源等这些问题在实践中显然具有重要应用价值9.5.1随机搜扫与均匀搜扫效率的比较对位于一个给定区域中的静止目标进行搜索，通常采用的策略有两种：随机搜扫和均匀搜扫我们来比较这两种搜索策略的效率1）随机搜扫设目标在面积为S的区域内是等概分布的随机搜扫时，观察者在区域中随机游走，航线各线段元的位置和指向是随机且相互独立的设航线总长为L,将L分成N个等长的线段元：L，有「丄=L那么在-：t时间间隔里发现目标的概率应为N这里，W为搜扫宽度，v为观察者的速度在随机搜索时，各段是否发现是相互独立的，故在整个航线上发现目标的概率为PlW：L)SL/.LPl-expeWSL^^exp(WsVSS(9—44)这里，t为总搜索时间将（9-44）式与（9—18）式比较，可得发现率_Wv-S于是，发现目标所需的平均时间(9—45)Wv(9—46)即随机搜扫时，只要观察者搜扫平均面积达到目标分布面积S,—般就能搜索到这个目标2）均匀搜扫。
它又称平行搜扫，这是因为平行搜扫是保证均匀搜扫的最简单的方法均匀搜扫的要点在于对目标分布面积S中的每个点只覆盖一遍，扫过的区域便不再重复搜扫这样，在t时刻的发现率将不再是式（9—45）中的_WvS在t时刻已搜扫的面积是Wvt,剩余的面积是S—Wvt,故此时的搜扫率为“、WvWv/S（t）:S—Wvt1-Wvt/S由（9—16）式，t时间后对目标的发现概率为(9—47)tP(t)=1-exp[-0Wv/S1_(Wv/S)tdt](9—48)WvtT的概率密度为当t_S时，P（t）=1，这时已搜索完全部区域故首次发现目标时间Wv,0:::t<_SWvWvP(t)=<~S0,其它发现目标所需平均时间SE[T]二Jtp(t)dt二腭WvtdtSS2Wv(9—49)与（9—46）式比较后可知，在其它条件相同时，均匀搜索发现目标所需时间是随机搜索时的一半9.5.2最优搜索的线性规划模型例7为了勘探某种矿藏，派了几类搜索组，每组配备有不同数量的m种仪器设第j类搜索组（j=1,2,…，n）每组配第i类（i=l,2,…，m仪器ay台，第i类仪器总数为b台，在勘探中，每个第j类搜索组可勘察面积为Cj，问应配备各类搜索组多少个,才能使勘察的总面积最大？解：设应配备第j类勘察组Xj个，可得线性规划：nmaxS八Cjxj（9—50）j吕"n为aijXj兰bii=1,2,■■；m约束于$j二jj?j兰0,取整数=j=1,2，…,n我们可用单纯形法解这个线性规划。
9.5.3最优搜索的动态规划模型例8在某个区域寻找沉没的船只，该区域由四个小区域组成在第j个小区（j=I，2,3,4）发现沉船的期望数Mj（m）取决于分配在这些区域中的搜索者个数m,如表9—1所示现有5个搜索者问怎样分配这5个搜索者，才能使打捞上的沉船数最多？解：我们把这个问题当作一个多级决策问题，利用动态规划法求解我们逐步对前4个区、前3个区、前两个区、前一个区分配搜索者今用xj表示到过程结束还剩下j步时搜索者的个数我们利用动态规划的原理，从后往前逐级决策X-!代表第1区被剩下的搜索者个数（距分配结束还有1步）X1可取的状态是X-!=0,1,2,3,4,5这时分配在第1区的最优搜索者个数是状态X1的函数，记为X0（X1），这时在该区上发现船只数的最大值也是状态X1的函数，记为fjxj显然，这时的最优选择是:Xo(Xi)=Xi,fi(xj=Mi(xJ我们将此结果记入表9—2表9-1mM1(m)M2(m)M3(m)M4(m)0000010.6000.4000.5000.30021.0800.6400.7500.51031.4640.7840.8750.65741.7700.8700.9380.76052.0160.9220.9690.832表9-2n=1X1x0(x1)f1(X1)000110.6221.08331.464441.77552.016X2是距分配结束还有2步时的状态，代表分配给第1区、第2区的搜索者个数之和，X2可取的状态数有X2=0,1,2,3,4,5。
这时分配到第1区上搜索者的最佳人数是X2的函数,记为X1(X2)，对应于X2，在第1、第2区上的最优决策使在这两个区上搜索到的沉船数最多，这个最大值记为f2(X2)，有f2(x2)=max[M2(x2-xjf1(X1)]0_%_x2列表9-3,可得出X1(x2)和f2(x2)X3是距分配结束还有3步时的状态，代表分配给第1区、2区、3区的搜索者个数之和X3可取的状态数有X3=0,1,2,3,4,5这时分配到第1、第2区上搜索者的最佳人数是X3的函数，记为X2(X3)，对应于X3，在第1、第2、第3区上的最优决策应使在这三个f3(X3)=[M3(X3-X2)f2(X2)]列表9—4,可得出X2（X3）和f3（X3）表9-3n=2X2XiX1(X2)f2(X2)012345000010.4+00+0.610.620.64+00.4+0.60+1.0821.0830.784+00.64+0.60.4+1.080+1.46421.4840.87+00.784+0.60.64+1.080.4+1.4640+1.46431.86450.922+00.87+0.60.784+1.080.64+1.4640.4+1.770+2.01642.17表9-4n=3X3X2X2(X3)f3(X3)012345000010.5+00+0.610.620.75+00.5+0.60+1.0811.130.875+00.75+0.60.5+1.080+1.4821.5840.938+00.875+0.60.75+1.080.5+1.480+1.86431.9850.969+00.938+0.60.875+1.080.75+1.480.5+1.8640+2.1742.364表9-5n=4X4X3X3(X4)f4(X4)01234550.832+00.76+0.60.657+1.10.51+1.580.3+1.980+2.36452.364X4是距分配结束还有4步时的状态，代表分配给第1区、2区、3区、4区的搜索者个数之和。
X4可取的状态只有X=5，这时分配到第1、第2、第3区上搜索者的最佳个数记为X3（X4），对应于X4，在这4个区上搜索到沉船的最大值记为f4（X4），有0乞x3
由于上面数学规划的目标函数和约束条件都是可微凸函数，故我们把上述模型称为凸规划模型，这个规划可用库恩一一图克（Kuhn—Tuker）条件解出下面我们给出这个规划的解：解方程1_ajbj(9—56)Z丄In—=1jbj-(，.吋)可以证明，满足（9—56）式的’（：：：0）唯一存在然后，将积ajbj,j=1,2，…，n从大到小排序，不妨设次序仍为则序列从某一项开始可能va1b1,a2b2,,anbn入则凸规划（9—54）、（9—55）的最优解为1_ajbj一ln,ajbja—九Xj(9—57)=5"jj0这个结果是可以理解的，为了得到很高的搜索效率，应对ajbj较大的区域分配较多的搜索资源，而对ajbj较小的区域，可少分配甚至不分配搜索资源9.5.5最优搜索的对策模型有些搜索态势是以两方的利益冲突为特征的这种冲突的主要表现在于：一方力图发现对方，而另一方力图避免被对方发现双方为了达到本身正好相反的目的而采取一些措施，而每一方的措施所取得的效果都与对方选择的行动方式有关描述这种对抗搜索态势的模型我们一般采用对策模型它的三个基本要素是局中人，策略和赢得例如，甲是猎人，乙是猎物，甲采用策略:i，乙采用策略］时，甲的赢得是甲对乙的发现概率Rj,乙的支付是乙被甲发现的概率P,若甲、乙双方的策略都是有限多个测这样便构成了一个二人有限零和对策，即矩阵对策:甲乙（目标）（搜索者）1'n:-1P11D・・・P2Pn2aP21D・・・P22F2n：mPm1D・・・Pm2Pmn我们可用对策论的方法解这个矩阵对策，甲、乙双方的最优策略可能是最优纯策略,可能是最优混合策略。