首页 > 试题广场 >

下列陈述错误的是（）

[单选题]

下列陈述错误的是（）

数值概率算法一般是求数值计算问题的近似解

Monte Carlo总能求得问题的一个解，但该解未必正确

Las Vegas算法的一定能求出问题的正确解

Sherwood算法的主要作用是减少或是消除好的和坏的实例之间的差别

查看答案及解析

huajian

数值概率算法（数值问题的求解，最优化问题的近似解）、蒙特罗卡算法（判定问题的准确解，不一定正确）、拉斯维加斯算法（不一定会得到解，但得到的解一定是正确解）、舍伍德算法（总能求得一个解，且一定是正确解）

发表于 2017-09-13 11:14:04 回复(0)

Yuerya

蒙特卡罗算法并不是一种算法的名称，而是是一类随机方法的统称。这类方法的特点是，可以在随机采样上计算得到近似结果，随着采样的增多，得到的结果是正确结果的概率逐渐加大，但在（放弃随机采样，而采用类似全采样这样的确定性方法）获得真正的结果之前，无法知道目前得到的结果是不是真正的结果。
从特性特性来说，我们知道，既然是随机算法，在采样不全时，通常不能保证找到最优解，只能说是尽量找。那么根据怎么个“尽量”法呢，我们我们把随机算法分成两类：

（1）蒙特卡罗算法：采样越多，越近似最优解；
（2）拉斯维加斯算法：采样越多，越有机会找到最优解；

举个例子，假如筐里有100个苹果，让我每次闭眼拿1个，挑出最大的。于是我随机拿1个，再随机拿1个跟它比，留下大的，再随机拿1个……我每拿一次，留下的苹果都至少不比上次的小。拿的次数越多，挑出的苹果就越大，但我除非拿100次，否则无法肯定挑出了最大的。这个挑苹果的算法，就属于蒙特卡罗算法——尽量找好的，但不保证是最好的。

而拉斯维加斯算法，则是另一种情况。假如有一把锁，给我100把钥匙，只有1把是对的。于是我每次随机拿1把钥匙去试，打不开就再换1把。我试的次数越多，打开（最优解）的机会就越大，但在打开之前，那些错的钥匙都是没有用的。这个试钥匙的算法，就是拉斯维加斯的——尽量找最好的，但不保证能找到。
---------------------
作者：bi_mang
来源：CSDN

原文：https://blog.csdn.net/bi_mang/article/details/52416258

Sherwood算法通过增加一个较小的额外开销从而使得算法的复杂度与具体实例x无关，虽然此时的算法仍有可能发生复杂度比较大的情况，但这种偶然行行为只是由于算法所做的概率选择引起的。我们可以通过多次执行算法来避免最差情况。

事实上几乎所有查找与排序算法都可以使用sherwood算法进行处理，排序算法在执行排序之前对数据进行随机打乱就是一个典型的方法。某些有序表的查找也可以在查找前随机找一个数进行比较，从而使算法具有较好的平均性能。

---------------------

原文：https://www.cnblogs.com/2010Freeze/archive/2011/09/25/2181016.html

编辑于 2019-03-21 23:28:27 回复(0)