一类有重要应用背景的概率计算问题的算法研究与编程.pdfVIP

一类有重要应用背景的概率计算问题的算法研究与编程 房琳智 北京邮电大学，北京 (100876) E-mail ：fanglinzhi@163.com 摘 要：本文将针对一类有重要应用背景的概率计算问题进行分析与研究，讨论两种不同的 解决问题方法，并结合具体的算法用计算机实现最后的求解。首先我们将问题的模型提炼出 来：设有N 名侦察兵，在经过一系列危险后第 I 名侦察兵顺利到达目的地的概率是P(I)(概 率与人有关) ，那么至少有M 名侦察兵顺利到达目的地的概率是多少？很显然这是军事领域 中经常遇到的一类问题，在其他领域与此问题类似的模型也是屡见不鲜的，关于这些问题的 背景以及意义将在本文的第一部分介绍。第二部分将对问题进行提炼，把此类问题归结为数 学问题，应用概率论的知识实现原始算法的设计。经过分析我们将发现原始算法的一些瑕疵， 从原始算法的缺点出发，引出优化算法将是第三部分的内容。经过对优化算法复杂度与原始 算法复杂度的比较分析，得出优化算法的优越性。进而利用优化算法解决问题。 关键词：概率，算法，复杂度，效率 中图分类号：O1-0 1. 引言 该研究课题是从军事实际问题中提炼出来的。设有 N 名侦察兵，在经过一系列危险后 第I 名侦察兵顺利到达目的地的概率是P （I ）(概率与人有关) ，那么至少有M 名侦察兵顺利 到达目的地的概率是多少？进一步，如果上级命令至少有M 名侦察兵顺利到达目的地的概 率不得小于0.8, 则至少需要派出多少名侦察兵才能完成任务？ 在军事自动化指挥系统中尤其是高技术兵器的自动化指挥系统中， 在确定了打击目标 后，需要根据打击任务来确定各高技术兵器的使用数量， 其中的一个基本子问题就是要反 复求解课题描述中所提出的数学模型 ( 由于保密原因，我们不给出原模型) 。 此问题虽然来源于军事领域，但它的应用并不是局限于军事。从经济运行到公民的日常 生活都可以找到与这个问题类似的模型。我们可以对此问题作如下的叙述： 一个企业打算对N 个项目进行风险投资，每一项成功的概率是P （I ），那么至少有M 个项目成功的概率是多少？进一步。如果投资者要求至少有M 投资项获得成功的概率不得 小于0.8，则至少需要进行多少项投资才能完成任务 也可这样描述： 一个人打算邀请N 个好朋友到家里做客，每一个人赴约的概率是P （I ），那么至少有 M 个好朋友能赴约的概率是多少？进一步，如果主人希望至少有M 个人来家做客的概率不 得小于0.8，则至少需要邀请多少个人才能符合要求 如此看来这个问题应用的领域是无处不在的。我们研究它并给出一个求解它的快速算法 是非常有意义的。 2. 原始算法 2.1 符号的说明 N 表示总共派出N 名侦察员。 M 表示要求到达M 名侦察员。 q(i)表示第i 名侦察员顺利到达目的地的概率。 P(i ，j) 表示派出j 名侦察员i 名到达目的地的概率。 - 1 - Ai 表示从N 名侦察员中刚好优M 名到达的一种组合。 2.2 问题求解 设至少有M 名侦察兵到达目的地的概率为事件B P(B)=P(M ，N)+P(M+1 ，N)+···+P(N ，N) (N ≥M) 根据公式只要给出计算P(M ，N) 的方法，其余项可以类似给出。 根据概率的理论分析[1]，以及此类问题常规的计算方法得出： P(M，N)= ∑p (Ai) M