作者：周爱民

题记：

＝＝＝＝＝＝＝＝＝

为拟这篇读后的标题，我花费了不少的功夫，最终我想起邹欣先生在他的博客上的一段文字，说的是上次博客堂年会上的预测之TOP。其中就有这样的一个关于书名的观点，正好引来作本文的开题。再加之本就是邹先生所述或所认可的观点，固而必当切合其书的本旨。 (http://blog.joycode.com/xinz/archive/2007/12/31/113262.aspx)

0、引子

＝＝＝＝＝＝＝＝＝

有一天，我问了方志远兄一个问题：有没有一本书，是有一个主标题，而有两个副标题的。志远兄答我说，明清或民国时期的书里可能会极偶然地有过，但那种做法在现在的书中，是找不到的。那时，我想我提出的问题大概已经足够奇怪了。

后来去北京参加SD2C，正好听周筠老师说要出版这样一册《编程之美——微软技术面试心得》，当时心里就打着小鼓：一本书怎么能既讲面试心得，又讲编程之美呢？这个书名的主副标题的风马牛之怪异状，大概可以同我的那个“两个副标题”并肩了。

很好，我仍是第一时间拿到了这本书的样章。本没有打算写书评，然而看完大概，又生出悲天悯人之心来：如同邹欣先生那本《移山之道》一般，如果仅是从标题看去，大概读者会陷死在作者设计的、需要以超过249的智商、并有着袋鼠腿般弹跳力的思维来解局的假象之中而不得脱身。如此充满异能色彩的标题，其本身就提出了一个（或许也可用于面试的）题目：主副标题的背后究竟有何玄机？

我认为自己智商能达到要求，可以象解述《移山之道》那样为大家解释一下这个书名，以免读者走了弯路。遂决定做一做这个题目，由是写了这篇读后。

1、多面性：唐僧团队

＝＝＝＝＝＝＝＝＝

在写这些文字之前，我正好读到一篇有关HR的文章，是讲人事经理如何看待“唐僧团队”裁员的。三种人事经理／主管分别从员工价值、阶段需求和工作内容方面提出了看法。我首先觉得，从人事部门来看，这些选择无可厚非。要么量人，要么量力，要么应事之需，所以也算得好办法。 (CIO思考:假如唐僧团队裁员你会先裁掉谁,  http://cio.csdn.net/page/6ee073ef-1fa8-4c8a-96d1-eba9041ac433)

然而，这并不见得是“唐僧团队裁员问题”的正确解法。因为这个问题本身是具有多面性的，不同的部门或人从各自的角度来看，都会有差异。但如果这时有一个“充要问题”提出，那么问题转变为单面的了——如果你能确认这个问题是其它任何问题的前提的话。

例如我发现，所有HR都没有提到这样一个充要问题：唐僧团队是拿来干什么的？

显然，我们只是要裁员，不是要否定这个团队的目标。所以无论如何解决问题，都不能影响这个目标的达成。而“唐僧团队”的目标，其实是“保护唐僧西天取经”（参见《西游记》原著）。由此问题变得很有趣了，在这个团队中，看起来最无能、最碍事的那个人，却是最不能被裁员的。因为那个人——唐僧是目标的一部分。

尽管这只给出了谁不能被裁，而不是“裁掉谁”的答案，但这说明：当问题由多面变为单面时，答案将变得清晰——哪怕这个答案不是最终的解。

2、目标：沙漠求生

＝＝＝＝＝＝＝＝＝

问题的多面性中，最容易看到也最容易被忽略的是“目标”。我们大多数人容易陷入对细节或具体问题的讨论，而忘掉讨论它的原因。

例如我刚到盛大时，接受过两天的内训。这个内训中有一个“沙漠求生”问题，说飞机迫降在沙漠中了，现有十件物品需要决定其重要性，以便在必要时使用或抛弃。这个问题是由不同的小组共同协商并给出答案的。我所在的小组开始了讨论：大家对各个物品逐一衡量，然后在较小的争议的情况下达成了一致，最后用了不到五分钟，便给出了答案。在交卷时，我问了一下：我们干么要决定物品的重要性呢？我们真正的问题“好象是”要逃生……但我的疑问没有被解决，答卷就交上去了。

内训后的评论中，讲师说：这是盛大最快的一次交卷。从答案的分数上来说，各位都很聪明，能较正确地选择这些物品。但只有一名同事提了一个问题：我们做这些选择的目的只是逃生，所以没有逃生计划的选择都是错误的。

在五分钟的时间里，我们没有推举出“逃生项目”领导者，没有制定出逃生的计划，也没有更详细的分析。我们小组用了5分钟证明大家都是可以交出90多分答卷的聪明人，但面对逃生项目，我们都失败了。

因为我们忽略了做这些选择，其原始的目标是什么。

3、从《编程之美……》到微软的人力策略

＝＝＝＝＝＝＝＝＝

很早以前，我就听说过“Google只招最聪明的人”、“微软只招最优秀的人”。这两个人力策略其实有一个一致的陷井：如何衡量。一个、或一系列问题的“答案”，是否是衡量优秀与聪明的标准呢？

当然不是。通过类似的衡量，我们小组在“沙漠求生”中成了“聪明的失败者”。聪明与否，不是从问题的答案就可以看出来的——能看出来的，是解决问题的能力。

《编程之美》列举了几十道精彩的试题，每个题目都有详细的分析和解释。你可能非常聪明，但却不会解答其中的任意一个问题。因为这些问题所展示的能力，并不见得是你所擅长的。换言之，这些问题不是为一个通常概念上的“聪明人”或“优秀的人” 而设定的，而是为一个职明或优秀的“程序员”而设定的。

在招聘这个问题上的“充要问题”是：招来人做什么？真正的答案是：你被招来做什么，决定了你的“优秀”与“聪明”如何被衡量。因此，如果你被招来做程序员（或其它类似的技术职位），那么（在微软亚洲工程院）衡量你方法，就是类似于《编程之美》中所列举的那些问题。

但是，微软并不只招程序员，IT业也并不仅仅需要程序员。

4、程序＝计算求值，但问题不总是有答案的

＝＝＝＝＝＝＝＝＝

如果我们把一个问题看成总是有结果的，那么我们总是可以把这个问题抽象为可计算的模型并求值。如果作为人——世界的观察者，我们面临的问题都是这种类型的，那种世界必然是程序化的。

然而，世界不是程序化的。所以，你面临的问题也不是必然有结果的。

我终于理解为什么这本书是叫《编程之美》，而将“面试”作为它的副标题。“在微软的技术面试”，在这本书中被局限在一个“做程序员”的范围之内。这本书设定的目标是：如果你想向微软证明你可以是合格的程序员，那么你就解决这些程序化的问题。

而我大概是没有这个“在微软做程序员”的命了，因为在我看来，问题的复杂性在于它的无解，而不在于它的有解。无解的问题如同一只海胆，你从哪方面看去都是问题，你必须拔了那些刺——既是问题的边角，也是问题的根源，然后你才会看到问题的真相：海胆原来只是一堆细胞。

5、你的目标是什么？

＝＝＝＝＝＝＝＝＝

如同“唐僧团队”问题所表现出来的：（若非特殊情况，）HR不会为某个团队需要什么人而招聘，HR的作用是为构建公司的人力体系而招聘。他的条件是“符合公司需要的（例如聪明的或优秀的）、有充分价值的”人才。前提是：这些人才的选择，是在某种领域中可量化考核的。

你的目标是什么呢？是微软吗？或者是微软亚洲研究院？更或者是一名开发人员？你的目标到底是一个公司，还是一份工作呢？你是热爱这个公司，还是热爱这个工作呢？你的目标所需要的能力是什么？你的能力又是什么呢？

这些都是问题。然而，如果你不弄清这些问题而去读《……——微软技术面试心得》，就不是问道于盲，而是盲人问道了。

6. 总结

＝＝＝＝＝＝＝＝＝

在我而言，邹先生的考题是“这本书的书名为什么是这样”，而我的答案是：看到问题的多面性，看到问题的目标。

一本书要作为两本书来读：编程之美讲编程，面试心得讲面试。至于书名上还写着的“微软”两个字，正好是作者组成员们的身份。一个书名里头讲了三件事，正好比我那个“两个副标题”的问题——虽然很奇怪，但总有其内在的道理。

书的好与不好，不要总盯在书名上。分开来看，这本书在编程与面试两个部分写得都非常精彩。“想做程序员”如同“想做科学家”一样，如今都快被人拿来做笑谈了，但是这两种意愿却完全没错，也相等同的崇高。所以想做程序员的人不必怕着了那些流言，自按自的道去走就好了。而同样的原因，这本书的精彩与不精彩，也不必听着了那些闲杂碎语，便有畏怯之心，摆正了一个程序员的心态，或者一个面试者的心态去读就好了。

这本书不会只给你答案，还会教给你思考问题的方法——所以它是一本好书。而我这篇文章， 并不是讲一本书好或不好的书评，而只是教给你思考问题的方法——所以它算不上一篇好的读后。然而我之现在，已然少了“好或不好”的评价欲望，时时升腾在我心中的，是面向问题时的那种折返不息的浪潮——我甚至不关心浪潮的扑打，而只把眼光投向洋流的来向。

原博客地址：http://blog.csdn.net/aimingoo/archive/2008/06/12/2541941.aspx

作者：InfoQ中文站总编辑 霍泰稳

      收到《编程之美》这本书的时候，我是悲喜交集的。喜的是可以从中了解一下微软是如何做面试的，和其他的软件公司有什么区别，这可能是我长期从事编辑的毛病，遇事总爱比较一番；悲的是我发现上面的绝大多数面试题目我都看不懂，更悲的是我还是一个计算机科班出身的人，看来今后再也不能随便给别人吹嘘我曾经还学习过什么数据结构、编译原理什么的。

      本书作者邹欣老师一直是我很崇拜的人，事业有成（在我看来毕业于国外名校，而且能在微软研究院待很久的人都是事业有成的），家庭幸福（夫人漂亮，小女考试经常双百），心态平和（很少见其动怒，总是一副深思的样子），而且文笔了得（已经写过一本《移山之道》的书，InfoQ中文站上有样章发布）。在我从前编辑《MSDN开发精选》的时候就打过交道，在和他的沟通中，了解到他的注意力不仅仅是自己在研究院里的一亩三分地，还常常发感慨说如何能为国内的技术社区多做点事情，如何能帮助的中国的开发人员多做点事情，我想《编程之美》的最终完成应该是符合他的这个感慨的。

      这本书的价值，我想看过此书的朋友应该是有所感触的，另外从这本书的畅销也能有所体察。在工作过程中，我也经常面试人，不论是从前从事软件开发的时候还是现在做编辑。经常困扰的一个地方是，通过和被面试者的交谈，我们可以基本了解这个人的品行、工作态度如何，但是要了解他的专业能力是难上加难。虽然一个人有了热情，可以在以后的工作中比较快地追赶上来，但是“万丈高楼平地起”又往往不是一个中小型公司所需要的，他们通常没有那么多的时间和财力来对新人进行培训。《编程之美》从某种程度上，我认为可以帮助软件公司里面的技术主管解决这个问题。另外一方面，很多时候，面试求职者又对所求公司的要求摸不着头脑，一轮一轮面试下来，一次一次打击下来，挫折感倍增。如果有内部人士将自己身居高堂的经验抖落一下，哪怕是点滴之言，对他们也是有百益而无一害。微软作为软件公司的代表，《编程之美》作为其面试过程的总结，应该可以帮助万千编程人员一解面试之苦。

    当然，如果只是照本宣科，从书中摘选一些题目用于面试，这肯定不是本书作者的原意。其实从书中我们可以了解到，作者更希望让面试者和被面试者都能够有所觉悟，都能够从“美”的角度看待编程，将编程人员和“IT民工”“软件蓝领”区别开来。话说回来，编程本是高尚的，只是不高尚的人误以为不高尚罢了。授之以鱼，不若授之以渔，希望读者能理解作者的苦心！

我们需要拟定计划、有步骤分阶段地执行，如此才能循序渐进，一步步朝目标前进。据微软的研究显示，过程应该分为6个阶段，分别是发现、探究、提案、执行、复查、收尾。这不一定适用于任何调校的情境，笔者从来也没有完全这么做，但却是个可供参考的方法论，能据以修正成自己的方法。有固定的准则后，才可以累积经验并加以分门别类。

现将各步骤的原文列出如下：

Ÿ  Discover the problem：发现问题。

Ÿ  Explore the conditions：探究原因，为问题提供明确的定义与定位。

Ÿ  Track down possible approaches：提供可能的解决方案。

Ÿ  Execute the most likely approach：执行最有可能的解决方案。

Ÿ  Check for success（如果需要的话，重复之前的步骤）：确认解决方案成功与否。

Ÿ  Tie up loose ends：完成收尾的工作。

1.3.1  各阶段重点说明

以下对各阶段稍做说明。

1.3.1.1  发现问题

这可能是支持性能调校的专家们花时间最少的一个阶段，因为大部分的工作都是用户在做，他们可能已经有一大堆的观察经验，而找你来，不会期望你完全重做一遍他们已经做过多次的事情，而是希望看到你马上采取一些行动，并一针见效。

这个阶段专业与否就看你是否可以立刻找到重点，把握住各个细节，而不是在整个调校的各个程序中，来来回回、反反复复询问相同的问题。这个阶段最重要的就是发现（Discover）问题、详述（Describe）问题，并且正确而详细地记录下来（Document）。在进入下一步骤前，你应该问问自己以下这些问题。

对于问题是否已经有简明的描述

若无法简明地描述问题，代表你尚不了解问题，或者没抓到重点。这是很有可能的，因为用户常拉拉杂杂地说了一大堆，让你晕头转向，只好急着做点东西，不见得是有方向，只是想摆脱用户像倾倒垃圾一样，噼里啪啦地描述现象时，还夹缠着抱怨与谩骂，大家一拥而上，对你一股脑儿地说个不停。信息虽然多，但零零碎碎看不到全貌。

你可以尝试将自己听到的，重新有序地整理一遍再诉说给用户听，看看是否符合大家共通的观点，若没有异议，就有了一个大致正确的开始。

用户的基线与期待在哪

在前面一节中强调了基线的重要，这让你可以比较成果，并有前进的目标。例如，当用户抱怨“SQL Server 跑得太慢了”，这时要理清他们的“慢”是怎么定义的，而什么是合理可接受的速度。若没有基线，则需要你为他们建立。

性能调校可能是一再循环的过程，除了时间难以掌握外，还不一定所有的问题都有解。不要让用户有错误或过高的期待，从而能减少承担不可能完成任务的压力，更可减少长时间调校后，达不到用户期望而招致的愤怒。

在查找的过程中尽量不要急躁或恐慌，贸然进入到下一个步骤，只会让你再一次回到原点，重新定义问题。

1.3.1.2  探究原因，为问题提供明确的定义与定位

确定用户的问题与需求后，下一步是探究原因，此步骤的重点是“探索（Explore）”、“找寻证据（Evidence）”、“建立（Establish）”描述整个问题来龙去脉的假设。

当你从以上步骤确切了解用户的问题后，就需要建立问题发生原因的假设和导致性能不足的运行模型，而当前这个步骤便是在搜集证据，以建立并确认该假设。在这个阶段中，你可以通过SQL Server Management Studio、SqlDiag.exe、性能计数器、事件查看器、SQL Profiler、SQL Server 2005 Performance Dashbord Reports、DMV与DMF等工具来找线索（以上工具在本书第3章“性能调校相关工具程序”中有详细说明）。

这个步骤的主要任务是广泛搜集相关数据，但并未深入分析数据间的关联性，这是下一步骤要做的事情。当然，要搜集正确而相关的证据，难免要稍做分析，但不要过度耗时在某项单一的事件上。此步骤要的是全貌，尽量了解系统的每一个方面，避免深入分析时，漏了某个关键现象而误入歧途。

当然，若在这个阶段就发现重大问题，一眼就看出关键点，例如，硬件毁损，某个硬盘区间或内存区间不稳，某个程序吃掉所有的内存，让SQL Server无内存可用，抑或是该程序常常出问题，拖垮CPU等，则可以跳过DETECT方法论之后的步骤，进行深入探讨这个问题并予以解决。

通常性能调校并不是那么容易一眼看出重大错误，或许用户自己就可以解决，而需要专门做性能调校的情况可能如战场上不断带来的伤患，第一步要做的是决定伤患的轻重，再决定如何利用有限的资源做最有效的治疗。当你在前一步获得用户大量的问题后，接下来就要搜集并探究各种现象，决定轻重缓急，通盘考虑后，进入下一步。

1.3.1.3  提供可能的解决方案

在深入分析前述两步骤搜集到的数据，并对整个问题的前因后果提出假设，进而拟出对应策略，如果前一个步骤做得不够详实，就可能误判，导致努力了半天，但没有碰到瓶颈点。

在拟定策略时，应当参考大量的在线说明、Knowledge Base，在网络上广泛查找资料，看看前人或是微软对于你所面对的问题是否有好的方案。到相关网站讨论区提出问题，或是询问技术顾问，最好不要闭门造车，防止解决问题时又出现新问题。

这个步骤最重要的是拟定计划，而这又可分为两个部分：用来证明对问题所建立的假设的计划，以及解决问题的计划。前文一再强调，性能调校可能是个一再循环的过程，有一个好的计划，你才能知道方向与步骤。

不要冲动地进入到下一步骤，信息界有句名言：“最早开始的，最晚结束”。言下之意就是凡事要谋定而后动，若匆忙进入到下一步执行解决方案，可能因为疏失而导致更多的错误，甚至因为你的操作让系统更为不稳定，原本性能不佳的系统宕掉了，这时会招致用户更大的不满。

1.3.1.4  执行最有可能的解决方案

这可能是DETECT 方法中最简单的一步，因为只要执行上一步中所拟定的计划即可。但是在执行计划时，仍然要注意系统的反应，随时都可能会要放弃当前的计划，因为新的证据可能证明先前的判断是错误的，因而要修正计划，甚至是退回到重新拟定计划。

随时反省，不要急着操作。每一步愈稳也就愈少反复，因此，现在的时间花费可以节省未来的时间（Spend time now to save time later）。整个性能调校的过程就是在考验团队的细心与耐力、知识的广度与深度，切勿急躁。

在这一部分执行的计划也有二个，分别是上一步拟定的：其一是对问题的假设，验证某些行为导致性能不足的计划；其二是解决问题的计划。先证明假设成立，再执行解决该问题的方案。若假设错误，当然就不需要执行解决方案。否则努力地重载了程序、变更了数据库架构、买了新的硬件等，却是验证了瓶颈点不在此，结果就尴尬了。

同时要小心观察你的计划会不会导致新的问题，并严重影响当前系统的执行，不要原来是系统迟缓，而你的测试却成了压垮骆驼的最后一根稻草。

1.3.1.5  确认解决方案成功与否

执行计划后，需要重新收集数据，以验证该计划成功与否。这一步骤又分两个阶段，第一阶段是确认计划是否证实了假设，若证实假设是对的，则需要继续搜集相关的数据，以确立接下来的步骤。

第二阶段是分析已收集到的数据，看看是否解决了优先级最高的瓶颈，若已解决，应有瓶颈转移的现象，此时要针对次要瓶颈开始拟定新的计划，并确定是否已经符合用户的目标。

如果执行结果不如预期，证明假设错误，会非常让人气馁。

其实，定错性能调校的目标是常有的事，这时就是要你在错误的面前，停下来好好思考，不要立刻行动。查看先前步骤的各项产出，重新理出头绪，最重要的是清楚知道这一回的错误在哪，如此新的步骤就会更逼近目标。犯错是常有的事，踩着错误走向成功是性能调校的常态。现在，你可以休息一下，喝杯咖啡，和合作伙伴放轻松，回顾一下这个过程，对整个问题建立更清晰的轮廓。

1.3.1.6  完成收尾的工作

前5个步骤循环重复地执行，每一次循环的结果都更逼近问题的核心，直到达到性能调校的目标。

但当我们完成目标后，依然要注意以下的问题。

Ÿ  解决的方式是否有边际效应而造成其他的问题？

例如，为了某类的查询工作建立了大量的索引，事后原本正常的添加、修改、删除都出现了性能问题。

Ÿ  是否真正根除了问题，还是仅表象地头痛医头，脚痛医脚？

建立问题的假设时，很容易将问题特殊化，仅局部地解决该问题。例如，加了某个索引或稍稍改变查询语句，舒缓了当前的瓶颈，但当用户稍微增加或采用不同的查询方式时，老问题就容易复发。

Ÿ  是否要建立持续跟踪的计划？

当你无法确定已经根除问题时，那可能就要拟定持续跟踪的计划了。决定是否要持续观察某些计数器，跟踪某些现象是否还会发生，若发生了要如何解决等。如此不但可以让用户安心，更可以让你知道之前的行为到底有多少效益，下次的性能调校才能提出更完整的解决方案。

摘自胡百敬著作《SQL Server 2005 performance tunning性能调校》

讲到Workflow，很可能有人会立刻想到比尔•盖茨常常向人推荐的一本书——《世界是平的》。作者托马斯•佛里德曼在他的著作中提到的抹平世界的十辆推土机，其中第三辆就是工作流软件。对照《Windows Workflow Foundation新一代工作流开发实务》书里的分析，再看看.NET Framework 3.0的出现，你应该可以感受到这股潮流。

很多人怀疑，从.NET Framework 3.0之后所增加的三大功能——WPF、WCF、WF中，WPF着重在炫酷的UI画面，WCF则减轻开发人员在现今复杂的多平台中沟通各种通信协议的痛苦，这些都很容易理解。可是，第三个“基础”，为什么是一般开发人员很少去注意的Workflow？为什么不是其他功能？不管过去你熟不熟悉Workflow，WF的出现，说明了微软把Workflow当作是未来软件开发中，必然被重复使用的一个关键技术（因而称为“基础”，Foundation），也因为WF自然地变成一个基础，所以也很自然地可以和WPF、WCF，甚至ASP.NET整合（用WF来控制ASP.NET页面流程），都让Workflow的观念自然而然地使用，而不像过去Workflow似乎是企业才会用到的玩意儿。

.NET Framework 3.0正式推出已经一年多了，不过，市面上看到的几乎都是炫酷的WPF书籍，虽然“表面”工夫很重要，但是很高兴靖灏前辈和智桦前辈带给我们一本中文的WF著作。虽然WF这个东西本质上不像WPF那么炫，但绝对是属于“精神”层面的心灵滋润，而我也相信，以他们两位平常在研讨会上说故事的能力，一定可让读者在看完这本书（《Windows Workflow Foundation新一代工作流开发实务》）之后，将这个软件开发必备的技能发挥得淋漓尽致。

王  森        
开发技术推广经理
台湾微软 开发工具与平台推广处

下载地址：http://files.cnblogs.com/bvbook/laobing.pdf

谢谢大家。

前面已经写了一些关于烙饼问题的简单分析，但因为那天太累有些意犹未尽，今天再充实一些内容那这个问题研究透。我想，通过这篇文章，我们就可以把这一类问题搞懂。再遇到优化问题，如果我们想不到别的办法，就可以采用搜索树算法来解决，至少我们不至于拿不出解决方案。前面我们已经知道，关于一摞烙饼的排序问题我们可以采用递归的方式来完成。其间我们要做的是尽量调整UpperBound和LowerBound，已减少运算次数。对于这种方法，在算法课中我们应该称之为：Tree Searching Strategy。即整个解空间为一棵搜索树，我们按照一定的策略遍历解空间，并寻找最优解。一旦找到比当前最优解更好的解，就用它替换当前最优解，并用它来进行“剪枝”操作来加速求解过程。

书中给出的解法就是采用深度优先的方式来遍历这棵搜索树，例如要排序[4,2,1,3]，最大反转次数不应该超过(4-1)*2=6次，所以搜索树的深度也不应大于6，搜索树如下图所示：

这里只列到第三层，其中被画斜线的方块由于和上层的某一节点的状态重复而无需再扩展下去（即便扩展也不可能比有相同状态的上层节点的代价少）。我们可以看到在右子树中的一个分支，只需要用3次反转即可完成，我们的目标是如何更为快速有效的找到这一分支。直观上我们可以看到：基本的搜索方法要先从左子树开始，所以要找到本例最佳的方案的代价是很高的（利用书中的算法需要查找292次）。

既然要遍历搜索树，就有广度优先和深度优先之分，可以分别用栈和队列来实现（当然也可以用递归的方法）。那么如何能更有效地解决问题呢？我们主要考虑一下几种方法：

（1）       爬山法

该方法是在深度优先的搜索过程中使用贪心方法确定搜索方向，它实际上是一种深度优先搜索策略。爬山法采用启发式侧读来排序节点的扩展顺序，其关键点就在于测度函数f(n)的定义。我们来看一下如何为上例定制代价函数f(n)，以快速找到右子树中最好的那个分支（很像贪心算法，呵呵）。

我们看到在[1,2,4,3]中，[1,2,3]已经相对有序，而[4]位与他们之间，要想另整体有序，需要4次反转；而[3,1,2,4]中，由于[4]已经就位，剩下的数变成了长度为3的子队列，而子队列中[1,2]有序，令其全体有序只需要2次反转。

所以我们的代价函数应该如下定义：

1 从当前状态的最后一个饼开始搜索，如果该饼在其应该在的位置（中间断开不算），则跳过；

2 自后向前的搜索过程中，如果碰到两个数不相邻的情况，就+1

这样我们就可以在本例中迅速找到最优分枝。因为在树的第一层

f(2,4,1,3)=3，f(1,2,4,3)=2，f(3,1,2,4)=1，所以我们选择[3,1,2,4]那一枝，而在[3,1,2,4]的下一层：

f(1,3,2,4)=2，f(2,1,3,4)=1，f(4,2,1,3)=2，所以我们又找到了最佳的路径。

上面方法看似不错，但是数字比较多的时候呢？我们来看书中给出的10个数的例子：

[3,2,1,6,5,4,9,8,7,0]，程序给出的最佳翻转序列为{ 4,8,6,8,4,9}（从0开始算起）

那么，对于搜索树的第一层，按照上面的算法我计算的结果如下：

f(2,3,1,6,5,4,9,8,7,0)=4

       f(1,2,3,6,5,4,9,8,7,0)=3

       f(6,1,2,3,5,4,9,8,7,0)=4

       f(5,6,1,2,3,4,9,8,7,0)=3

       f(4,5,6,1,2,3,9,8,7,0)=3

       f(9,4,5,6,1,2,3,8,7,0)=4

       f(8,9,4,5,6,1,2,3,7,0)=4

f(7,8,9,4,5,6,1,2,3,0)=3

f(0,7,8,9,4,5,6,1,2,3)=3

我们看到有4个分支的结果和最佳结果相同，也就是说，我们目前的代价函数还不够“一击致命”，但是这已经比书中的结果要好一些，起码我们能更快地找到最佳方案，这使得我们在此后的剪枝过程更加高效。

爬山法的伪代码如下：

1 构造由根组成的单元素栈S

2 IF Top(s)是目标节点 THEN 停止；

3 Pop(s);

4 S的子节点按照启发式测度，由小到大的顺序压入S

5 IF 栈空 Then 失败

Else 返回2

              如果有时间我会把爬山法解决的烙饼问题贴在后面。

（2）       Best-First搜索策略

最佳优先搜索策略结合了深度优先和广度优先二者的优点，它采取的策略是根据评价函数，在目前产生的所有节点中选择具有最小代价值的节点进行扩展。该策略具有全局优化的观念，而爬山法则只具有局部优化的能力。具体用小根堆来实现搜索树就可以了，这里不再赘述。

（3）       A*算法

如果我们把下棋比喻成解决问题，则爬山法和Best-First算法就是两个只能“看”未来一步棋的玩家。而A*算法则至少能够“看”到未来的两步棋。

我们知道，搜索树的每一个节点的代价f*(n)=g(n)+h*(n)。其中，g(n)为从根节点到节点n的代价，这个值我们是可求的；h*(n)则是从n节点到目标节点的代价，这个值我们是无法实际算出的，只能进行估计。我们可以用下一层节点代价的最小者来替代h*(n)，这也就是“看”了两步棋。可以证明，如果A*算法找到了一个解，那它一定是优化解。A*算法的描述如下：

1．  使用BestFirst搜索树

2．  按照上面所述对下层点n进行计算获得f*(n)的估计值f(n)，并取其最小者进行扩展。

3．  若找到目标节点，则算法停止，返回优化解

总结：归根到底，烙饼问题之所以难于在多项式时间内解决的关键就在于我们无法为搜索树中的每一条边设定一个合理的权值。在这里，每条边的权值都是1，因为从上一个状态节点到下一个状态节点之需要一次翻转。所以我们不能简单地把每个节点的代价定义为翻转次数，而应该根据其�