编程沙龙（08）

IT商界

PALADIN

　　算法设计的策略

　　上个月我们讲了递归技术。由于递归技术是算法设计的基本功之一，所以初学的朋友们一定要用些功夫来熟练掌握递归技术。如果你对递归还有什么不太了解的地方，可以参考上期有奖答题的源代码。本期我们将来讨论一下算法设计究竟有哪些可以总结出来的策略。

　　解决上期的8个棋子的问题，用到的是回溯的思想，也就是系统地搜索问题的解集。为了实现系统的搜索，就要对解集进行有效的组织，而典型的组织方式就是“图”和“树”。就拿上期的题目来说，考虑逐行放置棋子在棋盘上，其实就是用“树”的概念来放置8个棋子在棋盘上所有的可能情况，由此我们才确定可以利用深度遍历树的方法来解题。

　　除了上面说到的回溯的思想，我们还常常使用分治策略。分治策略顾名思义就是将一个复杂的问题分解成若干小问题，然后分别解决这些小问题，而这些小问题的解答组合起来就是原问题的解。通常这些小问题之间以及小问题和原问题之间都有着很大的相似性，所以分治策略总是和递归紧密相连。如二分查找、快速排序、矩阵乘法以及平面上最接近点对的确定等问题都是分治策略的应用。

　　如果说回溯思想是屡试不爽的法宝，那贪心策略则可能是最简单并往往是最有效的算法了。贪心策略主要用于解决最优化的问题。举个最简单的例子，如果用1分、2分、5分和1角的若干个硬币凑出0.87元钱，而又保证4种币都至少用1个且使用的硬币个数最少。我想小学三年级的学生不用计算机也能知道该如何来凑。

　　最复杂、最难懂的策略要算是动态规划了。很多资料上显示动态规划能够弥补贪心策略和分治策略的不足，是相当有用的算法设计思想。在笔者看来，动态规划和分治策略在很多方面相似，只是分治策略适合于分解的子问题，能够相对独立。如果分解的子问题不能相对独立，则可以使用动态规划。而动态规划比贪心策略优越的地方是贪心策略是一种不可更改的决策，而动态规划则要判断每个最优决策集中是否包含一个最优子集并以此互相影响。动态规划常见于图像压缩、最短路径等问题的解决方案中。

　　当然用这么简单的三言两语想要表述上面的四种程序设计策略是远远不够的。老实说，在解决具体问题时，我们开始时无法分清究竟是该用哪种策略，而事实却是常常要用到上面的多种策略，所以这也只是给大家一个模糊的印象。(PALADIN)

　　我们还是在应用中来理解这些高深策略的真正意义吧。

　　本期有奖问答的题目是：

　　对于任意两个字符串s1和s2(字符串中字符只限于26个小写的英文字母)的最长公共子序列lcs(s1,s2)是s1和s2中都出现的最长子序列。例如，tie是striped和tiger的最长公共子序列。

　　要求写一个程序，用户输入s1和s2，计算并显示出它们的最长公共子序列lcs(s1,s2)。

　　做这道题，读者朋友可以用你最擅长的语言和编程工具来完成。答题方式为：把你的答案发送到software@cpcw.com，邮件主题写上“算法演义答题”。我们会从中选取答题最好的参赛者，并发送精美奖品。