第6章-第1讲-概率算法介绍-1

第六章概率算法每节一经典走好运，造机遇----随机算法

第1讲概率法§1.1引言故事：想象自己是神化故事的主人公,你有一张不易懂的地图,上面描述了一处宝藏的藏宝地点.经分析你能确定最有可能的两个地点是藏宝的地点,但二者相距甚远.假设：你到达其中一处,就立即知道该处是否为藏宝地点（一看便知）.从其中一处到另一处的距离是5天的行程.进一步假设有一条恶龙,每晚光顾宝藏并从中拿走一部分财宝（d）。假设你取宝藏的方案有两种：第1讲概率法§1.1引言5天5天5天??

藏宝地点藏宝地点走哪边最容易找到宝藏？第1讲概率法§1.1引言方案1

花4天的时间计算出准确的藏宝地点,然后出发寻宝,一旦出发，不能返回。方案2

有一个小精灵告诉你地图的秘密,但你必须付给他报酬,相当于恶龙3晚上拿走的财宝。若忽略可能的冒险和出发寻宝的代价,你是否接受小精灵的帮助？显然,应该接受小精灵的帮助,因为你只需给出3晚上被盗窃的财宝量(3d),否则你将失去4晚被盗财宝量(4d)。方案3:但是,若冒险,你可能做得更好！问题理解第1讲概率法§1.1引言设x是你决定之前当日的宝藏价值，设y是恶龙每晚盗走的宝藏价值，并设x>9y

方案1：4天计算确定地址，行程5天，你得到的宝藏价值为：x-9y

方案2：3y付给小精灵，行程5天失去5y，你得到的宝藏价值为：x-8y

方案3：投硬币决定先到一处，失败后到另一处(冒险方案)

一次成功所得：x-5y，机会1/2

二次成功所得：x-5y-5y=x-10y，机会1/2}期望赢利:x-7.5y数学模型平均（期望）赢利=(x-5y)*(1/2)+(x-10y)*(1/2)=x-7.5y第1讲概率法§1.1引言该故事告诉我们：当一个算法面临某种选择时,有时随机选择比花费更多时间（耗时）做最优选择更好,尤其是当最优选择所花的时间大于随机选择的平均时间的时侯。第1讲概率法概率算法是指选择下一步执行步骤时，用随机（概率）方法进行选择，而不是用逻辑上确定的方法进行选择.§概率算法定义允许算法在执行的过程中随机选择下一个计算步骤。许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择省时。因此概率算法可在很大程度上降低算法的复杂度。

p1p2p3p4p5第1讲概率法随机决策不可再现性

在同一实例上执行两次其结果可能不同;在同一实例上执行两次的时间亦可能不太相同。分析困难

要求有概率论，统计学和数论的知识。§概率算法的特点第1讲概率法§概率算法的分类数值概率算法（Numerical）蒙特卡罗算法（MonteCarlo)拉斯维加斯算法（LasVegas）舍伍德算法（Sherwood）很多人将所有概率算法(尤其是数值概率算法)称为MonteCarlo算法第1讲概率法

数值概率算法数值算法常用于数值问题的求解.最早用于求数值问题的近似解。

特点:概率算法获得的答案一般是近似的,但通常算法执行的时间越长,精度就越高,误差就越小.使用的理由：

精确解存在但无法在可行的时间内求得。

有时答案是以置信区间的形式给出的。经典实例

投币法计算π值

计算定积分

解非线性方程组第1讲概率法

MonteCarlo算法(MC算法)蒙特卡洛算法，1945年由J.VonNeumann进行核武模拟提出的.它是以概率和统计的理论与方法为基础的一种数值计算方法,它是双重近似:一是用概率模型模拟近似的数值计算,二是用伪随机数模拟真正的随机变量的样本.这里我们指的MC算法是:若问题只有1个正确的解,而无近似解的可能时，使用MC算法。例如,判定问题只有真或假两种可能性,没有近似解,如因式分解,我们不能说某数几乎是一个因子。第1讲概率法

特点:MC算法总是能给出一个答案,但该答案未必正确,成功(即答案是正确的)的概率正比于算法执行的时间。一般不能有效地确定算法的答案是否正确。

经典实例:

主元素问题

素数测试

MonteCarlo算法(MC算法)第1讲概率法

LasVegas算法(LV算法)LV算法绝不返回错误的答案。特点：获得的答案必定正确,但有时找不到答案，和MC算法一样,成功的概率亦随算法执行时间增加而增加.无论输入何种实例,只要算法在该实例上运行足够的次数,则算法失败的概率就任意小。

经典实例:

n后问题

整数因子分解

模p平方根第1讲概率法Sherwood算法总是给出正确的答案。当某些确定算法解决一个特殊问题的平均时间比最坏情况下所需时间快得多时,我们可以使用

Sherwood算法来减少甚至是消除“好的”和”坏的”实例之间的差别。

Sherwood算法

经典实例:

线性时间选择算法

跳跃表

随机的预处理第1讲概率法智能优化算法

模拟自然过程“优胜略劣汰”的算法一般称之为智能算法。例如，根据动植物繁衍过程原理、物理或化学现象原理等设计的解决困难计算问题的算法，都可以称为智能优化算法。例如：

模拟退火算法

遗传算法

神经网络算法

蚁群优化算法

粒子群优化算法

鱼群算法……第1讲概率法计算智能智能计算演化计算仿生计算进化计算……现代计算新方向：（以下含义基本相同）第1讲概率法模拟退火算法物理学中，通过对固体退火过程的研究知道：高温状态下的物质降温时其内能随之下降；如果降温过程充分缓慢，则在降温过程中物质体系始终处于平衡状态；当降到某一低温时，其内能可能达到最小；称这种降温过程为退火过程，模拟退火过程的寻优方法称为模拟退火算法（simulatedannealing,SA）.Metropolis1953年提出。第1讲概率法遗传算法遗传算法是模拟生物进化过程的智能优化算法，由J.H.Holland60年代提出。关键思想是：1）对问题的解用染色体编码表示（0，1编码）；2）染色体结合时，双亲的遗传基因的结合使子女具有双亲特征；3）染色体结合时，随机的变异造成子女与双亲的不同。4）算子：选择，交叉，变异例如：解编码：双亲—交叉(后三位)—子女10011101111111111011

第1讲概率法神经网络算法根据人脑组织结构和运行机制，40年代心理学家McCulloch和数学家Pitts提出了人工神经网络的数学模型。神经网络由大量神经元互连而成，具有高速信息处理能力。例如：特点：分布并行第1讲概率法神经网络算法根据人脑组织结构和运行机制，40年代心理学家McCulloch和数学家Pitts提出了人工神经网络的数学模型。神经网络由大量神经元互连而成，具有高速信息处理能力。例如：特点：分布并行第1讲概率法粒子群优化算法粒子群优化算法(PSO)是一种进化计算技术(evolutionarycomputation)，由Eberhart博士和kennedy博士发明（199