搜尋論

搜尋論 search theory 研究尋找目標的計畫與實施過程的理論與方法的學科。目的是以最大的可能或最短的時間找到特定的目標。第二次世界大戰期間，為了滿足軍事上有效使用飛機和軍艦來尋找敵方潛艇的緊迫需要，開始形成搜尋論這門獨特的學科。

基本介紹

• 中文名：搜尋論
• 外文名：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