ITnews 版 (精华区)

发信人: petrel (紫燕＊自在飞花轻似梦*燕燕于飞), 信区: ITnews
标  题: 有趣的算法世界---什么是算法    
发信站: 哈工大紫丁香 (Fri Aug  8 10:01:07 2003)

有趣的算法世界---什么是算法    PercyLee（原作） 
  
关键字     算法 
  


    

     什么是算法？
     如果您想进入这个世界的话，您就不应该不知道，这个美丽的世界，她究竟是什么？

     什么是算法？是呀，这是个问题。它的意义，可比于那个“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,mu
l(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个城堡被敌军占领后，我方的城堡仍然可以通过大道
相互支持。将军毫无疑问要不惜一切代价完成使命，而财政大臣的任务就是使所有的花费
尽可能低。这项工程应该如何完成？（假设花费只和道路的长度有关）

 


--

                    ·  一沙一世界，一花一天堂  ＊





※ 来源:．哈工大紫丁香 bbs.hit.edu.cn [FROM: 202.118.239.116]