蛮力法

现在着手讨论算法设计技术。接下来的7章中，每一章都专注于一种特定的算法设计策略。本章的主题是蛮力法——一种最简单的设计策略。人们是这样描述它的：

蛮力法是一种简单直接地解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。

“力”是指计算机的计算能“力”，我们常用“直接做吧！”来描述蛮力法的策略。

蛮力法常常用于一些非常基本，但又十分重要的算法，比如计算n个数字的和，求一个列表的最大元素，等等。蛮力法也用于解决小规模的问题实例。

小结

• 蛮力法是一种简单直接地解决问题的方法，通常直接基于问题的描述和所涉及的概念定义。
• 蛮力法的主要优点是它广泛的适用性和简单性；它的主要缺点是不多数蛮力算法的效率都不高。
• 对于应用蛮力法得到的额第一个算法，可以通过适度的努力来提升它的性能。
• 下列这些著名的算法可以看作是蛮力法的例子：
  • 基于定义的矩阵乘法算法
  • 选择排序
  • 顺序查找
  • 简单的字符串匹配算法
• 穷举查找是解组合问题的一种蛮力方法。它要求生成问题的每一个组合对象，选出其中满足该问题约束的对象，然后找出一个期望的对象。
• 旅行商问题，背包问题和分配问题是典型的能够用穷举查找算法求解的问题，至少在理论上是这样的。
• 除了相关问题的一些规模非常小的实例，穷举查找法几乎是不实用的。