搜索論

　　關於在資源和探測手段受到限制的情況下，如何設計尋找某種特定目標的方案，並如何加以實施的理論和方法，目的是希望以最大的可能或（和）最短的時間找到該目標。它是運籌學初期的重要研究物件之一。第二次世界大戰期間盟軍為瞭克服敵方潛艇對海上交通的嚴重威脅，建立瞭反潛戰運籌小組從事搜索水下潛艇的數學分析。當時成果發表於1951年由P.M.莫爾斯和G.E.金佈林合著的《運籌學方法》一書中，1953～1957年B.O.庫普曼在美國《運籌學》雜誌上撰文“搜索論”，對之作瞭系統統的理論綜合。至今，搜索論的發展已超出瞭傳統的軍事領域、在地下或海域的資源勘探、海上捕魚、邊防巡邏、搜捕逃犯、檢索書籍、尋找故障等非軍事領域中也得到瞭應用。

　　搜索過程的目的，首先是在用於搜索的資源和手段已經給定之下查明特定目標有多大可能存在於某個區域內，並以最大的可能或最短的時間找到它，通常用發現目標的概率、期望個數、期望面積、體積或期望搜索時間來描述；其次在於測量目標的狀態參數，如速度、位置等，用適當的測量準確度來描述。搜索論主要研究前者。

　　搜索要素　實現搜索目的依賴於三個搜索要素。

　　①目標特性　包括目標的幾何形狀、大小、個數，被發現的特征以及位置或運動的變化規律等。在搜索論中，通常把目標的存在看作離散空間或連續空間中的點（有些特定目標則需要用有限區域來描述），它對搜索者而言，是不能預知的，如果目標是靜止的，一般用均勻的、正態的或其他合適的概率分佈函數(簡稱分佈)來描述；如果目標是運動的，則當目標運動與搜索者行動無關時，可用馬爾可夫過程、維納過程來描述，當目標運動依賴於搜索者的行動策略時稱為對抗搜索，可用對策論來描述。

　　②探測特性　包括搜索者（或被搜索目標）所使用的探測手段發現目標存在信息的概率特征。在離散觀察中，假設探測手段一次觀察發現位於x點的目標的概率為g_x，則在各次觀察獨立的假設下，n次觀察發現它的概率為

。在連續觀察中，設在時間 t(≥0)內沒有發現位於 x點的目標條件下，而在 t以後單位時間內發現它的概率為 r _x( t)，則在時間 T＞0內發現目標的概率為

式中 g _x或 r _x亦稱探測手段的發現率，可由試驗數據經過統計處理獲得。上述兩種發現目標的概率表示式中蘊涵著探測發現規律的如下一般特性，即發現目標概率既是目標相對位置又是搜索時間的函數，而且它雖是搜索時間 T或觀察次數 n的遞增函數，但是，這種遞增的變化率卻是嚴格遞減的。在搜索論中，把具有以上性質的發現概率函數稱為正規的，即若記它為 b( x， z)，則它滿足： b( x，0)＝0。 b對 z的偏導數是連續的、正的和嚴格遞減的，其中 x表示目標位置， z表示在 x上使用的某種搜索力。

　　③搜索力分配方式　包括探測手段數量、所耗費的搜索時間在空間上的分配。從而構成為搜索策略，可以搜索者的運動軌跡或搜索區間序列、搜索時間序列、搜索力密度等表示。

　　主要內容　可分為兩類：一類是描述性問題，即根據已知的目標（靜止和運動的）位置分佈、發現概率函數和特定的搜索策略（搜索力分配計劃）構成搜索模型，計算發現目標的效果；一類是最優化問題，即根據已知的目標（靜止或運動的）位置分佈或行動策略、發現概率函數，對於給定的總搜索力，求解搜索效果達到最大的搜索策略，或者對於給定的搜索效果求解代價最小的搜索策略。下面是這兩類問題的一些典型結果。

　　隨機遭遇　假設在平面上有一批運動速度為u、位置與搜索者的航向差角都服從均勻分佈的目標；搜索者以等速υ按直線運動，所使用探測手段對目標的作用距離為R。目標進入以搜索者為中心、半徑為R的圓域內時，稱為搜索者遭遇目標。現求搜索者在不同方向角β下遭遇目標的概率。對此，B.O.庫普曼最早利用幾何概率，推導瞭著名的遭遇概率公式，它可以用圖形概略地表示。

　　圖

中，用淺綠色標註的輻線表示目標方向角 β取值 ～360°，用黑色標註的閉曲線表示速度比參數 m＝υ/ u取值0～∞，用紅色標註的同心圓表示遭遇目標概率 P _m( β)取值0～0.5。搜索者位於圖的中心，且航向為0°。

　　B.O.庫普曼的推導原理：搜索者遭遇目標的概率，等於目標出現在被搜索者可能發現的區域內的概率。這一原理為解決一大類描述性搜索效果的計算問題奠定瞭基礎，得到瞭許多的推廣應用。

　　隨機搜索　即考慮對靜止目標的搜索。假設在面積為S的區域D內的目標位置服從均勻分佈；搜索者在D中進行瞭N次隨機的不重疊探測，每次探測的面積為α，且Nα=A，A/S┚1，則搜索者發現目標的概率為

稱為隨機搜索公式，其中 A/ S為覆蓋系數。在此模型中，目標位置服從均勻分佈的假設，說明搜索者所瞭解的目標信息最小；搜索者采用隨機探測方式的假設，說明尋找行動的盲目性最大。如果搜索者能獲得目標位置分佈的更多信息，並且采取適應於該分佈的搜索方式，則必能增大發現概率。因此，隨機搜索的發現概率是一切搜索方式的發現概率的下界。

　　馬爾可夫搜索　考慮對運動目標的搜索，假設目標在平面R²上的位置x=x(t)是一個擴散過程，這過程取決於目標在時刻t位於x條件下到時刻τ(τ≥t)位於y的轉移概率密度ψ(x，t；y，τ)。搜索者知道目標的初始位置x₀=x(t₀)服從某個分佈ρ(x₀)，且使用一種馬爾可夫型的探測手段進行搜索，該手段的發現概率γ(x，t)與t以前發現目標的經歷無關。令p(y，t)表示搜索者直到t前沒有發現目標，且目標位於y的聯合概率密度。A.R.西爾沃證明瞭p(y，t)滿足下列積分方程

初始條件為 p( x ₀，0)= ρ( x ₀)，從而給出搜索者在時刻 t發現目標概率為 。馬爾可夫搜索為估計搜索運動目標效率提供瞭解析計算方法。

　　最優一致搜索計劃　通常在某平面區域D內搜索目標時，投入的總搜索力是限定的，它是時間t的函數，且隨t遞增。搜索者在時刻t對D內每一點處的單位面積上分配搜索力，在上述搜索力的約束條件之下，求一個搜索計劃使得時刻t前總的發現目標概率為最大，這計劃就稱為最優一致搜索計劃。

　　突防對策　它起源於第二次世界大戰中如何組織飛機在海峽中的巡邏，以阻止敵方潛艇從水下偷渡的問題。假設甲、乙兩方對峙，在長度為L的直線段S兩側。在S的每一點x上，甲方按照總兵力的百分率(巡邏密度)ψ(x)部署巡邏兵力：

乙方按照概率密度 φ( x)安排偷越地點： φ( x)≥0， x∈ S， 。已知乙方偷越者在 x點遭遇巡邏兵條件下偷越失敗的概率為 p( x)，那麼甲方如何部署有利的巡邏密度 ψ( x)。作為對策來處理，可以定義如下的平均巡邏成功率 F作為甲方的贏得

甲方力圖選擇 ψ使 F最大，乙方力圖選擇 φ使 F最小。甲方巡邏成功意味著乙方偷越的失敗，故可證明最優混合策略為 ，其中 甲方贏得為

　　實際的搜索問題是多種多樣的，可以應用規劃論、對策論、馬爾可夫決策論或其他的運籌學方法來解決，對於復雜情況，還需利用電子計算機的模擬技術求得近似的最優搜索策略。

　　

參考書目

　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.