第六章 随机化算法

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

1、第五章搜索法175均等待时间是n个顾客等待服务时间的总和除以n。5-10整数变换问题。关于整数i的变换f和g定义如下：f(i)=3i，g(i)=i/2。试设计一个算法，对于给定的两个个整数n和m，用最少的f和g变换次数将n变换为m。例如，可以将整数15用4次变换将它变换为整数4：4=gfgg(15)。当整数n不可能变换为整数m时，算法应如何处理?5-11推箱子问题。码头仓库是划分为n×m个格子的矩形阵列。有公共边的格子是相邻格子。当前仓库中有的格子是空闲的；有的格子则已经堆放了沉重的货物。由于堆放的货物很重，单凭仓库管理员的力量是无法移动的。仓库管理员有一项任务，要将一

2、个小箱子推到指定的格子上去。管理员可以在仓库中移动，但不能跨过已经堆放了货物的格子。管理员站在与箱子相对的空闲格子上时，可以做一次推动，把箱子推到另一相邻的空闲格子。推箱子只能向管理员的对面方向推。由于要推动的箱子很重，仓库管理员想尽量减少推箱子的次数。请设计一算法，使仓库管理员推箱子的次数最少。5-12喷漆机器人。F大学开发出一种喷漆机器人Rob，能用指定颜色给一块矩形材料喷漆。Rob每次拿起一种颜色的喷枪，为指定颜色的小矩形区域喷漆。喷漆工艺要求，一个小矩形区域只能在所有紧靠它上方的矩形区域都喷过漆后，才能开始喷漆，且小矩形区域开始喷漆后必须一次性喷完，不能只喷一部分。为Ro

3、b编写一个自动喷漆程序，使Rob拿起喷枪的次数最少。PrinttoPDFwithoutthismessagebypurchasingnovaPDF(http://www.novapdf.com/)第六章随机化算法教学目标理解产生伪随机数的线性同余法掌握数值随机化算法的特点及应用掌握蒙特卡罗算法的特点及应用掌握拉斯维加斯算法的特点及应用掌握舍伍德算法的特点及应用前面各章讨论的算法每一计算步骤都是确定的，而本章讨论的随机化算法允许算法在执行过程中随机地选择下一个计算步骤，这种算法的新颖之处是把随机性注入到算法之中，该策略使得算法的设计与分析更加灵活，其解决问题的能力也大为改观。6.1

4、概述随机化算法与现实生活息息相关，例如：人们经常会通过掷色子来看结果，投硬币来决定行动，这就牵涉到一个问题：随机。随机化算法看上去是凭着运气做事。其实，这种算法是有一定的理论基础的，且很少单独使用，大多是与其他算法（如贪心法、查找算法等）配合起来运用，求解效果往往出人意料。6.1.1随机化算法的类型及特点随机化算法的一个基本特征是：对所求解问题的同一实例用同一随机化算法求解两次可能得到完全不同的效果，这两次求解问题所需的时间甚至所得到的结果可能会有相当大的差别。一般情况下，可将随机化算法大致分为四类：1．数值随机化算法这类算法常用于数值问题的求解，所得到的解往往都是近似解，而且近

5、似解的精度随计算时间的增加不断提高。使用该算法的理由是：在许多情况下，待求解的问题在原理上可能就不存在精确解，或者说精确解存在但无法在可行时间内求得，因此用数值随机化算法可得到相当满意的解。2．蒙特卡罗算法蒙特卡罗算法是计算数学中的一种计算方法，它的基本特点是以概率与统计学中的理论和方法为基础，以是否适合于在计算机上使用为重要标志。蒙特卡罗是摩纳哥的一个著名城市，以赌博闻名于世。为了表明该算法的上述基本特点，蒙特卡罗算法象征性地借用这一城市的名称来命名。蒙特卡罗算法作为一种可行的计算方法，首先是由Ulam（乌拉姆）和VonNeumann（冯·诺依曼）在20世纪40年代中叶提出并加

6、以运用，目的是为了解决研制核武器中的计算问题。该算法用于求问题的准确解。对于许多问题来说，近似解毫无意义。例如，一个判定问题其解为“是”或“否”，二者必居其一，不存在任何近似解答。PrinttoPDFwithoutthismessagebypurchasingnovaPDF(http://www.novapdf.com/)第六章随机化算法177蒙特卡罗算法的特点是：它能求得问题的一个解，但这个解未必是正确的。求得正确解的概率依赖于算法执行时所用的时间，所用的时间越多得到正确解的概率就越高。一般情况下，蒙特卡罗算法不能有效地确定求得的解是否正确。3．拉斯维加斯算法该算法绝不返回错

7、误的解，也就是说，使用拉斯维加斯算法不会得到不正确的解，一旦找到一个解，那么这个解肯定是正确的。但是有时候拉斯维加斯算法可能找不到解。与蒙特卡罗算法类似，拉斯维加斯算法得到正确解的概率随着算法执行时间的增加而提高。对于所求解问题的任一实例，只要用同一拉斯维加斯算法对该实例反复求解足够多的次数，可使求解失效的概率任意小。4．舍伍德算法当一个确定性算法在最坏情况下的计算时间复杂性与其在平均情况下的计算复杂性有较大差异时，可在这个确定性算法中引入随机性来降低最坏情况出现的概率，进而消除