第9章 随机算法.ppt

《第9章 随机算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第9章随机算法1.随机算法引例2.随机算法的类型3.舍伍德算法4.拉斯维加斯算法5.蒙特卡罗算法1.随机算法引例rr由此推导出：2.随机算法的类型第1类算法：数值概率算法。用于数值问题求解，所得到的几乎都是近似解，但计算精度随着计算时间的增加而不断提高。引例中就是一个数值概率算法；在给定函数f(x)的定义域和x与f(x)之间的映射关系，求解f(x)的最值时，可以用数值概率算法。第2类算法：舍伍德算法。舍伍德算法不会从整体上或平均的改善问题求解的时间复杂度，但可以对一些特别耗时的特定输入改善至较适中的时间

2、复杂度第3类概率算法是拉斯维加斯算法。该算法可能给出问题的正确答案，也可能得不到问题的正确答案。但对所求解的问题，用同一个拉斯维加斯算法反复求解多次，可以使得求解失效的概率任意小蒙特卡罗算法总能得到问题的答案，但偶尔会产生不正确的答案。有时并不能判断给出的答案是否正确。重复运行算法使得产生不正确解的概率任意小3.舍伍德算法3.1舍伍德算法概述3.2随机快速排序算法3.3随机选择算法3.1舍伍德算法概述假设TA(x)是确定性算法A对一个输入实例x的运行时间，则上述算法可能存在某个x使得TA(x)远远大于平

3、均时间复杂度。舍伍德类型算法通过向确定性算法A中加入随机因子，使得每一个输入实例与平均时间复杂度相差不大3.2随机快速排序算法快速排序的时间复杂度最好情况下是O(nlogn)，最坏情况下是O(n2)，平均情况是O(nlogn)。最坏情况的出现原因是：待排序的对象已经基本上排序完毕，使得问题的中轴始终处于所有数据的某端或接近于某端为了排除上述情况，可以在中轴选取时，引入随机因子：端点和某个随机位置的数据交换。这使得中轴不大可能是最小（最大）值，或接近最小（最大）值的数值有没有更保险的算法？3.3随机选择算

4、法从n个元素中选择第k小的元素，存在一个O(n)级别的算法，这个算法的时间复杂度上界是20n，具有一个较大的常数上述算法最耗时的地方是：查找一个合适的中轴（把所有元素分成n/5组，每组5个，找出每组中数，然后找出所有元素的近似中数）计算元素中数的过程可以省略，取而代之的是在所有元素中取得一个随机位置，然后让这个位置上的数作为中数这个随机算法的时间复杂度小于4n是否可以继续改进这个随机算法?4.拉斯维加斯算法4.1拉斯维加斯算法概述4.2八皇后问题4.3字符串匹配拉斯维加斯型概率算法有时成功，有时失败当出

5、现失败时，只要在相同的输入实例上再次运行相同的拉斯维加斯概率算法，就又有成功的可能假设BOOLlas_vegas(P(x))是针对问题P的某个实例x的运行代码，则拉斯维加斯执行下面代码：while(!las_vegas(P(x))假设p(x)是输入实例x和运行成功的概率之间的关系，如果存在常数，使得p(x)，就认为该拉斯维加斯算法正确，随着时间增加，可以让算法的错误概率(1-)k任意小4.1拉斯维加斯算法概述4.2八皇后问题可以把拉斯维加斯概率算法和回溯法结合解决八皇后问题单行随机选择的拉斯维加

6、斯算法：单行选择位置时和回溯法相似，只是位置并不是从左到右遍历，而是随机在一行中选择一个位置。如果经过多次（预设的值）找不到，就回溯多行随机选择的拉斯维加斯算法：在已有选择的基础上，对紧跟的多行随机选择位置。要同时保障满足两个约束：新添行之间的约束；与前面已有行的约束。如果经过多次（预设的值）找不到，就回溯整体随机选择的拉斯维加斯算法：在n行上随机选择n个列，如果满足约束就是一个解；如果不满足，就重新选择4.3字符串匹配4.3.1哈希查找概述4.3.2简单的哈希函数4.3.3字符串匹配算法总结4.3.4

7、字符串匹配的拉斯维加斯算法4.3.1哈希查找概述哈希查找算法是一个高效的算法，如果设计得当，可以通过O(1)的比较次数找到所需元素哈希查找算法不可避免地会有地址冲突的问题哈希算法的思想有许多其他的应用，例如在挖掘关联规则的过程中利用哈希查找的办法发现二次的大项集4.3.2简单的哈希函数网络传输的冗余位就是一个哈希函数11010010虽然不能保证冗余位相同的两个字节相同，但冗余位不同的两个字节一定是不同的网络传输中的一位出现了错误是能够发现的，而这又是最常见的情况4.3.3字符串匹配算法总结朴素的匹配算法

8、。时间复杂度O(mn)KMP算法。时间复杂度O(m+n)4.3.4字符串匹配的拉斯维加斯算法一个简单例子：假设字符集是{a,b,c,d}。在母串“bcbccdabc”中查找子串“cda”任意取一个素数19（在计算允许的情况下越打越好）把子串“cda”变换成4进制数230，这个数对应的十进制数是44，模19之后的数是6计算母串的前3个字符的4进制模19的数值，是6，因此，前3个字符构成的子串有可能和模式串匹配，通过朴素的算法发现它们不匹配字符