2.4 Las Vegas algorithm课件.pptVIP

Las Vegas Algorithms 挣蠢狗舒穆晶仅咏咨息拱调表烂复蚌渴凋集聘固逾荐慰黑湍模玛未既屑慕2.4 Las Vegas algorithm课件2.4 Las Vegas algorithm课件 2 Summary Introduction n Queens Problems Factorizing Large Integers 剿梭危纂釉侮皇痊博弛萝柯茁椽询龙罩抉阁品撒谬亨镁遣惧扶雁怖幽贼揍2.4 Las Vegas algorithm课件2.4 Las Vegas algorithm课件 3 A Las Vegas algorithm is a type of randomized algorithm that uses a random value to make randomized choices and never produces an incorrect answer. The choices made during computation attempt to guide the algorithm to the desired solution faster than other methods. 搭雁宠硬鸟籽灯辰与倪镶违梯萧妆藉砧疑谊癸徊噶越七关默究涨酬兹帧咐2.4 Las Vegas algorithm课件2.4 Las Vegas algorithm课件 4 Make randomized choices to get to an answer quicker on average Never returns a wrong answer,but no answer is possible. Note: This is different than guaranteeing a right answer 殴饶胚陋漆举们等超膳舜沮兴晶想一最休吮抵登漆至赃收抉卷士印屁寂奸2.4 Las Vegas algorithm课件2.4 Las Vegas algorithm课件 5 Deterministic vs. Las Vegas Possible Outcomes Correct Answer Running Time Fast for a few Slow for most Possible Outcomes Correct Answer No answer Running Time The slow cases have a probability of going fast The fast cases have a probability of slowing down 雪熔窍亡拽汉舍释裴婪痢瞻赶袜去烘措因探舶兴一婆说僵欺爪筋端廓艇基2.4 Las Vegas algorithm课件2.4 Las Vegas algorithm课件 6 Las Vegas algorithms exist for problems with no known efficient deterministic algorithms Las Vegas algorithms have good expected performance for any instance to be solved since Deterministic algorithms could be vulnerable to an unexpected probability distribution of instances that may focus on the catastrophic worst-case instances 醒恶央味雀俐递阮幸家幂韦拢坦狱犁恩拢割空娇板柿搜沿坏烷卤维侩诚捷2.4 Las Vegas algorithm课件2.4 Las Vegas algorithm课件 7 Las Vegas algorithms have a p(I) probability of solving an instance I. The p(I) value tells us on average how many times we need to run to get an answer A correct Las Vegas algorithms should have p(I)0 for all input instances, in more strong sense, p(I)≥δ, δ0. 堰训纷叁甸钒嗓揩讲两顺芭录憨蕾吗琢誉奶礁缀滁腔佩突刘播蛰仕昔夹朴2.4 Las Vegas algorithm课件2.4 Las Vegas algorithm课件 8 RepeatLV(I) 1 repe