2006 算法设计qiu-lec5

《2006 算法设计qiu-lec5》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、随机化算法（RandomizedAlgorithms）算法设计与分析¢Average-caseanalysisofdeterministicAlgorithmsDesign&Analysisalgorithms(确定性算法的平均情况分析)第五讲：随机化算法¢Expectedrunningtimeofrandomized华中科技大学软件学院algorithms(随机算法的期望运行时间)邱德红主讲2005年4月12Introduction:雇佣问题（TheHiringProblem)TheHiringProblem—AnIntroduction¢Problem(问题描述

2、)ßUseajobagencytohireanewofficeassistant(通过中介招聘新职员)Hire-Assistant(A)1current←aninfinitelyuselessdummyassistant(初值)ßEverydayweinterviewanewcandidateprovidedbytheagency(一天面试一个中介介绍2fori=1..n的候选人)3doifA[i]isbetterqualifiedthancurrent4thencurrent←A[i]5returncurrentßIfthecandidateisbetterqua

3、lifiedthanourcurrentofficeassistant,wefirethecurrentassistantandhirethecandidate(优胜劣汰)34代价模型（ACostModel）代价模型（ACostModel）¢Everycandidateweinterviewcostsuscidollars(面试代价)¢Question:Howmuchshouldweexpectßcdollarsfeetobepaidtothejobagency(中介费用)1topaywhenselectinganofficeassistantßcdollarstr

4、avelexpensesofthecandidate(候选人路2费等等)…outofncandidates?(n选一的期望支出为多少?)¢Ifwehirethecandidate,wehavetopaychextradollars(雇佣代价)ßcdollarsadditionalchargetobepaidtothejob3agency(因雇佣付给中介的额外费用)ßcdollarsinternaladministration(雇佣导致的内部管理4费用)561¢Generalanswer(问题解答):¢Worstcase(最坏情况):ßThecandidatessho

5、wupinincreasingorderofßWealwayspayc⋅ndollarsfortheinterviews(面试nqualification(越来越好)i个人的费用)ßThenwehireeverycandidate(每次面试的结果都是被招ßWepayc⋅mdollarsforhiringpeople,wheremis聘)hthenumberofcandidateswehire(andfire)intheßThecostisprocess(m个人获得雇佣的费用,比如给中介)c⋅n+c⋅nc⋅n+c⋅mihih¢Abstractproblem:Compu

6、tetheexpectednumber¢Bestcase(最好情况):ofcandidateswewouldhire.(问题:期望的m是什么?)ßThefirstcandidateisthebest(第一个最优)ßThenourcostisc⋅n+cih78概率分析(ProbabilityAnalysis)期望雇佣人数(TheExpectedNumberofHiredCandidates)¢Tocomputeexpectations,weneedaprobabilitydistributionoverallpossibleinputs.(欲求期望的m,则需要了解输入

7、的分布)¢Thenumbermofcandidateswehireisarandomvariablethatdependsonthe¢Forthehiringproblem(雇佣问题概率分析):giveninputpermutation.(与输入的排列有关)ßAssumethatnotwocandidatesareequallyqualified(互异)ßThenwecanrankthecandidates1,2,…,n(排序)ßWeassumethateverypossibleorder(permutation)ofthe¢Ourgoalistocompute