算法分析与设计里的概率算法-概率算法.pptxVIP

算法设计与分析

黄刘生

中国科学技术大学计算机系

国家高性能计算中心（合肥）

1

§1.1引言

1.故事：想象自己是神化故事的主人公，你有一张

不易懂的地图，上面描述了一处宝藏的藏宝地

点。经分析你能确定最有可能的两个地点是藏

宝地点，但二者相距甚远。假设你如果已到达

其中一处，就立即知道该处是否为藏宝地点。

Ch.1概率算你到达两处之一地点及从其中一处到另一处的

法距离是5天的行程。进一步假设有一条恶龙，

每晚光顾宝藏并从中拿走一部分财宝。假设你

取宝藏的方案有两种：

2

01方案1.花4天的时间计算出准确的藏宝地点，然后

出发寻宝，一旦出发不能重新计算

02方案2.有一个小精灵告诉你地图的秘密，但你必须

付给他报酬，相当于龙3晚上拿走的财宝

03若忽略可能的冒险和出发寻宝的代价，你是否接受

1.1引言小精灵的帮助？

04显然，应该接受小精灵的帮助，因为你只需给出3晚

上被盗窃的财宝量，否则你将失去4晚被盗财宝量。

05但是，若冒险，你可能做得更好！

3

设x是你决定之前当日的宝藏价值，设y是恶龙每晚盗走

的宝藏价值，并设x9y

方案1：4天计算确定地址，行程5天，你得到的宝藏价值

为：x-9y

方案2：3y付给精灵，行程5天失去5y，你得到的宝藏价

值为：x-8y

1.1引言