算法设计指南(The Algorithm Design Manual)

https://book.douban.com/subject/27092363/


关于深度优先搜索算法

深度优先搜索(DFS)做利用进入/离开时间将顶点有条不紊的组织起来,进而将边划分为树边和反向边。正是这种组织结构,才让深度优先搜索真正强大起来。`process_vertex_early/process_edge/process_vertex_late` 这3个callback, 以及加上 `discovered/processed/entry_time/exit_time` 来存储状态(这几个变量分别是,是否发现,是否处理,进入和离开的时间)


关于模拟退火和遗传算法

忘掉融化金属这回事而去关注优化吧。模拟退火(Simulated Annealing)之所以有效,这是因为它在解空间中处理质量较好元素所用时间要比处理质量较差元素的时间多得多,而因为它避免了重复的陷入同一局部最优解的困境。

遗传算法背后的这种思想极其吸引人。然而它在实际的最优化问题中表现的似乎不如模拟退火那么好。其主要原因有两个:第一,以遗传算子(比如位串上的突变和交叉的方式)对应用问题建模是非常不自然的。这种伪生物学让你与你所处理的问题之间隔了一层,从而提升了复杂度。第二,遗传算法在非平凡的问题上需要花很长的时间,交叉操作和突变操作通常对于问题定制的结构没有什么用,因此大多数转移都会导致较差的解,收敛速度会很慢。

我从来没有遇到过一个问题,让我感觉遗传算法是解决问题的正确方案。此外我也从来没有见过任何使用遗传算法,并见诸报道的计算结果能给我留下很好的印象。你若是需要启发式搜索算法,别犹豫,坚持选择模拟退火。


关于并行算法

加速潜力通常被一个较小的上界制约。假设你能使用20个处理器,这些处理器专门服务于你的工作且不能为别人所用,它们可以用于对最快的串行程序进行加速,并有潜力让加速比变为20。这当然很好,但是要能找到一个更好的串行算法,也许能获得更高的性能。你花在代码并行上的时间,也许应该去用在提高串行版本的性能上。相比并行模型模型而言,针对串行机器开发的如剖分程序等性能调优工具更好用。(好的并行算法很难开发和调试,优化串行算法工具和方法都比较多)

然而,要是在一台常见的并行机上运行某个易于并行化的代码,我们常常能见到一个精心设计的串行算法就击败了它。你的并行版本代码降到单处理器情况下,很有可能是一个较差的串行算法,因此加速性能这种计量指标通常无法公平的评测并行的优势。上述情况的一个典型例子出现在极小化极大(minimax)博弈树搜索算法中,该算法常用于计算机博弈程序。并行化一个蛮力的树搜索简单得令人尴尬:只需将每个子树放于不同的处理器上即可。然而由于不同的处理器会分析考虑相同的位置,许多计算量都被白白浪费。在串行情况下,从蛮力搜索转为更聪明的alpha-beta剪枝算法,可以轻易的节省99.99%的计算量,从而使并行蛮力搜索所获得的任何加速性能比在其面前都相形见绌。alpha-beta剪枝算法可以并行化但是不太容易,而且其加速比的提升速度慢的惊人。