《算法设计与分析》第七章随机算法及计算复杂性.ppt

第七章 随机算法及NP完全问题

7.1 随机算法引言

7.2 随机算法的类型

7.3 随机数发生器

7.4 数值概率算法

7.5 舍伍德(Sherwood)算法

7.6 拉斯维加斯（Las Vegas）算法

7.7 蒙特卡罗（Monte Carlo）算法

7.8 NP完全问题

7.1 随机算法引言

确定性的算法 ：

算法的每一个计算步骤都是确定的，

对于相同的输出，每一次执行过程都会产生相同的输出。

随机算法：非形式描述

随机算法为使用随机函数产生器的算法。算法中的一些判定依赖于随机函数产生器的输出。

随机算法对于相同的输入，在不同的运行过程中会得到不同的输出。

对于相同的输入，随机算法的执行时间也可能随不同的运行过程而不同。

8.1 随机算法引言

随机算法的优点：

1、执行时间和空间，小于同一问题的已知最好的确定性算法；

2、实现比较简单，容易理解。

很多确定性的算法，其性能很坏。可用随机选择的方法来改善算法的性能。

某些方面可能不正确，对特定的输入，算法的每一次运行不一定得到相同结果。出现这种不正确的可能性很小，以致可以安全地不予理睬。

7.2 随机算法的类型

数值概率算法

拉斯维加斯（Las Vegas）算法

蒙特卡罗（Monte Carlo）算法

舍伍德（Sherwood）算法。

7.2 随机算法的类型

1、数值概率算法：用于数值问题的求解。所得到的解几乎都是近似解，近似解的精度随着计算时间的增加而不断地提高。

2、舍伍德（Sherwood）算法：很多具有很好的平均运行时间的确定性算法，在最坏的情况下性能很坏。引入随机性加以改造，可以消除或减少一般情况和最坏情况的差别。

7.2 随机算法的类型

3、拉斯维加斯（Las Vegas）算法：要么给出问题的正确答案，要么得不到答案。反复求解多次，可使失效的概率任意小。

4、蒙特卡罗（Monte Carlo）算法：总能得到问题的答案，偶然产生不正确的答案。重复运行，每一次都进行随机选择，可使不正确答案的概率变得任意小。

7.3 随机数发生器

产生随机数的公式：

产生0~65535的随机数 序列，

b、c、d为正整数，称为所产生的随机序列的种子。

常数b、c，对所产生的随机序列的随机性能有很大的关系，b通常取一素数。

7.3 随机数发生器

#define MULTIPLIER 0x01

本文档共40页，可免费阅读15页，剩余25页请下载后阅读。继续阅读 

1、本文档共:40页，可阅读全部内容。

2、本文档内容版权归属内容提供方，所产生的收益全部归内容提供方所有。如果您对本文有版权争议，可选择认领，认领后既往收益都归您。

3、本文档由内容提供方上传，本站不保证质量和数量令人满意，可能有诸多瑕疵，付费之前，请仔细先通过免费阅读内容等途径辨别内容交易风险。如存在严重标题与内容不符之情形，可联系本站下载客服投诉处理。