算法设计与分析
黄刘生
中国科学技术大学计算机系
国家高性能计算中心(合肥)
2008.8.19
Ch.1 概率算法
1. 故事:想象自己是神化故事的主人公,你有一张不易懂的地图,上面描述了一处宝藏的藏宝地点.经分析你能确定最有可能的两个地点是藏宝地点,但二者相距甚远.假设你如果已到达其中一处,就立即知道该处是否为藏宝地点.你到达两处之一地点及从其中一处到另一处的距离是5天的行程.进一步假设有一条恶龙,每晚光顾宝藏并从中拿走一部分财宝.假设你取宝藏的方案有两种:
§1.1 引言
方案1. 花4天的时间计算出准确的藏宝地点,然后出发寻宝,一旦出发不能重新计算
方案2. 有一个小精灵告诉你地图的秘密,但你必须付给他报酬,相当于龙3晚上拿走的财宝
Prob 1.1.1 若忽略可能的冒险和出发寻宝的代价,你是否接受小精灵的帮助
显然,应该接受小精灵的帮助,因为你只需给出3晚上被盗窃的财宝量,否则你将失去4晚被盗财宝量.
但是,若冒险,你可能做得更好!
§1.1 引言
设x是你决定之前当日的宝藏价值,设y是恶龙每晚盗走的宝藏价值,并设x>9y
方案1:4天计算确定地址,行程5天,你得到的宝藏价值为:x-9y
方案2:3y付给精灵,行程5天失去5y,你得到的宝藏价值为:x-8y
方案3:投硬币决定先到一处,失败后到另一处(冒险方案)
一次成功所得:x-5y,机会1/2
二次成功所得:x-10y,机会1/2
§1.1 引言
}期望赢利:x-7.5y
2. 意义
该故事告诉我们:当一个算法面临某种选择时,有时随机选择比耗时做最优选择更好,尤其是当最优选择所花的时间大于随机选择的平均时间的时侯
显然,概率算法只能是期望的时间更有效,但它有可能遭受到最坏的可能性.
3. 期望时间和平均时间的区别
确定算法的平均执行时间
输入规模一定的所有输入实例是等概率出现时,算法的平均执行时间.
概率算法的期望执行时间
反复解同一个输入实例所花的平均执行时间.
因此,对概率算法可以讨论如下两种期望时间
平均的期望时间:所有输入实例上平均的期望执行时间
最坏的期望时间:最坏的输入实例上的期望执行时间
4. 例子
快速排序中的随机划分
要求学生写一算法,由老师给出输入实例,按运行时间打分,所有学生均不敢用简单的划分,运行时间在1500-2600ms,三个学生用概率的方法划分,运行时间平均为300ms.
8皇后问题
系统的方法放置皇后(回溯法)较合适,找出所有92个解 O(2n),若只找92个其中的任何一个解可在线性时间内完成O(n).
随机法:随机地放置若干皇后能够改进回溯法,特别是当n较大时
判断大整数是否为素数
确定算法无法在可行的时间内判断一个数百位十进制数是否素数,否则密码就不安全.
- 数值计算方法习题答案 > 算法设计与分析
-
算法设计与分析
下载该文档 文档格式:PPT 更新时间:2008-11-02 下载次数:7 点击次数:49文档基本属性 文档语言: 文档格式: ppt 文档作者: Image 关键词: 主题: 备注: 点击这里显示更多文档属性 经理: 单位: 2ndSpAcE 分类: 创建时间: 上次保存者: lshuang 修订次数: 222 编辑时间: 文档创建者: 修订: 加密标识: 幻灯片: 132 段落数: 1489 字节数: 2520767 备注: 80 演示格式: 在屏幕上显示 上次保存时间:
- 下载地址 (推荐使用迅雷下载地址,速度快,支持断点续传)
- PPT格式下载
- 更多文档...
-
上一篇:第三章习题答案.doc-阻的点位不同,列写方程时要注意自电导和互电导...
下一篇:第七章 卡平方(χ2)测验
点击查看更多关于数值计算方法习题答案的相关文档
- 您可能感兴趣的
- 数值计算方法习题 数值分析习题答案 清华数值分析习题答案 数值分析课后习题答案 数值分析基础习题解答 数值分析习题 数值计算方法课后答案 数值计算方法答案 数值计算答案
- 大家在找
-
- · 场效应管应用电路
- · 管理运筹学韩伯棠
- · 西门子840d视频讲座
- · 丰炜plc编程软件
- · pes2011最新球衣
- · 国电长治热电厂
- · 东莞二手手机
- · bemybaby
- · 华南师范大学资源网
- · 黄奇帆与葛红林
- · 金正日视察美女
- · 奔奔mini改装包围
- · 上海劲雕起重设备厂
- · 棒料的自动送料装置
- · 中兴安全工程师
- · 口腔医学考试网
- · xp系统自带全拼输入法
- · 重庆铜梁桂花节
- · 植物保护技术试题下载
- · 《思想道德修养与法律基础》教案
- · 李娜身份证
- · 四季橘的图片
- · 长江大学西校区
- · excel的全套财务表格
- · 重庆国贵贸易有限公司
- · 武汉膜片钳
- · 高中物理力学计算题
- · 东华大学研究生学费
- · 大学国际贸易考试题
- · 2008年湖北省费用定额
- 赞助商链接