第一章算法概述.ppt

,第一章 算法概述,第二章 递归与分治策略,第三章 动态规划,第四章 贪心算法,第五章 回朔法,第六章 分支限界法,第七章 概率算法简介,第八章 NP完全性理论简介,算法设计与分析 目录,7.1 基本知识,7.2 随机数,7.3 随机投点计算值,7.4 线性时间选择算法,7.5 n后问题,7.6 求素数的概率算法,7.7 求最近点对的概率算法,7.8 steiner树,算法设计与分析 目录,算法设计与分析 概率算法简介,算法思路 求解问题P的概率算法 A定义如下：设I是P的一个实例,I的规模|I|=n，在用A解I的某些时刻，随机地选取变量b的值(1=b=n)，由b的值决定算法的下一步选取，除了选取b的动作外，A的其它动作是确定的。为简单起见，通常设b的值出现的概率是相等的。,概率算法通常是确定算法随机化后的结果，它没有扩大原有的可计算函数的范围，所以不会影响已有的可计算性概念和结果.,7.1 基本概念,概率算法:指算法的某些步骤中的某些动作是随机性的.,对所求解问题的同一实例用同一概率算法求解两次所需的时间及所得到的结果可能会有很大的差别。,算法设计与分析 概率算法简介,适用问题,(1)对有些问题,最坏情况是极个别的,可能耗费很长时间,而 绝大多数情况算法执行效率还是很快的,这时候,平均复 杂性也许更有意义.(2)在许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择省时。,设计步骤,(1)对给定问题P设计一个确定算法A.(2)分析算法A的各个步骤及有关操作，确定随机化的入口 和随机化方式,从而将算法A随机化，得到概率算法A.(3)论证A是一个好的算法，即证明：A比A更好。,算法设计与分析 概率算法简介,时间复杂性,分析算法A的耗费时,要确定随机变量的耗费函数，并根据问题的特征和采取的随机模式(通常等概率)估算平均耗费.,平均耗费:如果对每个实例I P,|I|=n,算法A解I的平均耗费=f(n),则称A以平均耗费f(n)解问题p.其中,平均耗费是指同一实例对A中所有可能选中的r所耗时间对r的平均.,算法设计与分析 概率算法简介,数值概率算法 用于数值问题的求解。这类算法所得到的往往是近似解。且近似解的精度随计算时间的增加而不断提高。在许多情况下，要计算出问题的精确解是不可能或没必要的，此时用数值概率算法可得到满意的解。(投点法求),总能求得问题的一个解，且所求得的解总是正确的。当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可在这个确定性算法中引入随机性。(快速排序,搜索),舍伍德算法,概率算法分类,算法设计与分析 概率算法简介,蒙特卡罗方法(随机模拟方法)用于求问题的准确解。用蒙特卡罗算法能求得问题的一个解，但这个解未必正确。求得正确解的概率依赖于算法所用的时间。算法所用的时间越多，得到正确解的概率就越高。一般情况下，无法有效判定所得到的解是否肯定正确。(求素数),拉斯维加斯算法 一旦用拉斯维加斯算法找到一个解，这个解就一定是正确解。但有时用拉斯维加斯算法会找不到解。与蒙特卡罗算法类似，拉斯维加斯算法找到正确解的概率随着它所用的计算时间的增加而提高。对于所求解问题的任一实例，用同一拉斯维加斯算法反复对该实例求解足够多次，可使求解失效的概率任意小。(n后问题),线性同余法求伪随机数由线性同余法产生的伪随机数序列 a1,a2,an.满足 a0=d an=(b a n-1+c)mod m n=1,2,其中,b0,c 0,d m.d称为随机序列的 种子.,算法设计与分析 概率算法简介,计算机的随机数是由随机种子根据一定的计算方法计算出来的数值（伪随机数）。计算机中无法产生真正的随机数.,7.2 随机数,随机序列的性能与b,c,d的选取有关.m应充分大(机器大数),且 gcd(m,b)=1.故可取b为素数.d为无符号长整数,可由用户选取,也可由系统时间自动产生.,算法设计与分析 概率算法简介,7.3 随机投点法计算值(数值概率算法),问题 设有一半径为r的圆及其外切四边形,向该正方形随机地投掷n个点.设落入圆内的点数为k,假定所投入的点在正方形上均匀分布,因而所投入的点 落入圆内的概率为r2/4r2,当n足够大时,k与n之比就逼近这一概率即/4,从而 4k/n.,Double darts(int n)static RandomNumber dart;in k=0;for(int i=1;i=n;i+)double x=dart.fRandom()double y=dart.fRandom()if(x*x+y*y)=1)k+return 4*k/double(n),7.4 线性时间选择算法(舍伍德),问题陈述 求n个元素中的第k小元素.,算法思路对输入数组A进行二分划分,使子数组A1的元素J,则K为A2的第K-J小元.,分析:,template Type RandomizedSelect(a,int p,int r,int k)if(p=r)return a p;int i=RandomizedPartition(a,p,r),j=i-p+l if(k=j)return RandomizedSelect(a,p,i,k);else return RandomizedSelect(a,i+1,r,k-j);,Tmax=(n2)(左半总为空),若分点总是等分点,则,Tmin(n)=,dT(n)=T(n/2)+cn,得:T(n)=(n),算法设计与分析 概率算法简介,*随机选择支点的函数,算法设计与分析 概率算法简介,template int randomizedPartition(Type a,int p,int r)int i=random(p,r)swap(ai,ap)return Partition(a,p,r),用ap对数组ap:r划分.,算法设计与分析 概率算法简介,7.5 N后问题(拉斯维加斯),算法思路 在棋盘上相继的各行中随机地放置皇后，并注意使新放置的皇后与已放置的皇后互不攻击，直至n个皇后均已相容地放置好，或已没有下一个皇后的可放置位置时为止。,问题描述 nXn棋盘上放置n个皇后使得每个皇后互不受攻击.即任二皇后不能位于同行同列和同一斜线上.,对于n后问题的任何一个解而言，每一个皇后在棋盘上的位置无任何规律，不具有系统性，而更象是随机放置的。由此容易想到下面的 拉斯维加斯算法。,算法设计与分析 概率算法简介,Bool queen:queenslv(viod)/随机放置 n个皇后的拉斯维加斯算法randomnumber md/随机数产生器Int k=1;/皇后编号int count=1;while(k0)count=0;int j=0;for(int i=1;i0)xk+=j return(count0);,算法设计与分析 概率算法简介,如果将上述随机放置策略与回溯法相结合，可能会获得更好的效果。可以先在棋盘的若干行中随机地放置皇后，然后在后继行中用回溯法继续放置，直至找到一个解或宣告失败。随机放置的皇后越多，后继回溯搜索所需的时间就越少，但失败的概率也就越大。,算法改进,12皇后的随机回溯法中的随机性能比较,算法设计与分析 概率算法简介,7.6 判定n是否为素数的概率算法,for i=2 to n-1 doif n mod i=0 then go to l2l1:write(“n是素数”)stopl2:write(“n是合数”)算法复杂性:O(n),for i=2 to INT(sqrt(n)doif n mod i=0 then go to l2l1:write(“n是素数”)l2:write(“n是合数”)算法复杂性:O(n),穷举法,改进算法,筛法,for i=2 to sqrt(n)do marki:=0;for i=2 to sqrt(n)do if marki=0 then if n mod i=0 then go to l2 s:=i+I;while(s sqrt(n)do marks:=1;s:=s+I;l1:write(“n是素数”)l2:write(“n是合数”)算法复杂性:O(),算法设计与分析 概率算法简介,换言之,设n是自然数,若存在自然数 b,1bn,使得 W(b)=b n-1 l mod n成立,则 n必为合数.这时称b是n为合数的 证人。,判定n是否为素数的概率算法,算法思路 随机选取m个数1=b1,.bm=n,对每个bi检查 W(bi)否成立.如有一成立,则n必为合数,如对所选序列 r=(b1,b2,.bm)，W(bi)都不成立，则可推断n为素数.,费尔马小定理 n 是素数,且b是自然数,1bn,则:b n-1 l mod n,该算法的出错概率为12m，耗费为O(m log 3n)；,算法设计与分析 概率算法简介,7.7 求平面点集上最近点对的概率算法,问题描述:给定平面S上n个点,找其中的一对点,使得在n(n-1)/2个点对 中,该点对的距离最小。,1)n较小时直接求(n=2).2)将S上的n个点分成大致相等的2个子集S1和S2 3)分别求S1和S2中的最接近点对 4)求一点在S1、另一点在S2中的最近点对 5)从上述三对点中找距离最近的一对.,T(n)=O(nlogn),直接算法:求出所有点对距离取其最小值.,T(n)=O(n2),分治递归算法,算法设计与分析 概率算法简介,1)从S中随机选取子集S1=xi1,xi2,xim,m=n2/3 2)计算S1中的最近点对距离(S1).3)构造以(S1)为尺寸的网格,将此网格尺寸向四个不同方向 扩大一 格,得到四个网格:1,2,3,4.则最近点对必落 在1,2,3,4 之一中.,概率算法,x3,x7,x3,x2,右上角网格1,左上角网格2,x7,x2,算法设计与分析 概率算法简介,4)对每个i,求它对点集S的划分:S=S1(i).S ki(i),i=1.4 其中Sj(i)是网格i 中第j个方格中的点.S中的每个点至多位 于4个方格中.故 ki 4n.求S的划分,可用散列或桶排序,桶排序计算量为O(nlogn),(行,列坐标分别排序后分割)用散列法可达O(n).5)对每个S1(i),计算(S1(i).计算量为O(n)6)取(S1(i)的极小值即为S的最小点对距离.,概率算法续,算法设计与分析 概率算法简介,问题描述 给定平面上若干节点，两点间的边长为两点间的直角折线距离,即d=|x1-x2|+|y1-y2|.如何连接这些结点使连线的总长度最小?在这里允许线路在站点以外的点（即Steiner点）连接.通过加入若干“虚设节点”后，构造出由原节点和虚设点组成的最小生成树（称为Steiner树），若虚设点设置得当，就可降低由原节点生成的最小生成树所需的费用用这种方法可降低费用多达134如何构造最小Steiner树，即最低费用的Steiner树？为构造一个有n个点的网络，最低费用的Steiner树最多需n2个Steiner点Steiner点位于给定节点的x，y坐标线形成的格点上,7.8 Steiner树,77,76,75,b(4,3),a(0,0),C(6,0),a,b,c,4,2,3,d(4,0),算法设计与分析 概率算法简介,l）给定点连同随机选取一些虚设点一起构成点集Z,求Z的最小 生成树，其费用记为C，置k0 2)产生新的点集S 从以下几种方式中随机选择一种：加入一个新的虚设点；去掉一个存在的虚设点；移动一个现有的虚设点到一个随机的允许位置3）确定新点集S的最小生成树，其费用记为C1 若c1=c，则更新C为C1，更新当前点集Z为S，当k=M时停 止，否则k=kl，转2）；若C1C，则仅以一定的概率（可取为exp-(C1C)/T(k)，其中T为一控制参数,称为温度，随k的增大而减小，比如取 T(k)=T(0)/k，称为冷却方案）接受S作为当前点集Z，转2).,模拟退火法求近似解,