概率算法决策：随机优于优化的选择

算法设计与分析是中国科学技术大学计算机系黄刘生教授于2008年8月19日在国家高性能计算中心（合肥）讲授的一门课程。课程的核心内容围绕概率算法展开，旨在探讨在决策过程中，随机策略有时可能优于优化策略，尤其是在计算成本高昂而不确定结果的情况下。 在课程的第一部分，通过一个关于寻找宝藏的故事，教授引导学生理解概率算法的概念。在这个情境中，有两个可能的藏宝地点，但两者相隔很远，且存在一只每晚窃取部分财宝的恶龙。两种方案供选择：一是花费4天计算精确位置再行动，二是付出代价获取地图秘密，即允许在3天内到达宝藏地点，但需支付3天被窃取的财宝价值。 教授强调，即使不考虑冒险因素，接受小精灵的帮助也是更优策略，因为在计算出精确位置前，可能已经被龙偷走了更多的财宝。然而，通过分析，随机选择（如投硬币决定先去哪个地点）的期望赢利（x-7.5y）实际上超过了传统方法（x-9y）。这个例子揭示了随机算法的优势，即它能够在期望时间上取得更好的效果，尽管可能面临最坏情况下的不利影响。 课程深入探讨了期望时间和平均时间的区别。平均执行时间是指在所有等概率出现的输入实例中算法的平均运行时间，而概率算法的期望执行时间则是指对同一个输入实例反复运行时的平均时间，包括平均的期望时间和最坏的期望时间。例如，在快速排序中，随机划分策略被引入，学生们被告知在实际应用中，虽然简单的划分可能不是最快的，但它们在平均情况下的性能可能优于复杂而耗时的优化策略。 这门课程让学生们认识到，在实际问题解决中，特别是当优化算法的成本过高时，理解和掌握概率算法的理论和实践意义重大。通过这些实例，学生能够学习如何权衡风险和收益，设计出更加灵活和高效的算法解决方案。