如何求解问题

《如何求解问题》由会员分享，可在线阅读，更多相关《如何求解问题（121页珍藏版）》请在金锄头文库上搜索。

1、如何求解问题 -现代启发式算法,How to Solve It Modern Heuristics,主要内容：,传统方法： 穷举搜索、局部搜索、单纯形法、贪婪算法、分而治之法、动态规划法、分枝定界法、A*算法 现代方法： 模拟退火、禁忌搜索、演化算法、约束处理技术、神经网络、模糊系统,引言,理性的人努力使自己适应这个世界； 疯狂的人坚持使世界适应自己； 因此，一切进步取决于疯狂的人们。 -G.B.萧伯纳革命家箴言,这不是一次算法讲座，但其中充满算法，算法不是讲座主题。,讲座不仅为你提供必要的知识，更重要的是帮你拓展才能去构建新的问题和进行创造性的思维。 有效的求解问题的重要性从来没有现在这么强

2、烈。 不幸的是，我们的麻烦在生命的早期就已出现。甚至早到上小学时，我们被教导去分解问题，去孤立地解决更简单、更小的问题，我们被填鸭式地灌输着问题的求解方法，却从未思考是否有其他办法！大学课本亦然！,美国初三数学课本内容,一个农夫有一个长方形的农场，它的周长是110米，面积是700平方米，问农场的边长各式多少？ 学生们用本章学的方法建立方程 2x+2y=110 Xy=700 根据刚学过的知识，很快算出x，解决问题,美国初三数学课本内容,另一章是关于几何和讨论三角形性质的。末尾总结了一系列需要解决的问题。学生们毫不怀疑他应用这些定理来解决这些问题。 但是这看上去并不是正确的教育之道。问题和方法的关

3、系应该通过问题而不是对方法的讨论而得到。从长远看，这样弊大于利，它使的学生不能独立地思考问题！ 为了说明这一点，下面举例说明。,证明：AD+DBAC+CB,C,D,A,B,很明显，三角形内的线段之和必定小于三角形两边之和,有资料为证，此问题给本科生、研究生，甚至数学、工程、计算机方面的教授，他们中不到5%的人能在1个小时内解出这个问题，大部分人需要几个小时，还有些人根本就解不出来！ 有趣的的是这个问题出自美国5年级课本！ 如果你不能在1小时之内解决问题，那么此讲座正是为你而做！,证明：AD+DBAC+CB,E,定理：三角形的任意两边之和必大于第三边。,三个孩子的年龄有多大？,数学家遇见多年未见

4、的朋友。 朋友说：我的三个孩子都是今天的生日，你能算出他们的年龄吗？ 他们三个的年龄之积是36，年龄之和是那栋房子的窗户数。 数学家看过房子说：我还需要一点信息。 朋友说：我大儿子的眼睛是蓝色的。 数学家说：OK。我算出来了。,三个孩子的年龄之积为36,第一 第二 第三 36 1 1 18 2 1 12 3 1 9 4 1 9 2 2 6 6 1 6 3 2 4 3 3,年龄之和为房子的窗户数,36+1+1=38 18+2+1=21 12+3+1=16 9+4+1=14 9+2+2=13 6+6+1=13 6+3+2=11 4+3+3=10,如此推理,假如房子的窗户数不是13，那么数学家就会立

5、刻给出答案。但是，他说，还需要信息，因此只有两种可能的情况： （9，2，2） 或 （6，6，1） 父亲说“大儿子眼睛是蓝色的”， 所以三个孩子的年龄一定是： （9，2，2）,1 为何有些问题难以求解？,搜索空间中可能解的数目太多以至于无法采用穷举搜索法去找到最优解 问题是如此复杂以至于为了得到答案，我们不得不采用问题的简化模型，而实际上所得的结果是无用的 描述可能解质量的评估函数或者有噪声或者随时间而变化，因此需要的不仅仅是一个解而是一系列解的解集 可能解都被严格约束以至于构造哪怕一个可行解都是困难的，更不用说找最优解了 求解问题的人没有作好充分准备或存在某种心里障碍使得他们难以找到答案,几个

6、典型问题及其搜索空间,问题一：SAT问题 逻辑学的一个基本问题是布尔可满足性问题（Boolean Satisfiability Problem，简称SAT ），也就是使得包含一些布尔变量的复合语句取值为真。考虑以下包含100个布尔变量的范式：,问题是要找出每个变量 的真值指派，使得 。,可能解的空间有多大？,解空间S的大小是： 非常大！,此外，选取那种评估函数也不很清楚。我们希望评估函数有助于我们评价可能解的质量，越接近准确答案的值应该产生出越好的评估值。如果采用枚举搜索法，我们就不会在乎这些，只要一个一个地找，直到找到为止。但是如果想用评估函数指引我们比枚举法更快地找到最优解的话，那就不仅仅

7、是要知道“正确”与“错误”了。这就使得用于解SAT问题的方法立刻显得复杂起来。,问题二：TSP问题,有些问题看起来比SAT问题更简单，因为它们提供了自然的评估函数，甚至解空间的大小也是可数的。例如，考虑旅行商问题（Traveling Salesman Problem，简称TSP）。这个问题非常简单：旅行商必须以最短路径访问所有的城市一次且仅一次并回到出发地。,图1.1给出了一个简单的对称的20城市的TSP，图中每对城市i到j 的距离等于j 到i的距离。 即：dist（i，j）= dist（j，i）,TSP的搜索空间是什么？,可以看作是n个城市的排列的集合。n个城市的任意排列产生一个有序表，它决

8、定了所访问的城市的顺序，从商人的家所在城市开始，然后经过所有城市直至回家。最优解就是产生最小费用的那个排列。 注意，以下路径是相同的： 2- -6-15-3-11-19-17 15-3-11-19-17-2-6 3-11-19-17-2-6-15,搜索空间与评估函数,搜索空间的大小：n！/（2n） TSP的解空间大到令人无法置信！ 评估函数的选择 对于路径：15-3-11-19-17-2-6 Cost=dist(15,3)+ dist(3,11)+ dist(6,15),问题三：NLP问题,现在来看第三个例子：一个特定的非线性规划问题（Nonlinear Progamming Problem,

9、简称NLP）这是一个在科学文献中研究过的难题。迄今为止，还没有哪种传统的优化算法能给出一个令人满意的结果。事实上它是非线性规划问题11个测试函数中的第二个。,问题是求函数：,的最大值，使满足条件,其中,解空间是多大？,函数G2是非线性的，它的全局最大值未知，但存在于原点附近。它的解空间是多少呢？如果精确到小数点后第6位，那么每个变量就有10000000=107个取值，因此搜索空间的大小是：107n 这个值要远远大于相应的TSP的解的数目。即使n=50时，NLP的可能解在取6位小数的精度时，达到10350个！,评估函数如何？怎样评价不同解的质量？,有一种方法是将G2本身作为评估函数，使函数G2取

10、值更大的解被认为优于使其值更小的解。问题是，如图所示，图中有不可行区域，并且所有不可行点被置为0。可行区域和不可行区域的边界由等式 来限定，并且最优解靠近这个边界。即使没有这个额外的难题，仅仅凭其可供选择的解的数目之巨大就足以看出这些看似简单的问题所面临的巨大挑战，由此可见，评估这些解的方法并不总是显而易见的。,2 几个基本概念,求解问题的所有算法有三个基本概念是相同的，不管采用什么技术，都必须确定： （1）表示方式对可选择的候选解进行编码 （2）目标描述了要达到的目的 （3）评估函数给出了给定表示方式下的任 意特定解的质量,这是一个极好的例子,给你6根火柴棒，你的任务是以他们为边搭建起4个等

11、边三角形。很容易用5根建立起两个这样的三角形，却很难将它扩展到4个三角形，特别是只剩下1根火柴棍。,从一个错误的搜索空间开始，你将永远不可能找到正确答案,四个等边三角形，6根火柴,定义一个搜索问题,现在定义一个搜索问题。给定搜索空间S和它的可行部分FS，要求找到某一xF，使对所有的y F，有 Eval（x） Eval（y）（极小化问题） 满足上述条件的点x叫做全局解。 找到问题的这样一个全局解是很困难的！,邻域和局部最优解,S搜索空间,x,N（x）,如果对于所有的y N（x），都满足Eval（x） Eval（y），那么x就是局部最优解。,X的邻域,爬山法 （hill-climbing meth

12、od）,就像所有的局部搜索算法一样，都是运用迭代改进的技术。 每次迭代从当前点的邻域中选取一个新点，若新点的评估值优于当前点，它就变成当前点；否则就选取当前点邻域中的其他点来比较。 很明显，这种爬山法只能提供局部最优解。,简单迭代爬山法的思想,现在有很多种爬山算法，主要是在新解与当前解进行比较的方式上有所不同。 开始时，当前解的所有可能邻域都被考虑，并且将具有最好评估值eval（vn）的点vn与当前点vc做比较。 若eval（vc）比 eval（vn）差，则新点vn就成为当前点；否则，则没有可能再进行局部改造：该算法已经达到局部最优或全局最优（变量local=TRUE） 在这种情况下，算法的下

13、一次迭代（t=t+1）随机选取一个新的当前点来执行。,Procedure 迭代爬山法 Begin t=0 初始化 best repeat local=FALSE 随机选取一个当前点VC 评估VC repeat 在VC的邻域中选择所有新点 从这个新点的集合中找使评估函数eval的值最优的点Vn if eval（Vn）好于eval（Vc） then Vc= Vn else local=TRUE until local t=t+1 if Vc 好于best then best= Vc until t=MAX end,简单迭代爬山法,3 传统方法第一部分,穷举搜索 局部搜索 单纯形法,穷举搜索 （ex

14、haustive search）,检查搜索空间中的每一个解直到找到最好的全局解。 如果要解决的是一个小问题，并且有时间去枚举出整个搜索空间时，保证你能用穷举法找到最优解。 如果面临一个较大的问题，不要用此法，因为你永远也无法列举完所有情况。,局部搜索,1、从搜索空间中找到一个解并 进行评估其质量，将它定义为当前解。 2、变换当前解为一个新解并评估它的值。 3、如果此解比当前解更好，则将当前解用 新解替换，否则抛弃新解。 4、重复2、3直至在给定集中找不到改进解。 此类算法的关键：变换类型。,线性规划,单纯形法-1947年，美国空军服役转任斯坦福大学的科学家丹茨格教授。 椭球法1979年苏联名不

15、见经传的数学家哈奇扬。 内点法-1984年，美国贝尔实验室年轻的印度裔数学家卡马卡。,运筹学的主要分支：,一、 线性规划 二、 非线性规划 三、 动态规划 四、 图与网络分析 五、 存储论 六、 排队论 七、 对策论 八、 决策论,4 传统方法第二部分,贪婪算法 分而治之法 动态规划法 分枝定界法 A*算法,贪婪算法(greedy algorithm),贪婪算法通过一系列步骤构造完整解来解决问题。这个算法流行的原因很明显：简单！贪婪法的基本思想出奇的简单：一个一个地为所有的决策变量赋值，在每一步作出最佳的决定。当然，这个过程假定了一种决策的启发式思想，即在每一步作最好的移动，以获得最大的“好处

16、”，这就是“贪婪”这个名字的来由。但是这种方法也是目光短浅的，因为每一步作出最佳决定并不一定最终能得到全局最优解。,贪婪算法和SAT问题,对从1到n的每个变量，不分次序，指定一个真值，使其尽可能地满足最大数目的当前未满足子局。如果不分胜负，则随机选择一个最好赋值。 将所有变量按照它们在子局中出现的频率，从大到小进行排序。 依照上面次序，对每个变量进行赋值，使满足最大数目的当前未满足子局。如果不分胜负，则随机选择一个。 根本找不到一个解决SAT问题的贪婪算法！,方法1 方法2 方法3 对于每一种你能想象的常识性启发式规则，都能找出一个特例使得这种规则看上去非常愚蠢！,贪婪算法和TSP问题,对于NLP问题确实