贝叶斯搜索理论

维基百科,自由的百科全书
跳转至: 导航搜索

贝叶斯搜索理论利用贝叶斯统计理论搜索失踪物,曾被多次用于搜救失踪的船只。

流程[编辑]

一般的流程如下:

  1. 提出所有关于船只失踪事件的假设。
  2. 针对每一假设,构造船只位置的空间分布概率。
  3. 针对每一位置,假设已知船只位于此处,计算能找到失踪船只的概率分布。在海洋中,这一般取决于水深:在浅水处找到失踪物的机会比在深水处大。
  4. 结合上述两个概率分布,构造整体的搜索成功的概率分布。
  5. 构造搜索路径:始于高概率区,经过居中概率区,最后搜索低概率区。
  6. 在搜索过程中,持续更新上述概率分布。例如,如果在某处未能找到失踪物,那么船只位置分布于此的概率要被降低。这一更新过程需要用到贝叶斯定理

贝叶斯搜索不仅可以综合多个信息来源,而且可以自动估计搜索成功的概率。即使在搜索前,我们可以估计“5天内找到失踪物的概率是65%。在搜索十天后,这个概率会升高到90%。15天后,升高到97%”。如此,在分配搜索资源前可以评估可行性。

數學[编辑]

假定失踪物位于某区域的概率是 p,在此处能搜索成功的概率是 q。如果搜索此处后未能找到失踪物,根据贝叶斯定理,失踪物位于此处的概率被更新为

  p' = \frac{p(1-q)}{(1-p)+p(1-q)} = p \frac{1-q}{1-pq} < p.

对其它区域,如果其原本失踪物在其处的概率是 r,那么这一概率将被更新为

 r' = r \frac{1}{1- pq} > r.

另見[编辑]

參考資料[编辑]

  • Stone, Lawrence D., The Theory of Optimal Search, published by the Operations Research Society of America, 1975
  • Iida, Koji., Studies on the Optimal Search Plan, Vol. 70, Lecture Notes in Statistics, Springer-Verlag, 1992.
  • De Groot, Morris H., Optimal Statistical Decisions, Wiley Classics Library, 2004.
  • Richardson, Henry R; and Stone, Lawrence D. Operations Analysis during the underwater search for Scorpion. Naval Research Logistics Quarterly, June 1971, Vol. 18, Number 2. Office of Naval Research.
  • Stone, Lawrence D. Search for the SS Central America: Mathematical Treasure Hunting. Technical Report, Metron Inc. Reston, Virginia.
  • Koopman, B.O. Search and Screening, Operations Research Evaluation Group Report 56, Center for Naval Analyses, Alexandria, Virginia. 1946.
  • Richardson, Henry R; and Discenza, J.H. The United States Coast Guard computer-assisted search planning system (CASP). Naval Research Logistics Quarterly. Vol. 27 number 4. pp. 659–680. 1980.
  • Ross, Sheldon M., An Introduction to Stochastic Dynamic Programming, Academic Press. 1983.