brute force approach

"Brute force approach"，这个短语你见过么？至少我是第一次见到这个英文短语，在完成SPOJ Problem Set 第一道题目1. Life, the Universe, and Everything的时候我见到了这个短语。开始感觉应该就是一种穷举比较的方法。呵呵，和昨天的blog一样，俺用了Google 的Definition，找到如下的一段解释：

---

It's a primitive programming style in which the programmer relies on the computer's processing power instead of using his own intelligence to simplify the problem, often ignoring problems of scale and applying naive methods suited to small problems directly to large ones. The term can also be used in reference to programming style: brute-force programs are written in a heavy-handed, tedious way, full of repetition and devoid of any elegance or useful abstraction.

The canonical example of a brute-force algorithm is associated with the "travelling salesman problem" (TSP), a classical NP-hard problem:

Suppose a person is in, say, Boston, and wishes to drive to N other cities. In what order should the cities be visited in order to minimise the distance travelled?

The brute-force method is to simply generate all possible routes and compare the distances; while guaranteed to work and simple to implement, this algorithm is clearly very stupid in that it considers even obviously absurd routes (like going from Boston to Houston via San Francisco and New York, in that order).

---

再看看Brute force的中文解释，金山词霸的解释是“暴力的”意思。再查询Definition的时候找到一个brute-force attack的解释：In security, an attack that requires trying all (or a large fraction of all) possible values until the right value is found.这个解释就想软件破解领域的一个术语：暴力破解。

暴力，对于一些特殊的应用是不得已的方案。但是很多时候我们在编写程序的时候却“偷懒”的使用了这种概念。比如在进行数据排序的时候，很多人使用的是编程语言直接提供的方法，有时候这些方法得到的效率是非常低下的。但是人，偷懒了，或者可以理解为采用了暴力的方法来解决这些问题。这里的暴力，我更多的理解成为一种不考虑问题精解的方法。正如上面那段英文解释第一段中说明的那样。brute-force programs are written in a heavy-handed, tedious way, full of repetition and devoid of any elegance or useful abstraction.

我认为“暴力”还有一个解释，那就是对整个问题的解空间进行穷举。这种方法在上个世纪中叶计算资源和能力非常稀缺的年代是很难实现，也是根本不允许的。作为一个非职业化的程序员，我们应该尽可能的减少问题的解空间，比如采用上一片blog中提到的启发式方法来进行。特别是在我们计算机应用专业里面，应用一个算法的时候，或者实现我们的一种新的算法的时候，我们往往不去考虑程序执行的时空复杂度，有些朋友的观点是程序能够运行起来，而且得到结果那就是万幸了，至于程序运行的速度和所占内存空间根本都不用考虑。

有一句古语，不积圭步，无以至千里。我们应该尽可能的提高个人的编程修养，多多阅读一些相关的资料和多进行一些相关的实践。这样才会出现编程能力的迭代式的提高。看着《CODE COMPLETE》我现在越来越觉得编程和做研究在很多方面是相通的。既然我们在做研究的时候那么严格要求自己的研究方法和正确性，研究成果的高度可重复性，以及论文的原创性；我们为什么不再给自己完成编程工作的时候加上一个编程严格规范的限制呢。这种限制，我认为是一种对于计算机专业人员的归属的体现。作为计算机专业的不管是本科、硕士，还是博士，高水平的编程能力是必须的。这一点，我现在已经有了较为清楚的认识。

行，胜于言！在彻底解决了Komodo中文问题的基础上，那就好好的练习吧。期待自己的编程能力得到提高！