How to Solve It: Modern Heuristics

http://blog.csdn.net/feliciafay/article/details/6200509

@@问题=>模型=>求解

求解问题的时候，我们其实往往是先把问题描述为一个模型，然后给问题的模型求解

@@证明问题的基本思路

1演绎法

2归纳法

3反证法

4把这个问题转换为它的逆否命题再做证明

@@对算法进行分类

第一类：评估子空间而非个体解

贪婪算法、动态规划、分枝界定法

第二类：将整个搜索空间看成潜在解的统一集合，只评估单个完整解，而没有子空间的概念。

        爬山法、模拟退火、禁忌搜索

第三类：演化算法

       结合以上两类的特点，允许个体既描述子空间，又描述特定解

@@候选解的组织形式

SAT问题可以用树的形式来组织，这样可以方便剪枝等操作。

@@如何设计评估函数？

评估函数可以比目标函数更加简单，这样可以提高效率。

@@对参数调整进行分类

1)运行前的参数调整

2)运行时的参数调整

         2.1)确定性的

         2.2)适应的

         2.3)自适应的

@@关于演化算法

1 由所解决任务的候选解构成一个种群，通过随机变化和选择等一代代演化下去。其中随机变化提供了发现新解的机制，而选择则确定了保持哪些解作为下一步搜索的基础。

2 如果没有办法快速找到完美解，那么应该退而求其次，尝试快速产生近似最优解。

一些疑惑存于心中，我接下来会把以下问题弄清楚。

1什么样的问题适合动态规划？

2模拟退火与禁忌搜索的异同比较

3书中谈假设检验时用了下面的说法：我们即使有再多的证据也不能说“接受”零假设，我们只能说不拒绝零假设。

这样的表述反映了假设检验的怎样的实质？我需要好好研究一下。

http://blog.csdn.net/feliciafay/article/details/6203923

如果说这本书的主菜是对启发式算法的介绍，那么开胃酒就是点缀其间的小问题了。如果把这些每个小问题整理整理，形成若干小主题，那么将会非常有意思。

主题一 扩大你的搜索空间
1 卓上有六根火柴棒，请搭建四个三角形。
问题的形式暗示这是一个二维的平面，这个形式误导了我们，使我们限制于此空间，难以求解。
 

然而，如果改变搜索空间。比如，假设是在三维空间中，六根火柴就可以完成搭建四个三角形的任务。

 

2 过河修桥问题
如下图所示，我们需要在城市A与城市B之间修建座桥，但是两个城市被河流给分隔开。我们需要使这两个城市之间的道路的总路程最小，且桥必须建得和河水垂直，该如何修桥？
 

常规思路，列式表达出AB之间的道路的距离，计算量很繁琐。

换一种想法，求AB之间的道路的距离的时候，我们其结果发现和桥的位置虽然相关，但是最后其实并没有包含桥的长度。这样，问题可以被转换为一个常见问题。

想象河流的宽度逐渐缩短到零，那么AB间的最短距离就是线段AB。现在，河流的宽度虽不为零，但可以把B点上移桥宽的距离至新的B’点，这样AB’就是要求的最短距离了，而AB’和桥岸的交点就是河道修建的位置了。

 

3 台球的运动轨迹
假设有个台球被撞击了一下，然后无限地在桌面上运动了起来，它遵循物理学的一个基本定律，角α总是等于角β，那么，在什么情况下台球会在桌面上做往返运动?

假设台球只反射1次，我们很容易作出到如上图所示的图画，然而，如果台球反射10次，我们的思维就会乱掉。

如果扩展问题的空间，问题会简单许多。当球反射第一次的时候，其实以下两幅图是等价的。
 
顺这个思路继续，每当球进行了一次反射，我们就扩展一次桌面，那么最后将出现如下图所示的结果：

也就是说，如果球能够回到原始位置，说明它将形成如上图所示的造型，
也就是说，经过水平方向的p个桌子和竖直方向的q个桌子。
也就是说，tan(α)=p/q，即tan(α)是个有理数。

主题二 不同的假设带来不同的结论

大前研一在《思考的技术》中强调的最核心的一句话便是：解答问题是有模型的，这个模型就是“假设-结论”模型。

这个模型提出的思维框架非常有力。它把你已有的一条条杂乱的思维线索以更明晰的方式组织了起来。虽然你的单独一条思维线索不能通过这个框架得到飞跃，但是它们之间相互构建的方式会得到改变。我认为这就是这个思维框架的优势。它没有花费大量时间成本去提升你的思维能力，它只用少量时间把原有的思维重新组合了一下却收效明显。这个模型很棒。

那么具体是什么模型呢？

常见的思维误区太渴望得到一个解答而忘记了其实可能有不止一个解答。

往往，解答可以有很多个。比发现一个解答更棒的，是发现一堆解答，比发现一堆解答更棒的，是发现在怎样的假设下会发生这样的解答。

案例来了，地面上有个半径为1的圆R，有个像两个方向无限延长的直线L丢在地上将圆分为两半。要求出该圆被切出的切弦的长度大于等于√3概率。

一方面，把切弦的中点叫做M，从上图可以看出来，如果中点M落在半径为R/2的小圆的范围内，那么切弦的长度小于√3，如果中点M落在圆环(大圆扣除小圆所形成的圆环)的范围内，那么切弦的长度大于等于√3。所以，所求的概率等于小圆的面积与圆环的面积的比值1/4。

另一方面，想象这条直线首先和圆相切，然后逐步向圆心靠近直到刚好切弦长度为√3，此时圆心距离直线R/2。也就是说，所求的概率等于R/2与R的比值1/2。

现在，发现这两个值居然不相等，是否有某个值计算出错？

其实，两个值不相等的真正原因是我们在求每个解的时候已经默认了随机线段的运动模型。对于第一个解，默认随机线段的中点在圆中是均匀分布的，对于第二个解，默认随机线段总是朝着一个方向运动而不发生旋转。

总结一下，这个问题真正的解决要点在于首先要识别出可能存在的假设，然后还要理解不同的假设如何对应不同的结论。