Talk:Randomized Algorithms (Spring 2010)

From EtoneWiki
Jump to: navigation, search

请大家点击页面上方的“edit”进行留言和讨论 --etone 13:08, 11 January 2010 (UTC)


尹老师,你好!上次去听了你的randomized algorithms的课,很不错。但有几点疑问,描述如下: 1、你课件上说randomized algorithms有个特性是“简单”,能否举个例子,最好能跟这个例子的deterministic algorithms做下比较。 2、monte carlo式的randomized algorithms的结果怎么验证?比如min-cut这个例子,假设独立地执行karger算法10次,其中有一次结果是正确的,10次结果如下: F,F,F,F,T,F,F,F,F,F(T为正确,F为错误),问题是我怎么知道第5次是正确的。甚者,如果执行n(n比较大)才能得到一次正确结果,即使是人工验证也是很难的。不知道是否想错误了。 望老师有空解答下。

Re:
(1) randomized algorithm算法简单的例子有很多,例如karger algorithm明显就比确定算法计算min-cut的最大流算法简单。以后还会看到更多。
(2)课上讲的是:如果可以高效的检验结果的正确性,则poly-time monte carlo algorithm可以通过反复“尝试-验证”的方法转换为expected poly-time las vegas algorithm。
假如无法高效的检验结果的正确性,则该方法就不行了。例如你说的karger algorithm计算min-cut,我们不知道如何高效的检验一个cut是否最小,所以无法最终确定正确。课堂上讲了,通过反复运行,取所有返回cut中最小的一个cut,我们可以把error probability缩小到足够小,但无法缩小到0,即无法完全确定结果真的正确。(实际上,由于min-cut是P问题,我们可以运行最大流算法去确定地计算min-cut,和karger algorithm返回的cut比较就知道是否正确。理论上讲,这也算“验证”了结果的正确性,但这显然不是你的原意)
如果对于任何问题人类都知道怎么高效验证一个解的正确性,那么高效monte carlo算法就等同于高效las vegas算法,于是就有ZPP=RP=BPP了。然而目前这还是未知的。
--etone 10:07, 18 March 2010 (UTC)