博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
算法导论5.1 雇用问题
阅读量:5858 次
发布时间:2019-06-19

本文共 3470 字,大约阅读时间需要 11 分钟。

第五章围绕概率分析,随机算法,概率与期望展开了一系列有趣的讨论,其中许多有趣概率习题。
------------------------------------------------------------------------------------------------------------------------------------------------

雇佣问题描述:

假设你要雇佣一个新的办公室助理,雇佣代理每天想你推荐一个应聘者(连续推荐n个),你面试这个人,如果这个应聘者比目前的办公室助理更优秀,你就会辞掉当前的办公室助理,然后聘用这个新的。面试一个人需付给雇佣代理一笔费用,聘用办公助理也需要费用。

假设面试费用为Ci,雇佣的费用为Ch,假设整个过程中雇佣了m次,于是总的费用是 nCi+mCh。由于n是固定值,总费用的变化取决于m值。

这个场景用来当做一般计算范式的模型,通常情况下我们需要检查队列中的每个成员,并且维护一个目前的获胜者,来找出序列中的最大或最小值。雇佣问题是对哪一个成员当前获胜的更新频繁程度建立模型。

最坏情况

最坏情况下,我们雇佣了每一个应聘者,m=n。

HIRE-ASSISTANT(n)1  best ← 0     ® candidate 0 is a least-qualified dummy candidate2  for i ← 1 to n3       do interview candidate i4          if candidate i is better than candidate best5             then best ← i6                  hire candidate i 注意n个人总是要全部面试完的,所以面试的费用是一定的,关键在于雇佣几次是不确定的,取决于n个人的排名及先后顺序。

---------------------------------------------------------------------------------------------------------------------------------------------------

概率分析

事实上,我们既不能得知应聘者出现的顺序,也不能控制这个顺序,因此我们使用概率分析。概率分析就是在问题的分析中使用概率技术。为了使用概率分 析,必须使用关于输入分布的知识或者对其做假设,然后分析算法,计算出一个期望的运行时间

有些问题,我们对所有可能的输入集合做某种假设。对于其他问题,可能无法描述一个合理的输入分布,此时就不能使用概率分析方法。

在雇佣问题中,可以假设应聘者是以随机顺序出现的。假设可以对任何两个应聘者进行比较并确定哪个更优;换言之,在所有的应聘者之间存在这一个全序关 系。因此可以使用从1到n的唯一号码来标志应聘者的优秀程度。用rank(i)来表示应聘者i的名次。这个有序序 列<rank(1),rank(2),..., rank(n)>是序列<1,2,...,n>的一个排列。说应聘者以随机的顺序出现,就等于说这个排名列表是1到n的n!中排列中的 任何一个,每种都以相等的概率出现。

随机算法

在许多情况下,我们对输入分布知识知之甚少;即使知道关于输入分布的某些信息,也无法对这种分布建立模型。然而通过使一个算法中的某些部分的行为随机化,就常常可以利用概率和随机性作为算法设计和分析的工具

比如在雇佣问题中,如果雇佣代理给我们一份应聘者的名单,每天我们随机地挑选一个应聘者进行面试,从而确保了应聘序列的随机性。

更一般地,如果一个算法的行为不只有输入决定,同时也由随机数生成器所产生的数值决定,则称这个算法是随机的

由以上描述可知概率分析和随机算法的区别
概率分析是对输入做假设,假设输入服从某种分布(例如假设输入是随机的),然后根据假设的概率前提来分析期望情况。
而随机算法是通过一个算法来重新排列输入,使得输入变的随机化。
--------------------------------------------------------------------------------------------------------------------------------------------------

几道习题还是相当有难度的,网上可以搜到相关的解答
练习5.1.2

假设Random(a,b)以相同概率返回a到b之间的任何一个数字,描述Random(a,b)过程的一种实现,它只调用现有实现Random(0,1)。作为a和b的函数,你的程序的期望运行时间是多少?假设Ramdom(0,1)的运行时间是常数。

http://bbs.chinaunix.net/thread-1192193-1-1.html    上有一个讨论
思路1:
这个题目相当于在能随机生成 0, 1 的前提下,要求随机生成 n 个整数。(每个数生成的概率相等
把要生成的数标记为 0,1,2,..., n-1
取最小的 m,使得 2^m >= n-1
通过随机生成 0,1 的函数生成一个  m 比特整数(随机生成每一位),这样能随机生成 [0, 2^m) 内的整数。
随机生成一个 [0,2^m) 中的整数,如果这个数大小在 [0,n-1] 内,则取这个数为结果。
如果这个数在 [0,n-1] 外,则丢弃它,重新生成一个。

思路2:

k = b-a+1,如果k为偶数,则将S均分成两组,通过一次R(0,1)来淘汰其中一组;如果S为奇数, 则用上述方法来分组,将占多数的一组淘汰。可以证明这个算法后也是正确的。只要在某一轮的测试中R(0,1)的输出为全0或全1,问题的规模就可以缩小一 半。

思路3:
或者用二分的方式,根据Ramdom(0,1)是0还是1进入[a,b]区间的前半部分或者后半部分,这样同样面临如果区间长度不是2的整数次方,会导致每个数生成的概率不一样,应该再做一点处理,扩大生成的范围,像思路1中把不是范围内的数丢掉。

 -------------------------------------------------------------------------------------------------------------------------------------------------

练习5.1.3

假设你希望以各1/2的概率输出0和1。你可以自由使用一个输出0或1的过程 BIASED-RANDOM。它以概率p输出1,以概率1-p输出0,其中0<p<1,但是你并不知道p的值。给出一个利用BIASED- RANDOM作为子程序的算法,返回一个无偏向的结果。你的算法的期望运行时间是多少?

分析:设计的思路是利用对称性。 假设有两个基于BIASED-RANDOM的伯努利试验序列A、B。每个试验序列都会产生0,1值序列;每一轮A和B各进行一次,如果该轮试验的结果是 ai>bi(即ai=1,bi=0)则算法结束,结果为1;如果ai<bi则算法结束结果为0;如果ai=bi则开始下一轮迭代。

由于每一轮试验都是独立的,所以只要能够证明每一轮在得出结果的条件下,得出1和得出0的概率相等就可以了

while TRUE

do
x = BIASED-RANDOM
y = BIASED-RANDOM
if x != y
then return x
得出1的概率是p*q    (x得出1,y得出0)

得出0的概率是q*p  (x得出0,y得出1)

精妙!
-------------------------------------------------------------------------------------------------------------------------------------------------
总结:
第五章有许多有意思的习题,值得思考
参考:
算法导论
http://blog.csdn.net/longhuihu/article/details/5864442   csdn上某人的算法导论学习笔记
http://bbs.chinaunix.net/thread-1192193-1-1.html

你可能感兴趣的文章
css3 布局
查看>>
Hadoop CDH4.5 MapReduce MRv1部署
查看>>
JavaWS官方测试地址
查看>>
oracle11g ORA-12514错误
查看>>
doctrine 报错处理办法: Unknown database type enum requested
查看>>
循环队列
查看>>
Zabbix api脚本
查看>>
G7 HTC Desire Root提权 图文教程
查看>>
xampp安装 StatusNet 提示 Cannot load required exten...
查看>>
mysql安装小记
查看>>
cocos2d-x在win7下的环境配置
查看>>
iOS培训教程——用xcode创建hello world
查看>>
JAVA生成指定位数的随机数
查看>>
Windows 8 附件工具
查看>>
我的友情链接
查看>>
1. 预处理的工作原理
查看>>
switch case语法在oc中的运用
查看>>
酸奶×××升级成酸奶妈妈了!
查看>>
C语言权威指南和书单 - 初学者
查看>>
开发中常用的单词缩写
查看>>