第一章算法概述

《第一章算法概述》由会员分享，可在线阅读，更多相关《第一章算法概述（22页珍藏版）》请在金锄头文库上搜索。

1、第一章第一章 算法概述算法概述第二章第二章 递归与分治策略递归与分治策略第三章第三章 动态规划动态规划第四章第四章 贪心算法贪心算法第五章第五章 回朔法回朔法第六章第六章 分支限界法分支限界法第七章第七章 概率算法概率算法简介简介第八章第八章 NP NP完全性理论简介完全性理论简介算法设计与分析算法设计与分析 目录目录苫毅馏贷孪矿块崭洼畔码恃桌趾橇寺命砍茵阂牛膜隧们橡冈柒叼攘台责粳第一章算法概述第一章算法概述7.1 7.1 基本知识基本知识7.2 7.2 随机数随机数7.3 7.3 随机投点计算随机投点计算 值值7.4 7.4 线性时间选择算法线性时间选择算法7.5 n7.5 n后问题后问题7

2、.6 7.6 求素数的概率算法求素数的概率算法7.7 7.7 求最近点对的概率算法求最近点对的概率算法 7.8 steiner 7.8 steiner树树算法设计与分析算法设计与分析 目录目录校壳炬旷俊质慧斜诱面惮须言菩当柔善高璃堡陆对外啤庞嘎拒邹关祁扼未第一章算法概述第一章算法概述算法设计与分析算法设计与分析 概率算法简介概率算法简介算法思路算法思路 求解问题求解问题P的概率算法的概率算法 A定义如下：定义如下：设设I是是P的一个实例的一个实例, I的规模的规模| I |=n，在用，在用A解解I的某些时刻，的某些时刻，随机地选取变量随机地选取变量b的值的值 (1=b 概率算法简介概率算法简介

3、 适用问题适用问题 (1) 对有些问题对有些问题, ,最坏情况是极个别的最坏情况是极个别的, ,可能耗费很长时间可能耗费很长时间, ,而而 绝大多数情况算法执行效率还是很快的绝大多数情况算法执行效率还是很快的, ,这时候这时候, ,平均复平均复 杂性也许更有意义杂性也许更有意义. . (2) 在许多情况下，当算法在执行过程中面临一个选择时，在许多情况下，当算法在执行过程中面临一个选择时， 随机性选择常比最优选择省时。随机性选择常比最优选择省时。设计步骤设计步骤 (1) 对给定问题对给定问题P设计一个确定算法设计一个确定算法A. (2) 分析算法分析算法A的各个步骤及有关操作，确定随机化的入口的

4、各个步骤及有关操作，确定随机化的入口 和随机化方式和随机化方式,从而将算法从而将算法A随机化，得到概率算法随机化，得到概率算法A. (3) 论证论证A是一个好的算法，即证明：是一个好的算法，即证明：A比比A更好。更好。 压各睦凌瞧继充牵戴巢粕泊家涩蛰谓畏漓惦趋揉烦菇懂幢聘室登羹叁司喧第一章算法概述第一章算法概述算法设计与分析算法设计与分析 概率算法简介概率算法简介时间复杂性时间复杂性分析算法分析算法A的耗费时的耗费时, 要确定随机变量的耗费函数，并根据要确定随机变量的耗费函数，并根据问题的特征和采取的随机模式问题的特征和采取的随机模式(通常等概率通常等概率)估算估算平均耗费平均耗费.平均耗费平

5、均耗费: 如果对每个实例如果对每个实例I P, |I|=n, 算法算法A解解I的平均耗费的平均耗费 概率算法简介概率算法简介数值概率算法数值概率算法 用于数值问题的求解。这类算法所得到的往往是近似解。用于数值问题的求解。这类算法所得到的往往是近似解。且近似解的精度随计算时间的增加而不断提高。在许多情况且近似解的精度随计算时间的增加而不断提高。在许多情况下，要计算出问题的精确解是不可能或没必要的，此时用数下，要计算出问题的精确解是不可能或没必要的，此时用数值概率算法可得到满意的解。值概率算法可得到满意的解。 (投点法求投点法求 )总能求得问题的一个解，且所求得的解总是正确的。当一总能求得问题的一

6、个解，且所求得的解总是正确的。当一个确定性算法在最坏情况下的计算复杂性与其在平均情况个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可在这个确定性算法中下的计算复杂性有较大差别时，可在这个确定性算法中引入随机性。引入随机性。 (快速排序快速排序,搜索搜索)舍伍德算法舍伍德算法概率算法分类概率算法分类泥糕滋臼滁滁骇茄莽淄汝画枯鲜排袒舌破烙绝沁希籍宛疮拎箭讳卡涣跳糟第一章算法概述第一章算法概述算法设计与分析算法设计与分析 概率算法简介概率算法简介蒙特卡罗方法蒙特卡罗方法(随机模拟方法随机模拟方法)用于求问题的准确解。用蒙特卡罗算法能求得问题的一个用于求问题的准确解。用

7、蒙特卡罗算法能求得问题的一个解，但这个解未必正确。求得正确解的概率依赖于算法所解，但这个解未必正确。求得正确解的概率依赖于算法所用的时间。算法所用的时间越多，得到正确解的概率就越用的时间。算法所用的时间越多，得到正确解的概率就越高。一般情况下，无法有效判定所得到的解是否肯定正确。高。一般情况下，无法有效判定所得到的解是否肯定正确。 (求素数求素数 )拉斯维加斯算法拉斯维加斯算法 一旦用拉斯维加斯算法找到一个解，这个解就一定是正一旦用拉斯维加斯算法找到一个解，这个解就一定是正确解。但有时用拉斯维加斯算法会找不到解。与蒙特卡罗算确解。但有时用拉斯维加斯算法会找不到解。与蒙特卡罗算法类似，拉斯维加斯

8、算法找到正确解的概率随着它所用的计法类似，拉斯维加斯算法找到正确解的概率随着它所用的计算时间的增加而提高。对于所求解问题的任一实例，用同一算时间的增加而提高。对于所求解问题的任一实例，用同一拉斯维加斯算法反复对该实例求解足够多次，可使求解失效拉斯维加斯算法反复对该实例求解足够多次，可使求解失效的概率任意小的概率任意小。(n后问题后问题)喉阶牟锄苔扎昂迅曾侥栅州匡袄埂皋通蜗携进参指擦酞亥陵扔味裔羔惰啼第一章算法概述第一章算法概述线性同余法求伪随机数线性同余法求伪随机数由线性同余法产生的伪随机数序列由线性同余法产生的伪随机数序列 a1,a2,an.满足满足 a0=d an=(b a n-1+c)

9、mod m n=1,2,其中其中, b 0 , c 0, d m. d称为随机序列的称为随机序列的 种子种子.算法设计与分析算法设计与分析 概率算法简介概率算法简介计算机的随机数是由随机种子根据一定的计算方法计算出来的数计算机的随机数是由随机种子根据一定的计算方法计算出来的数值（伪随机数）。值（伪随机数）。计算机中无法产生真正的随机数计算机中无法产生真正的随机数. .7.2 7.2 随机数随机数 随机序列的性能与随机序列的性能与b, c, d的选取有关的选取有关. m应充分大应充分大(机器大数机器大数),且且 gcd(m,b)=1. 故可取故可取b为素数为素数. d为无符号长整数为无符号长整数

10、,可由用户选取可由用户选取,也可由系统时间自动产生也可由系统时间自动产生.帅殃龙拘峡鳃摇勿血反虾熔濒阔呜孰戌煎郑挞陛樟豁符跺泰遥既露握品统第一章算法概述第一章算法概述算法设计与分析算法设计与分析 概率算法简介概率算法简介7.3 随机投点法计算值(数值概率算法)问题问题 设有一半径为设有一半径为r的圆及其外切四边形的圆及其外切四边形,向该正方形随机向该正方形随机地投掷地投掷n个点个点.设落入圆内的点数为设落入圆内的点数为k,假定所投入的点在正方假定所投入的点在正方形上均匀分布形上均匀分布,因而所投入的点因而所投入的点 落入圆内的概率为落入圆内的概率为 r2/4r2, 当当n足够大时足够大时,k与

11、与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小元素小元素.算法思路算

12、法思路对输入数组对输入数组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 概率算法简介概率算法简介伞孙奸泳桨酋柜祝鞠伴承煞楚钳坟讣叶频染牙还孕崭堵白却护噎克途峰寸第一章算法概述第一章算法概述*随机选择支点的函数算法设计与分析算法设计与分析 概率算法简介概率算法简介 t

13、emplate 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 N7.5 N后问题后问题( (拉斯维加斯拉斯维加斯) ) 算法思路算法思路 在棋盘上相继的各行中随机地放置皇后，并注在棋盘上相继的各行中随机地放置皇后，并注意使新放置的皇后与已放置的

14、皇后互不攻击，直至意使新放置的皇后与已放置的皇后互不攻击，直至n n个皇后个皇后均已相容地放置好，或已没有下一个皇后的可放置位置时均已相容地放置好，或已没有下一个皇后的可放置位置时为止。为止。 问题描述问题描述 nXnnXn棋盘上放置棋盘上放置n n个皇后使得每个皇后互不受攻击个皇后使得每个皇后互不受攻击. . 即即任二皇后不能位于同行同列和同一斜线上任二皇后不能位于同行同列和同一斜线上. . 对于对于n后问题的任何一个解而言，每一个皇后在棋盘上的位置后问题的任何一个解而言，每一个皇后在棋盘上的位置无任何规律，不具有系统性，而更象是随机放置的。由此容易无任何规律，不具有系统性，而更象是随机放置

15、的。由此容易想到下面的想到下面的 拉斯维加斯算法拉斯维加斯算法。 扔姜架贞犹境陆脾沸帛氟矢硅私查会舒惨绷平赖码满演芒湾牛修萤艺哲酞第一章算法概述第一章算法概述算法设计与分析算法设计与分析 概率算法简介概率算法简介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);利芦埂与世碍吓睛

16、港戍剿竹虎合荚常祁揪咖霞蜀刮束鞋歧辱厩鳃摆械推锚第一章算法概述第一章算法概述算法设计与分析算法设计与分析 概率算法简介概率算法简介如果将上述随机放置策略与回溯法相结合，可能会获得更如果将上述随机放置策略与回溯法相结合，可能会获得更好的效果。可以先在棋盘的若干行中随机地放置皇后，然好的效果。可以先在棋盘的若干行中随机地放置皇后，然后在后继行中用回溯法继续放置，直至找到一个解或宣告后在后继行中用回溯法继续放置，直至找到一个解或宣告失败。随机放置的皇后越多，后继回溯搜索所需的时间就失败。随机放置的皇后越多，后继回溯搜索所需的时间就越少，但失败的概率也就越大。越少，但失败的概率也就越大。 222.11

17、10.2013.000.04651280.3947.2333.880.50395262.00-262.001.00000tesp随机程度 算法改进算法改进 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)f

18、or 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 概率算法简介概率算法简介换言之换言之,设设n是自然数是自然数, 若存在自然数若存在自然数 b, 1bn, 使得使得 W(b)= b n

19、-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是自然数是自然数, 1b 概率算法简介概率算法简介7.7 7.7 求平面点集上最近点对的概率算法求平

20、面点集上最近点对的概率算法问题描述问题描述:给定平面给定平面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) 直接算法直接算法:求出所有点对距离取其

21、最小值求出所有点对距离取其最小值. T(n)=O(n2) 分分治治递递归归算算法法春捶范灌佑驹浊足舱樊缅六狗振诈德庇惫过道褪截啃攫潭税画排驯苞荒碗第一章算法概述第一章算法概述算法设计与分析算法设计与分析 概率算法简介概率算法简介1) 从从S中中随机随机选取子集选取子集S1=xi1,xi2,xim , m=n2/3 2) 计算计算S1中的最近点对距离中的最近点对距离 (S1).3) 构造以构造以 (S1)为尺寸的网格为尺寸的网格,将此网格尺寸向四个不同方向将此网格尺寸向四个不同方向 扩大一扩大一 格格, 得到四个网格得到四个网格: 1, 2, 3, 4. 则最近点对必落则最近点对必落 在在 1,

22、 2, 3, 4 之一中之一中.概率算法x3x7x3x2右上角网格右上角网格 1左上角网格左上角网格 2x7x2肖绢拾铁杀骤岗沸缮拎达缔跺狼落始叛柔党教黔铅草沽历大着待遭戍谓闽第一章算法概述第一章算法概述算法设计与分析算法设计与分析 概率算法简介概率算法简介4) 对每个对每个 i ,求它对点集求它对点集S的划分的划分: S=S1 (i) . S ki (i) , i=1.4 其中其中Sj (i)是网格是网格 i 中第中第j个方格中的点个方格中的点. S中的每个点至多中的每个点至多位位 于于4个方格中个方格中.故故 ki 4n. 求求S的划分的划分,可用散列或桶排序可用散列或桶排序, 桶排序计算

23、量为桶排序计算量为O(nlogn), (行行,列坐标分别排序后分割列坐标分别排序后分割) 用散列法可达用散列法可达O(n).5) 对每个对每个S1(i),计算计算 (S1(i). 计算量为计算量为O(n)6) 取取 (S1(i)的极小值即为的极小值即为S的最小点对距离的最小点对距离.概率算法续愧乃垮摩礼捆筐配舀碘葵馋综困妆甭陶纺镑曼蛙褪拖剥杉炒攻浪仲骆忌扯第一章算法概述第一章算法概述算法设计与分析算法设计与分析 概率算法简介概率算法简介 问题描述问题描述 给定平面上若干节点，两点间的边长为两点间的直角折线给定平面上若干节点，两点间的边长为两点间的直角折线距离距离, 即即d=|x1-x2|+|y

24、1-y2| .如何连接这些结点使连线的总长度最小如何连接这些结点使连线的总长度最小?在这里允许线路在站点以外的点（即在这里允许线路在站点以外的点（即Steiner点）连接点）连接.通过加入若干通过加入若干“虚设节点虚设节点”后，构造出由原节点和虚设点组成的最小后，构造出由原节点和虚设点组成的最小生成树（称为生成树（称为Steiner树），若虚设点设置得当，就可降低由原节点生树），若虚设点设置得当，就可降低由原节点生成的最小生成树所需的费用用这种方法可降低费用多达成的最小生成树所需的费用用这种方法可降低费用多达134如如何构造最小何构造最小Steiner树，即最低费用的树，即最低费用的Stein

25、er树？树？为构造一个有为构造一个有n个点的网络，最低费用的个点的网络，最低费用的Steiner树最多需树最多需n2个个Steiner点点Steiner点位于给定节点的点位于给定节点的x，y坐标线形成的格点上坐标线形成的格点上 7.8 Steiner树树7 77 77 76 67 75 5b(4,3)b(4,3)a(0,0)a(0,0)C(6,0)C(6,0)a ab bc c4 42 23 3d(4,0)d(4,0)糊曲堡十崖合竿该翻赵湛石钙魂鹤坪井惯掘逞惩闸惮陀朗摆蛮辐饺洼王痈第一章算法概述第一章算法概述算法设计与分析算法设计与分析 概率算法简介概率算法简介 l）给定点连同随机选取一些虚设

26、点一起构成点集）给定点连同随机选取一些虚设点一起构成点集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).模拟退火法求近似解模拟退火法求近似解玄郸褂翱比滤枯蔼疏卷迄星旨进邓喜轻府纵惑玲皮娩裴儡坐脓笋蜂锄法坟第一章算法概述第一章算法概述