算法的真正定义

什么是算法？
如果您想进入这个世界的话，您就不应该不知道，这个美丽的世界，她究竟是什么？
什么是算法？是呀，这是个问题。它的意义，可比于那个“To be，or not to be”，如果我们也如哈姆雷特般的徘徊起来：）……

我们不妨先回顾上次的一个问题，SAT问题。
当然，考虑问题总应从最简单处入手啦。看下面简单的例子，10个逻辑变量的：

C0 : -x0 V -x3 V x5

C1 : -x1 V -x6 V x7

C2 : -x5 V x8 V x9

这个子句集合可以都为真吗？呵呵，要解决它，我们是有办法的，要不就这样，10个逻辑变量，我们给出一组赋值：

TRUE，TRUE，TRUE，TRUE，TRUE，TRUE，TRUE，TRUE，TRUE，TRUE

去测试C0、C1和C2，如果子句都是取值为真，则这组赋值满足要求，返回它，结束。否则，我们试下一组：

TRUE，TRUE，TRUE，TRUE，TRUE，TRUE，TRUE，TRUE，TRUE，FALSE

……

如果搜索所有的赋值后，没有使这个集合的所有子句都为真的赋值，则输出此集合不可满足。

这是我们的一个思路。当然，我们可以写出一个“描述精确步骤的字符文本”，它表示了我们一步一步解决问题的办法。我们加以归纳，这就是算法的定义，即一步一步求解问题的方法，它有如下的特征：

（1）必为一有限文本的表示；

（2）每一步必有可能在有限的时间内机械的完成。

这个描述，固然很好理解，但作为基本的概念，算法可有形式化的定义？我们知道，如果是有穷自动机，它的算法是有形式化定义的，而一般意义的算法，我还未见到。自己也想应如何定义，却不知所终。

但对于算法之内涵，还是有可讨论的地方。我先来问您：

算法可否可以无穷执行？

“哈哈，我写了一个‘算法’，计算机执行到世界末日也不会结束……”，这是个算法吗？是吗？不是吗？呵呵，您是如何想的，不妨说说看。我的看法，当然是；算法当然可以无穷执行。（这里我们讲演化计算的康老师有个例子：你写个钟表的算法，它永不停息的走下去……不也是个算法吗？）

那么，我来问第二个问题：

是什么使某些问题很难解决，而又使另一些问题很容易解决？

举例来说，上次的例子，求自然数前n项和，比如n=1000，这个问题计算机可在一瞬间计算出来，而1000个变量的SAT问题，计算机只怕有些难以计算了。为什么？是什么因素起了决定作用，使的我们的算法如此的不同？我们可充分的理解了它的实质吗？毫无疑问目前还没有，几十年来的研究成果就是，我们有了一个标准，把问题划分为几类，我们知道什么是难题。仅知道它是难题。

问题远不止这些。但我们不会畏惧未知！

事实上，就是因为这些困难的存在，就是因为有无限的荒原，有戈壁，有沙滩，我们的这个世界才有了她独特的魅力……我相信无数的人希望在这里开拓出一片绿色的原野，希望在这里劳作，冒险，品尝争娶拥有或失败的欢乐！

呵呵，您准备好了吗？是否有充分的信心，随我进入这个世界？如果是的话，我再给您说说我眼中的这个世界，她的独特，优美，摇曳多姿……

这个世界，与她的兄弟姐妹有着千丝万缕的关系。

首先，算法的世界，因数学模型的不同会有大不同。
我们来看这个例子，不要说它简单哦：）：

e.g.1 求方程的根： ax+b=0 (a!=0)

问问自己，您会如何解决？使用计算机，我想您肯定会这样想：
存在x1，使得 a*x1+b<0, 存在x2,使得 a*x2+b>0,那么，在区间[x1,x2]内使用折半法迭代搜索！
如果您这样解决，我一点都不奇怪。事实上，我的第一反应，也是这样的解法。这个算法的数学背景是，误差控制内的数值方法。
当然，非常优秀的算法。也适合本题。

但是，如果您把它留给任何一个学过简易方程的小学生的话，我想他（她）的解法毫无疑问是这样的：
ax+b=0
ax=-b
x=-b/a (a!=0)
呵呵，怎么样？您或许会说，“哦……是呀，如果手算（换句话，人算：），我当然也这样解决。可是，用计算机呀……”。
用计算机就不可以了吗？
您注意到，人解决问题的方式是逻辑思维，不是按步长搜索或迭代的。如果我们一开始考虑的数学模型是另外一个样子的话，我们的算法将是完全不一样的：

定义：
个体域： 实数集R
函词： add(a,b): a+b
mul(a,b): a*b

谓词： Equal(a,b): a==b
规则： Any x,y in R, Equal(add(x,y),0)->Equal(x,add(0,-y))
Any x,y,z in R, Equal(mul(x,y),z) and ┐(Equal(y,0))->Equal(x,mul(z,1/y))

规则集中给出的是最重要的两个，其他的就没有加进来；但已经可以讨论问题了。我们依据这个逻辑系统，使用类似与机器证明的算法，完全可以推出方程的解。

您认为怎么样？或许，对于方程您还不在意数学模型的问题，但是，做一个大型的专家系统，您必须来细致的考虑这个问题了。

后注：这个问题我的本意不是让您定义一个函数f，参数为a，b，返回 -b/a ：）。呵呵，或许例子过于简单了。可我需要您着重体现出“计算”的过程。

其次，算法的世界因计算机体系结构的不同而大不同。

我们仍然考虑上次的一个简单的问题，求和：）。现在为：

e.g.2 有n个数据，求和

您如何来解决？呵呵，是不是我问的很傻？或者，您怪我把您看的太傻？哈哈，没有没有，如果您问多数的程序员（包括在校学生的准程序员），多半人会说：

一个循环： sum=0;
For i=0 To n-1 Do
sum+=a[i];
其中a[]存放数据。如果他又是个细心的人，他会考虑sum会不会数据溢出，这样他或许会考虑一个数据结构来存放结果。

没有问题的算法，一定程度上满足了题目的要求。但是，您的算法是基于单处理机的！这个工作，如果您的公司里有一个网络机群，您或许不应该使用这个串行算法了，您需要一个并行算法。那么，您需要把问题分割，并考虑通信的开销。算法就会完全改变了！

最后，一个浅显的特点，算法的世界因问题的规模不同而大不同。
一开始就分析的ＳＡＴ问题是个很好的例子。１０个逻辑变量我们或许可以穷举，但穷举绝对不是本问题的可采取的算法！否则它的时间开销将是按指数级增长的！

兼于我做了个这个问题的项目，演化计算来解决的，我后面还将更全面的分析这个问题。包括爬山法，Ａ算法，Ａ*算法，当然还有最后的解决方案，演化计算。

总而言之，算法世界可谓多姿又多采。因为我对于她的热爱，所以我自愿来做向导，虽然这个向导不好，但仍然盼望您不要因此拒绝风景的美丽哦！

下次将讨论数学，算法的渊源。

本帖的题目：

国王的城堡（percy lee提出：）：
有个国王，他的领土内有n个城堡。国王疑心很重，他认为敌人有可能偷袭并占领任何一个城堡。因此他给他的将军和财政大臣发了一道旨意，命令他们共同完成一项工程，在这n个城堡间修建大道，以保证任何k个城堡被敌军占领后，我方的城堡仍然可以通过大道相互支持。将军毫无疑问要不惜一切代价完成使命，而财政大臣的任务就是使所有的花费尽可能低。这项工程应该如何完成？（假设花费只和道路的长度有关）