最优化

译 By Murphy Shang

什么是最优化?

让程序更快

注意：除非你的程序已经正常工作，不要试图优化它，那样会使调试更复杂。而且，在优化以前，将程序备份。没有比优化后程序崩溃而没有备份再痛苦的事了。

本文集中在无法优化算法的情况下优化程序。如果有更快的算法，应该努力实现它，而不是让一个笨拙的算法稍微快一些，那样跟往猪身上抹香水是一样的。

主要，本文只讨论通过剪枝来对搜索算法优化。

题目:数列

假定必须通过乘除运算找出 xⁿ 的精确值(不能含log/exp)。这个过程中需要的中间结果分别是多少？按顺序写出项数最少的数列的所有项。

为了简便，我们只写出它们的指数。乘法将写作两数的和,除法将写作两数的差。 对于一个正确的方案，每一个数都应是前面的数的和或差。所以,计算x⁸ 将需要1 2 4 8；计算x¹⁵ 需要1 2 4 8 16 15。

数据规模 1

所有的幂都不大于50。运行时间在Pentium II 233 MHz上得到。

基本算法

从集合{1}开始,进行深度优先搜索(从以前的数中找出两个,将他们的和或差放入队列,依此类推).

这有什么错误?

它不会停止，因为没有加入停止条件。

所以，对于所有长度已经大于32的队列，进行剪枝。

运行时间： 4658.34 秒。

基本优化

剪掉出现过的，剪掉常出现的(原文就是这么罗嗦^-^)

注意：在二叉树的一个分支中连续两次剪枝，结点的数量就会变为四分之一。

两个让程序运行更快的思想：

·                     Don't Do Anything Stupid

·                     Don't Do Anything Twice

找出已扩展和没有用的节点。所有的优化都会利用简单的事实。确保它是正确的！

改进的方法

注意1

这里有一个简单的方法来生成数字，或至少可以计算上界。考虑数字的二进制形式。先计算出所有需要的2的幂，然后将需要的相加（当然最后答案有可能是相减，但我们没必要求出最优解，用这个方法求最优解是难以实现的）。它就是目前已知的最优解，所以一些很长的数据就会被剪枝。

例如， 43化为二进制是101011。那么,数列的起始应该是1 2 4 8 16 32。然后，将需要的相加，所以下一个数是1+2=3，然后是3+8=11，11+32=43，这样生成了一个长度为9的数列1 2 4 8 16 32 3 11 43。

运行时间: 4609.81秒.

评价：这刚刚是优化的开始。这个方法实现起来很简单，能剪掉一些结点，但不会起太大作用。

注意2

生成负数是愚蠢的举动。不要生成它们。假如第一个生成的负数是-42。注意-42 是作为两个数的差产生的，所以42也会同时生成，而且在以后的生成中，二者起同样的作用。当然，不生成-42是最好的。

新的运行时间: 387.34秒

生成0也是愚蠢的。生成它不会带来任何作用。剪掉任何包含0的结点。注意，加或减0都会生成相同的数，所以任何含0的结点都应该被剪枝。另外，含0的结点一定会生成负数，上面已经说过，这是没用的。所以，它应该被剪枝。

新的运行时间: 43.24秒

评价：两个简单的剪枝使运行时间缩短了100倍。它们很容易实现而且起到巨大的作用，是极好的剪枝。

注意#3

在一步中，能够生成的最大的数是目前最大数字的2倍。那么，如果目前最大的数乘以2^(目前的步数被最优解的步数减)小于目标，在最优解的步数中它是得不到目标值的。可以剪枝。

运行时间: 0.15秒

评价：实现有一点难度，但是它使运行时间缩短300倍，所以这是值得的，对于一般的时限来说，它都能解决。

增加数据规模

目前程序很快，我们应该增加数据规模了。新的数据中幂不大于300，运行时间是93.21秒。

注意4

为什么不使用可变下界搜索呢？结点的增长随着层数增长，所以结点的质量越来越小。

运行时间: 93.05秒。

评价：既然这样,从数据看这是一个不强的优化(慢慢会好起来)。它使程序代码产生了很大的改变，出错的机会增加了，还没有带来任何好处。这令我们有点惊讶，它一向有很大作用。

注意5

最近的操作必须使用next-to-last数。如果不用，生成它干什么?（这句话是The most recent operation must use the next-to-last number created. If it didn't, why bother generating that number，我翻译不通） (现在就呈现出可变下界深度优先搜索算法)。

运行时间: 7.47 秒 。

注意6

不要复制已有的数。

运行时间:：3.40 秒

检查

这样, 除了可变下深度优先搜索以外，只有“Don't Do Anything Stupid”这一原则被体现了，执行时间减少了约842,510倍。这是好的，但也许可以再提高。

增加数据规模

新的数据中幂不大于500，运行时间是206.71秒。

注意7

如果一个数列的前缀没有得到解，在后面加什么数也没有用。例如，如果1 2 4 8 7得不到解，就不用尝试1 2 4 8 16 7了。

运行时间： 53.70 秒

注意8

如果选择了i,数列中最大的数是j,而且i+j小于下一个需要的数,那就不要选择i。

运行时间: 44.52 秒。

注意9

如果一个数列生成 x (x不是目标)用了j项，而且存在另外一个数列用了少于j项，我们应该用这个短的数列把它替换掉，获得一个“更好的”数列，这是最佳的。

错误!

第一个反例: 10,127.用这种方法得到的解是17项，但是存在一个16项的方法。

这就是优化的风险：有时候，会得到错误结论。确保你不会掉入陷阱.

总结

8个优化使运行时间缩小400万倍。可以使不大于500的数据在44.52秒内出解。有的程序可以在640k内存限制的情况下1.91秒内出解(无限制时0.85秒)。看看你的程序有多快。