第六篇 随机化算法.pdf

第五章 搜索法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 个格子的矩形阵列。有公共边的格子是相邻格子。 当前仓库中有的格子是空闲的；有的格子则已经堆放了沉重的货物。由于堆放的货物很 重，单凭仓库管理员的力量是无法移动的。仓库管理员有一项任务，要将一个小箱子推 到指定的格子上去。管理员可以在仓库中移动，但不能跨过已经堆放了货物的格子。管 理员站在与箱子相对的空闲格子上时，可以做一次推动，把箱子推到另一相邻的空闲格 子。推箱子只能向管理员的对面方向推。由于要推动的箱子很重，仓库管理员想尽量减 少推箱子的次数。请设计一算法，使仓库管理员推箱子的次数最少。 5- 12 喷漆机器人。F 大学开发出一种喷漆机器人 Rob ，能用指定颜色给一块矩形材料喷漆。 Rob 每次拿起一种颜色的喷枪，为指定颜色的小矩形区域喷漆。喷漆工艺要求，一个小 矩形区域只能在所有紧靠它上方的矩形区域都喷过漆后，才能开始喷漆，且小矩形区域 开始喷漆后必须一次性喷完，不能只喷一部分。为 Rob 编写一个自动喷漆程序，使 Rob 拿起喷枪的次数最少。 Print to PDF without this message by purchasing novaPDF (/) 第六章 随机化算法 教学目标 理解产生伪随机数的线性同余法 掌握数值随机化算法的特点及应用 掌握蒙特卡罗算法的特点及应用 掌握拉斯维加斯算法的特点及应用 掌握舍伍德算法的特点及应用 前面各章讨论的算法每一计算步骤都是确定的，而本章讨论的随机化算法允许算法在执 行过程中随机地选择下一个计算步骤，这种算法的新颖之处是把随机性注入到算法之中，该 策略使得算法的设计与分析更加灵活，其解决问题的能力也大为改观。 6.1 概述 随机化算法与现实生活息息相关，例如：人们经常会通过掷色子来看结果，投硬币来决 定行动，这就牵涉到一个问题：随机。 随机化算法看上去是凭着运气做事。其实，这种算法是有一定的理论基础的，且很少单 独使用，大多是与其他算法 （如贪心法、查找算法等）配合起来运用，求解效果往往出人意 料。 6.1.1 随机化算法的类型及特点 随机化算法的一个基本特征是：对所求解问题的同一实例用同一随机化算法求解两次可