姓名：车文扬 学号：16020199006  转载自：https://www.cnblogs.com/sddai/p/5644011.html

【嵌牛导读】：启发式算法的详解

【嵌牛鼻子】：启发式算法

【嵌牛提问】：启发式算法有什么作用？

【嵌牛正文】：

（一）物理符号系统 

1 定性结构定律（Laws of Qualitative Structure） 

All sciences characterize the essential nature of the systems they study. These characterizations are invariably qualitative in nature, for they set the terms within which more detailed knowledge can be developed. Their essence can often be captured in very short, very general statements. One might judge these general laws, due to their limited specificity, as making relatively little contribution to the sum of a science, were it not for the historical evidence that shows them to be results of the greatest importance. 

在研究某个系统的时侯，我们可以建立一个简单而容易理解的模型来定性地描述这个系统的性质。就像生物学中的细胞学说，一切生物都是由细胞组成的，但任何一种生物的细胞都有极其复杂的种类、形态和功能。但我们可以建立一个标准的细胞模型：细胞由细胞核、细胞质和细胞膜组成，细胞核中有遗传物质，细胞质中有各种行使不同功能的细胞器，细胞膜包在细胞质外面，负责细胞核环境的物质交换和信息交流。在此基础上研究各种细胞的形态结构和功能就都显得比较简单了。同样的道理，“智能”是个相当抽象的、让人有点无从下手的研究对象，物理符号系统就是一个用以描述智能的，（相对来说）简单而容易理解的模型。 

2 物理符号系统的定义 

物理符号系统是“物理的”，就是说它是遵循物理定律的，而且能用工程技术手段来实现，比如说你的计算机；它是一种“符号”系统，但不局限于人类的符号系统。 

物理符号系统包括符号(symbols)、表达式(expressions)和过程(Processes)。符号是一种物理模式，是实体。符号组合起来就成了表达式，这里的组合方式可以是多种多样的。系统在任一时刻都包含着这样一些表达式。过程可以作 用于表达式来对表达式进行创造(creation)、修正(modification)、再生(reproduction)或破坏 (destruction)。然而，物理符号系统内的表达式本身并不能描述一切对象(Such a system exists in a world of objects wider than just these symbolic expressions themselves.不知道可不可以这样理解)。 

两个核心概念：指称(designation)和解释(interpretation) 

Designation. An expression designates an object if, given the expression, the system can either affect the object itself or behave in ways dependent on the object. 

Interpretation. The system can interpret an expression if the expression designates a process and if, given the expression, the system can carry out the process. 

Interpretation implies a special form of dependent action: given an expression the system can perform the indicated process, which is to say, it can evoke and execute its own processes from expressions that designate them. 

个人理解：指称表示的是一种表达式与对象的对应关系，就像指针一样。解释（或者译成翻译、说明）表示的是一种表达式与过程的对应关系，系统可以通过一些表达式来执行相应的过程。 

从定义来看，物理符号系统与一切通用计算机极为相似，它实际上也确实不是什么新的东西。很多已知的系统都具有这样的特征，其中最明显的有两个：计算机和人脑。 

3 物理符号系统假设：物理符号系统是智能活动的充要条件 

The Physical Symbol System Hypothesis：A physical symbol system has the necessary and sufficient means for general intelligent action. 

By "necessary" we mean that any system that exhibits general intelligence will prove upon analysis to be a physical symbol system. By "sufficient" we mean that any physical symbol system of sufficient size can be organized further to exhibit general intelligence. By "general intelligent action" we wish to indicate the same scope of intelligence as we see in human action: that in any real situation behavior appropriate to the ends of the system and adaptive to the demands of the environment can occur, within some limits of speed and complexity. 

其中，“必要性”的证明是认知科学的任务，也就是研究人类（或动物）的认知行为，然后用物理符号系统来解释这些认知行为。“充分性”是人工智能的任务，也就是构造一些物理符号系统，看它们能否产生智能。 

西蒙和纽厄尔把信息加工理论引入心理学，成为信息加工心理学，也就是认知科学。人工智能的研究离不开认知科学研究中提出的各种假设。 

刚开始，人们构造一些简单的程序来让计算机完成一些简单的、精心设计的任务，后来觉得不过瘾，就把研究工作扩展到了建立系统，如自然语言理解系统、模式识别系统、设计系统等。但是—— 

It would be surprising and unappealing if it turned out that the AI programs performing these diverse tasks had nothing in common beyond their being instances of physical symbol systems. Hence, there has been great interest in searching for mechanisms possessed of generality, and for common components among programs performing a variety of tasks. This search carries the theory beyond the initial symbol system hypothesis to a more complete characterization of the particular kinds of symbol systems that are effective in artificial intelligence. 

完成这些形形色色的任务的程序之间有没有什么共性？找到了这些共性，就意味着对智能有了更深层的理解。 

In the second section of this paper, we will discuss one example of a hypothesis at this second level specificity: the heuristic search hypothesis（启发式搜索假设）. 

（二）启发式搜索 

系统的智能活动是通过问题解决来体现的，系统是通过启发式搜索来解题的。启发式搜索假设是AI的第二个定性结构定律（第一个是物理符号系统）。 

1 启发式搜索假设 

Heuristic Search Hypothesis. The solutions to problems are represented as symbol structures. A physical symbol system exercises its intelligence in problem solving by search--that is, by generating and progressively modifying symbol structures until it produces a solution structure. 

问题的解也是符号结构。物理符号系统解决问题的过程就是产生某种符号结构，再一步一步的修正它，直到它与问题的解的结构相一致。就像解方程AX+B=CX+D一样，移项得（A-C）X=D-B，再消去系数（A-C），得到X=（D-B）/（A-C）。这就是逐步修正方程的结构，最终得到符合X=E的形式的解的过程。 

假如有无限的时间和存储空间还后无限的能量供应，那么系统总可以通过穷举的方式，遍历问题空间中的所有路径来找到问题的解——这就是传说中的蛮力搜索。但实际应用中这显然是不可能的。实际应用中必须在有限的步骤中，有限的时间内找到答案，因此就要用启发式搜索策略。 

A condition, then, for the appearance of intelligence is that the distribution of solutions be not entirely random, that the space of symbol structures exhibit at least some degree of order and pattern. A second condition is that pattern in the space of symbol structures be more or less detectible. A third condition is that the generator of potential solutions be able to behave differentially, depending on what pattern it detected. There must be information in the problem space, and the symbol system must be capable of extracting and using it. 

符号系统处于完全混沌的状态时，是不可能表现出智能的。符号系统的智能体现在它能够从问题空间中抽取信息，并运用这些信息指导搜索，从而避开错误的方向，避免迂回曲折的分叉而高效的解决问题。所以，问题空间中必须包含信息，或者说，包含某种程度的秩序和结构。 

实际中需要解决的问题不像解一元一次方程那样只有一条路对应一个固定的解，而是在每一步都有多种选择，对应着多个结局，形成一棵搜索树。 

The fact of limited resources allows us, for most purposes, to view a symbol system as though it were a serial, one-process-at-a-time device. If it can accomplish only a small amount of processing in any short time interval, then we might as well regard it as doing things one at a time. Thus "limited resource symbol system" and "serial symbol system" are practically synonymous. The problem of allocating a scarce resource from moment to moment can usually be treated, if the moment is short enough, as a problem of scheduling a serial machine. 

这里好像是说由于资源有限，在实际应用中是按照线性过程在进行搜索的，是串行的，一次只能沿着搜索树的一个分支走。（不过，有没有“多线程”的并行搜索呢？） 

In serial heuristic search, the basic question always is: what shall be done next? In tree search, that question, in turn, has two components: (1) from what node in the tree shall we search next, and (2) what direction shall we take from that node? Information helpful in answering the first question may be interpreted as measuring the relative distance of different nodes from the goal. Best-first search calls for searching next from the node that appears closest to the goal. Information helpful in answering the second question--in what direction to search--is often obtained, as in the algebra example, by detecting specific differences between the current nodal structure and the goal structure described by the test of a solution, and selecting actions that are relevant to reducing these particular kinds of differences. This is the technique known as means-ends analysis, which plays a central role in the structure of the General Problem Solver. 

下一步搜索从树的那一个节点开始？这就要进行不同节点与目标的相对距离测定。佳者优先策略要求从那个看起来离目标最近的节点开始下一步搜索。从该节点起应取什么方向？这就需要测出当前节点的结构与目标结构之间的差异，并向着最能有效消除差异的方向前进。这就使传说中的“手段—目的分析法”，在通用问题求解程序（GPS）中起主导作用。 

具体操作中则需要一个估价函数f(n) = g(n) + h(n) 其中f(n) 是节点n的估价函数，g(n)实在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。如果说详细点，g(n)代表了搜索的广度的优先趋势。但是当h(n) >> g(n)时，可以省略g(n)，而提高效率。（摘自百度百科，不过说实话这一段我没看懂，欢迎高手指点） 

Search—successive generation of potentional solution structures--is a fundamental aspect of a symbol system's exercise of intelligence in problem solving but that amount of search is not a measure of the amount of intelligence being exhibited. What makes a problem a problem is not that a large amount of search is required for its solution, but that a large amount would be required if a requisite level of intelligence were not applied. When the symbolic system that is endeavoring to solve a problem knows enough about what to do, it simply proceeds directly towards its goal; but whenever its knowledge becomes inadequate, when it enters terra incognita, it is faced with the threat of going through large amounts of search before it finds its way again. 

并不是搜索越多就意味着智能越高，正相反，智能高的表现恰恰是不用经过大量搜索也能解决问题。 

启发式搜索会造成这样的结果：找到的解虽然是令人满意的，却不是最优的；或者说，虽不是最优的却能令人满意。实际上在认知心理学研究中也表明，动物在进行决策的时候采取的也是启发式策略，尤其是在资源（时间、食物等）不充足的情况下。这样做出的决策往往不是最优的，不过至少是有效的。这个就是西蒙“有限理性”的理论来源，使得西蒙后来获得了诺贝尔经济学奖。 

2 几个启发式搜索的实例 

这部分参考《人工科学——复杂性面面观》 司马贺著 武夷山译 

http://www.douban.com/subject/1195595/ 

例一 通用解题者（General Problem Solver，GPS）P113-114 

“……在输入或感官一侧，GPS必须能表现想望状况或想望物（就是上面说的目标结构），表现目前状况，它也必须能表现想望状况与目前状况的差别。 在传出侧，GPS必须能表现改变实物或状况的行动。为了有目的的行动，GPS必须能不时地选择这样一些特定的行动，它们有可能消除系统探测到的目前状态与 想望状态之间的差别。在GPS这部机器中，这种选择是通过一张关联表实现的。该表将每种可探测到的差别与对减小那一差别有作用的行动联系起来。GPS的这 些联系（表现为产生过程）将传入状况与传出状况挂上了钩。由于通常需要一系列行动才能实现某一目标，由于某些努力也许是无效的，GPS也必须有探测自己的 进度（现实状态与想望状态间差别的变化）和试行新路子的手段。” 

可以看出GPS解决的是具有“良结构”（well structured）的问题。也就是说，等待解决的问题的当前状态、目标状态以及搜索空间中的路径都很清楚。不能满足此条件的问题称为结构不良问题（poorly structured problem） 

例二 “理解”（understand）P88 

这是一个可以解决结构不良问题的程序。 

“有一个名叫“理解”的程序，它模拟人们对饮茶仪式这种问题建立内部表象（即进行理解）的过程。“理解”分两阶段进行工作：先对问题指令的句子进行语法分析，然后根据经过语法分析的句子摘取出的信息构造一个表象。 

……分析的任务就是根据线性词串推断出隐含着的词组和从句的层级结构。“理解”程序是用相当正统的方式（类似于现有的其他语法分析程序）完成这一 步骤的。第二阶段（构造）更为有趣。这里。对经过语法分析的句子进行考察，以期发现提到了哪些宾词和宾词集，提到了宾词的那些性质，这些性质之间的关系是 什么，哪些谓词与关系描述了状态，哪些描述了步骤，目标状态是什么。“理解”接着构造一个表现状态的规则，产生出步骤符合规定（通过将一个状态转变为另一 状态）的程序。” 

这个看上去似乎挺牛的，不过实际上它的功能非常有限。在西蒙的《思想模型》（Models of Thought）一书的7.1章到7.3章有关于“理解”程序的详细描述。 

例三 培根（BACON）P99 

这是个具有发现能力的程序。 

“BACON程序的目的是发现大量数据中的不变量。给定各行星至太阳的距离与它们的轨道周期的数据，该程序发现，对于所有的行星，轨道周期的立方 与行星至太阳的距离的平方之比都是一样的（开普勒第三定律）。根据电流随电路中电阻线长度而变化的数据，它推出了欧姆定律。同理，它发现了气体定律、伽利 略自由落体定律和许多其他定律。 

为了解释发现的不变量，BACON就引入新概念。给定数据表明，当两个物体互相加速时，两者加速度的比值总是相同的。BACON程序由此发明了质量的概念，并给每一物体一个质量。同理，它发明了折射率，以及比热和化学价的概念。 

……BACON的基本构造没有多少新东西。给定两组数据，如果它发现一组数据随另一组数据单调变化，就检验一下它们的比值（或乘积）是否不变。如 果成功了，它就发现了数值之间的定律关系；如果失败了，它也定义了一个新的变量，可将此变量加到其他变量上去，再重复这一过程。该系统的行为了不起的地方 是，通过这些步骤发现上述种种定律并不需要大量的搜索。为找到一个不变量，很少需要考察原变量的十几个以上的函数。” 

科学家要失业了吗？不会的。BACON以及后来出现的一大堆发现程序虽然能发现一些定律，但并不能解释其中的内涵。我上小学的时候就知道E=mc2，可是到现在还是不懂狭义相对论。 

这些发现程序在化学学科中做了一些贡献，但主要被用于深化对人类发现过程的认识。“例如，人们将BACON程序的模拟结果与物理学和化学的发现的 历史事例进行了比较，还在实验室中庸一些受试者进行了并行实验，看看他们凭借BACON程序努力做出的发现和基于科学史中记载的资料努力做出发现的情形有 什么差异。” 

总结一下 

AI的两个定性结构定律： 

1 智能存在于物理符号系统中； 

2 符号系统是通过生成潜在可能的解，并对其进行检验，也就是通过搜索的方式来解题的。 

符号系统是许多模式和过程的集合体，过程能够产生、破坏或修正模式。模式能指称对象、过程或其他模式，当它们指称过程的时候，它们就能得到解释，完成被指称的过程。在我们所了解的符号系统中有两类意义最为重大，就是人类和计算机。 

符号系统的智能体现在它能够从问题空间中抽取信息，并通过搜索来解决问题。启发式搜索就是一种这样的搜索策略，通过估价函数来决定下一步搜索的起始点和方向，以有效率的解决问题。 

通过认知心理学对人类及动物认知过程的研究，提出了很多关于智能的假设。以这些假设为依据，人们开发了一堆各种各样的智能程序，能完成很多看起来 很复杂的任务，比如语义理解，定律发现等。但是每一种程序都有它的局限性。相信随着认知科学研究的不断深入，会有更多更牛的程序诞生