主题：【翻译】概率随机及编程 （一） -- 东方射日

东方射日:【翻译】概率随机及编程 （二）

下面让我们再看看另一个问题，GeneticCrossover该问题是处理条件概率的。这要求你基于它由它父母那继承来的基因来预言一个动物的适应性。注意一下问题的描述，基因有两种可能的情形，一是显性基因，不依赖于其他的基因；二是隐性基因，是否表现出来依赖与其他基因。

在第一种情形，假设P是某一显性基因表现出来的概率，那么P只有四种可能：

至少有一个双亲有一对显性基因（P=1）

双亲都仅有一个显性基因（P=0.5）

仅有一个双亲有有一个显性基因（P=0.25）

双亲均没有该显性基因（P=0）

现在我们在考虑第二种隐形基因的情形。这依赖性让事情变得有点复杂，因为双亲的基因也有可能是隐性基因等等。要判定一个一个隐性基因表现出来的概率，我们要判断该基因在染色体上被携带并传递下来这个事件的概率，为了让隐性基因表现出来，我们需要这个事件在双亲两边都发生。

以下是该问题的源代码，我们采用了递归：

int n, d[200];

double power[200];

// here we determine the characteristic for each gene (in power[I]

// we keep the probability of gene I to be expressed dominantly)

double detchr (string p1a, string p1b, string p2a, string p2b, int nr)

{

double p, p1, p2;

p = p1 = p2 = 1.0;

if (p1a[nr] ≤ 'Z') p1 = p1 - 0.5;

// is a dominant gene

if (p1b[nr] ≤ 'Z') p1 = p1 - 0.5;

if (p2a[nr] ≤ 'Z') p2 = p2 - 0.5;

if (p2b[nr] ≤ 'Z') p2 = p2 - 0.5;

p = 1 - p1 * p2;

if (d[nr] != 1) power[nr] = p * detchr (p1a, p1b, p2a, p2b, d[nr]);

// gene 'nr' is dependent on gene d[nr]

else power[nr] = p;

return power[nr];

}

double cross (string p1a, string p1b, string p2a, string p2b,

vector dom, vector rec, vector dependencies)

{

int I;

double fitness = 0.0;

n = rec.size();

for (I = 0; I < n; i++) d[i] = dependencies[i];

for (I = 0 ;I < n; I++) power[i] = -1.0;

for (I = 0; I < n; i++)

if (power[I] == -1.0) detchr (p1a, p1b, p2a, p2b, i);

// we check if the dominant character of gene I has

// not already been computed

for (I = 0; I ≤ n; I++)

fitness=fitness+(double) power[i]*dom[i]-(double) (1-power[i])*rec[i];

// we compute the expected 'quality' of an animal based on the

// probabilities of each gene to be expressed dominantly

return fitness;

}

随机算法

确定算法对于一个固定的输入总为产生固定的输出和同样的运行时间。随机算法则不同，它每次运算的运算路径，运算结果等都可能是不同的。基本上我们有两种随机算法：

门蒂卡罗算法（Monte Carlo algorithms）：可能产生错误的输出，我们只限定失败的概率（参考：外链出处）

拉斯维加斯算法（Las Vegas algorithms）：总产生正确的输出，唯一的变量是运行时间，我们研究运行时间的分布（参考：外链出处）

随机算法的主要目的是建立一种更快和更简单的解决方法。另一个好处就是能够处理一些困难的没有确定解决方案的问题。现在这些算法已经是大家感兴趣的研究方向并且已经找到一些针对困难问题的简单方法。（译者注：现在时髦的神经网络算法，遗传算法等在一定程度上就是随机算法的应用。神经网络算法中传递到下一层神经元的信号强弱和遗传算法中的基因突变都应用了随机的原则，感兴趣的朋友可以自己搜索资料）

还有一些问题有很多可能的解，其中一些是可接受的优化解（未必是最优解）（译注：原文中都使用了“optima”一词，但是依据上下文及我的理解，这里应该有优化解和最优解之分，传统的确定算法注重于寻找最优解，但是有些问题我们是无法以确定的时间、空间复杂度找到最优解，这种情况下我们往往转变注意力到寻找优化解，即是可以接受的解决方案，但并不一定是最优的。例如传统的背包问题就是这样一种问题，现在的数学除了穷举，仍旧无法在一个确切的时间、空间复杂度内找到最优解）。传统的方法是以一个确定的规则来一个个进行比较以寻找最优解。但是我们如果不能确定最优解在所有解中的位置，这样确定算法有时甚至无法在确定的时间找到最优解或优化解。随机算法的优势是不确定搜索的次序，这样，当优化解的集合是集中在某一区域的时候，随机算法（寻找优化解）的性能通常会比较好。例如“Queen Interference”(”8皇后问题”)

随机算法在面对恶意攻击是特别有效，在这种情况下对方故意输入错误的数据给算法。这在加密系统中有广泛应用。（译注：对这一段我还不是很理解，原文如下：Randomized algorithms are particularly useful when faced with malicious attackers who deliberately try to feed a bad input to the algorithm. Such algorithms are widely used in cryptography。）

随机算法在编程中也有其应用的意义，例如你有一个有效的算法，但是在一些退化的输入时，该算法会特别特别慢，那么你可以考虑随机算法。一个算法对各种输入都应该能在可以接受的时间内给出解答。否则即使是正确的，该算法也是不可行的。这就是我们在编程时特别强调“最坏情况下的运行效率”。

对程序的评判

如果你是编程竞赛的评委，你有15分钟的时间来检查其他程序员的BUG。这些提供给你的其他人提交的程序，在以下两种情况可能有时会引起你额外的注意：

一、提交的程序象是时间紧急时的仓促之作，对于大部分输入是失败的

二、算法经过比较彻底的测试，错误（或超时）的可能几乎是没有

对于第一种情况，你所要做的事是首先确定编程人员是不是一个成功的有经验的高手，如果是，在你考虑扔掉它前最好仔细研究一下他的算法，确定你了解他的用意。同时你要考虑一下其他因素，包括其他人对他的评价，算法的精确性，完成的时间，修改的次数等。（译注：本文作者是在topcoder，一个编程竞赛网站上贴的该文章，这段的意思是算法思路比实现算法更重要）

“随机”到底怎么用

在很多优化问题中，可行的优化解在所有可能解中的分布是不一定的。简单的方法是用一些不同的例子来观察算法的结果。做这样一个模拟通常相当快，且这试验本身也会给你提供一些解决方法的额外线索。

Max = 1000000; attempt = 0;

while (attempt < Max)

{

answer = solve_random (...);

if (better (answer, optimum))

// we found a better solution

{

optimum = answer;

cout << "Solution " << answer << " found on step " << attempt << "\n";

}

attempt ++;

}

练习：

略（这可是作者说最重要的一部分，俺咋就给略了呢？）