POJ 2714
最近又在 POJ 上做题，碰上2714，题意是：
输入 N，和 N 个点 (x,y)，从原点开始一共可以走 N 步，每一步可以随机选择移动 (x,y)，或者 (-x,-y)。N 的范围为 1-100。
输出最远能走到离开原点多远的地方，输出其距离。
分析一下，用迭代肯定可以，不过 2^N 的复杂度肯定太高了。每步有两种选择，其本质是求一个长度为 N 的 0、1 序列使得最后的值最大，为一个优化问 题。这里贪心不能求到最优解，稍微证明一下就能得出。如果不贪心，或者把贪心的范围扩大一点，求出每一步完后的凸包呢，然后再在这步的基础上继续扩展下一 些节点，再求凸包，继续如此，最后求得凸包中距离最远的。求凸包的复杂度位 O(nlgn)，即最后的复杂度为 O(N^2lgN)，是可以接受的。
随机搜索
以前看过《集体智慧编程》这本书，这里有一章是说的优化。稍微回顾一下其中的几个算法。对于优化问题，首先得找到一个评价函数，对于其某个方案评价函数能给出某个值评估方案的优劣。至于返回值越大还是越好没有规定，对于特定的问题选择特定的评价函数。随机搜索不是一种好的优化算法，但是却是后面的算法的根源。其基本思想是，我们随机长生一些解，看是否好，如果比当前更好，替换当前最优解，直到收敛了，或者猜测了足够的次数了。
do{
solution=rand_solution;
value=eval(solution);
if(value>best)
best=value;
times++;
//测试是否收敛
}while(times<max_iter&&(!limit_flag));这种盲目的猜测虽然有机会在某一次猜中最优解，但是效率肯定不怎么好。随机算法还是有一些问题可以适用，比如素数判定，如果能保证错误率很低很低也是可行的算法。
爬山法
随机搜索不是一种好的优化方法，为什么？因为没有充分利用已经得出的当前最好解。对于上面这个问题，最优解可能和当前最优解有一些相近之处，可能是因为某一步当前最优解走错了，最后没有演变成最优解。其意思就是，如果把当前最优解稍微改变一下，可能会向最优解的方向靠 近。那么爬山法就是通过当前的最优解，在其附近找更好的解，知道当前没有更好的解为止。而随机搜索是跳越型的，所以没有这个优势。看下面这幅图，现实中很 多问题都会像这样，如果我们把所有解都算出来，按组合排列的顺寻作为 x 轴，评估函数得出的值为 y 轴，能得出稍微连贯的曲线。随机从某个初始点出发，沿着我们想要的方向寻找，能找到优解。
陷入局部最小 最优解为最低点
screen
爬山法的缺点是，如过找到某个局部最优的地方，可能就被欺骗了，因为发现没有斜率了，以为是最优解。最后可能是个次优解。所以继续改进。
模拟退火
爬山法总是接受当前最好解，也算是一种贪心的思想，正如贪心一样，有可能得不到最优解。如何改进呢？那就在选择的时候不止是选最好的，还要接受一些看其来不怎么好的解。模拟退火就是这样，“模拟退火”的原理也和金属退火的原理近似。其关键在于：如果新的解比当前解更优，即换为当前最优解，如果不优，新的解仍然可能成为优解，但是要一定的概率接受。这个时候神奇的 e 派上用场了，这个接受的概率我们可以算 作：p=e^(-(highest-lowest)/(temprature))。刚开始的时候温度很高，所以 p 接近为 1，后面温度开始降低，表现出来的结果就是越是到后面接受较差解的机会就越小。就是因为接受一定的较差解，模拟退火能找到最优解的概率比较大。
遗传算法
换一个思路，如果我们把搜索空间中的所有解看成一个个的物种，初始化随便初始化一些物种，然后随着自然的演变，我们需要最好的最强大的最优秀的最优生命力的物种保存下来。遗传算法就是这样，符合自然规律，符合进化论。和上面几种算法一样，随机初始化。为了得出优秀的后代，需要优秀的双亲进行杂交，或者称为配对、或者交叉。别想歪了，对于简单的二进制序列，就可以选 p1 的一部分和 p2 的一部分组合成为一个新的解，当然还有其他的方式。位了避免局部最优的陷阱，我们还需要变异，正如现实中人类总是需要变异的天才一样。对于序列，简单的变异就是改变其中的某一位或者几位。然后每一轮都进行排序，选择其中%10，或者%20 的优秀物种，继续上面的操作，直到解收敛或者达到一定的循环次数。这里可以改变的参数就比较多了，最大筛选次数，生存的比率和选择的方法，变异的比率，杂交的函数选择，变异的函数选择等等。
总结
上面的优化算法都是一个算法框架，如 A*算法一样，最后更多的细节比如评估函数或者参数的选择对算法的效果都有影响。另外这些优化算法最后能生效都是基于这么一个事实：很多优化问题最优解附近的解也是比较优的解，比如上面的问题，另比如旅行商问题。但有的情况，如下图，就是一个可能不被优化的问题，最优解附近并不是好的解，对于上面的算法都有随机性，也许随机优化一下能找到这个解（概率很小），也许遗传算法能产生个变异，但这都是概率问题，不能保证。
难优化的例子 最优解为最低点
screen
说明：上面的图来自《集体智慧编程》中，这是本不错的书，在网上有代码，python 写的，感兴趣的同学可以仔细看看。
我试着用遗传算法去解上面这个问题，参数调了很多次，最后还是能在一个可以接受的时间内得到所有正确的解。
代码在后面，写得很难看。gene_alg
