论随机化算法的原理与设计
上海市控江中学周咏基
关键字随机化算法，稳定性摘要本文提出了一种新的解决信息学问题的算法随机化算法，并讨论了其原理与设计方法。论文首先给出随机化算法的定义，说明了由于“运气”的影响，必须对随机化算法的稳定性进行分析。然后分“随机不影响算法的执行结果”，“随机影响执行结果的正确性”，“随机影响执行结果的优劣”三种情况，以从基本算法到竞赛试题中用随机化算法有效解决问题的例子，详细分析了三种情况的随机化算法的原理与设计方法。最后总结出随机化算法的基本原理和共同性质，提出设计随机化算法的一般方法，并指出随机化算法的适用范围和一个有效的随机化算法应具备的特点
正文
1．引论
在这篇论文中，我们将研究一种新概念的算法随机化算法。顾名思义，随机化就是指使用了随机函数。这里的随机函数不妨是Borla
dPascal或TurboPascal中的RANDOMN，其返回值为0N1中的某个整数，且返回每个整数都是等概率的1。一个含有随机函数的算法很可能2受到不确定因素的支配。人们通常认为，一个受到不确定因素支配的算法肯定不是一个有效的算法正是在这种思维方式的支配下，随机化算法一直被冷落但是，在接下来的讨论中，我们将看到完全相反的事情发生：对于一些特定的问题，随机化算法恰恰成了十分有效的解题工具，有时甚至比一般的非随机化算法做得更好。随机化算法的定义随机化算法是这样一种算法，在算法中使用了随机函数，且随机函数的返回值直接或间接地影响了算法的执行流程或执行结果。根据这个定义，并不是所有的用了随机函数的算法都可称为随机化算法。例如，某个算法包含iRANDOMN，
36IOI’99中国集训队优秀论文选
f论随机化算法的原理与设计
但变量i除了在这里被赋予一个随机值之外，在其它地方从未出现过。显然，如果这个算法没有在其它地方用过随机函数，上面这条语句就无法影响执行的流程或结果，这个算法就不能称为随机化算法。另一方面，若一个算法是随机化算法，则它执行的流程或结果就会受其中使用的随机函数的影响。我们按影响的性质和程度分三种情况：1．随机不影响执行结果。这时，随机必然影响了执行的流程，其效应多表现为算法的时间效率的波动。2．随机影响执行结果的正确性。在这种情况中，原问题要求我们求出某个可行解，或者原问题为判定性问题3，随机的效应表现为执行得到正确解的概率。3．随机影响执行结果的优劣。这时，随机的r