警告: 以下内容包含机器翻译的部分, 故可能并不正确.
人工智能是通过计算的思想和方法研究智能的学科. 不幸的是, 目前对智能的定义似乎是不可能的, 因为智能看起来是许多信息处理和信息表示能力的融合.
当然, 心理学, 哲学, 语言学和相关学科提供了研究智能的各种视角和方法. 然而, 在这些领域中提出的理论大多过于不完整且表述过于模糊, 无法用计算术语实现. 尽管从传统研究中可以获得有价值的思想, 关系和约束——毕竟, 这些都是令人印象深刻的存在证明, 证明了智能确实是可能的——但我们仍需要更多东西.
人工智能提供了一个新的视角和新的方法论. 其核心目标是使计算机智能化, 既为了使它们更有用, 也为了理解使智能成为可能的原则. 智能计算机将非常有用, 这一点显而易见. 更深刻的观点是, 人工智能旨在使用计算的思想和方法来理解智能, 从而为理论形成提供一个根本性的新基础. 大多数从事人工智能工作的人相信, 这些理论将适用于任何智能信息处理器, 无论是生物的还是固态的.
还有一些值得关注的副作用. 任何成功模拟智能哪怕一小部分的程序本质上都将是庞大且复杂的. 因此, 人工智能不断面临计算机科学技术的限制. 所遇到的问题足够困难且有趣, 足以诱使人工智能研究者热情地投入工作. 因此, 从人工智能到计算机科学有着稳定的思想流动, 而且这种流动没有减弱的迹象.
这个人工智能系列的目的是为许多领域的人, 包括专业人士和学生, 提供及时详细的信息, 了解世界各地研究中心前沿正在发生的事情.
人工智能已经成熟. 稳定的科学进步带来了知识上的可信度. 在商业方面, 20世纪70年代出现了一些应用, 而在80年代, 专家系统技术成为解决信息处理问题的公认因素. 部分由微电子革命推动, 这些趋势导致了该领域的快速增长. 与80年代的爆炸性增长相比, 90年代的趋势似乎是人工智能技术向主流计算的持续且静默的传播.
这种增长的一个结果是对人工智能研究和应用感兴趣的人数大幅增加. 不幸的是, 人工智能专业知识的传播并未跟上步伐. 人工智能是一门实验性学科. 人工智能研究无一例外地需要编程. 将人工智能作为系统的一部分来执行某些大型任务, 要么需要理解体现人工智能技术的子系统的优势和劣势, 要么需要自己动手
以满足约束条件. 尽管成功的人工智能编程所需的技能大多与其他类型的编程相同, 但所涉及的技术通常不熟悉. 以前, 这些技术是通过师徒制传授的, 但该领域的爆炸性增长导致这一系统崩溃. 随着进步使前沿变得更加遥远, 更快地掌握基础知识变得至关重要. 本书旨在提供这方面的帮助.
本书的目标是教读者如何设计和构建计算机问题求解器. 虽然已经有几本描述Lisp和AI编程的书籍, 但本书在几个方面是独特的:
工业级AI系统所需的工程问题. 我们呈现的程序有一个整体复杂度梯度. 早期系统的编写是为了让只有Common Lisp课堂经验的读者容易理解. 后期系统展示了
工业级AI系统中常用的编程技术, 在这些系统中, 效率与优雅同样重要.
本书设计面向两类读者. 首先, 它被设计为研究生 (或高级本科生) AI编程课程的教科书. 这些材料可以在一个学期内涵盖, 通常能让新研究生在完成论文所需的技能方面获得先机 (或对本科生而言, 提供参与研究, 暑期工作和荣誉论文所需的技能). 其次, 它被设计成对自学和工业培训有用, 适合那些有其他背景但希望掌握AI技术的人. 为此, 我们包含了完整, 可运行的程序以简化实验. 这些程序 (及其派生版本) 已经在西北大学, 伊利诺伊大学, 牛津大学, 施乐公司, Bolt, Beranek和Newman公司, 以及许多其他大学, 公司和政府机构的研究项目中使用.
鉴于C语言 (现在是 C++) 在主流计算和一些应用人工智能领域的热潮, 为什么要使用 Lisp 呢? 显然, 原则上可以用C++编写本书中的每个程序. 我们的目标是教学性的: 我们选择Lisp是因为它是最佳的被广泛接受的语言, 可以轻松传达这些概念. Lisp将过程作为一等公民对待, 提供自动存储管理, 并具有简化的语法, 这些特性使程序能够轻松编写和分析其他程序, 大大简化了我们的系统并最小化了您——读者的认知负担. 在C或C++中开发这些功能会使已经很长的书变得更加臃肿.
逻辑编程爱好者可能会争辩说Lisp太低级
, 而像Prolog这样的语言会更合适. 我们相信逻辑编程的目标——包括提供具有扎实声明性语义的强大推理机制——是极其重要的. 然而, 我们不认为今天的逻辑编程语言必然是开发未来逻辑编程系统的最佳起点. 通过对推理系统设计做出更少的先验承诺, Common Lisp使我们能够更轻松地构建各种不同的系统.
另一种选择可能是众多商业化的知识工程工具包或专家系统外壳之一. 这类系统由于以下三个原因而不适合我们的目的:
打开引擎盖查看引擎的构建方式来获得.
最后,为什么使用Common Lisp而不是更简单的Lisp方言, 例如Scheme? Common Lisp被称为Lisp社区中的PL/1: 庞大而笨重, 由于它提供的大量库而难以实现. 但正是这些大量的库使它在AI工作中变得如此流行. 任何还记得Lisp程序员面对几个重叠且不兼容的结构设施, 字符串操作工具和打印例程库的日子的人, 都会感激标准化的库. 因为我们依赖Common Lisp的功能, 我们的系统比其他情况下要短小且简单.
我们理解那些由于资源有限而必须使用Scheme或部分Common Lisp实现的读者. 对于这样的读者, 有两种选择: 手动将程序翻译成你选择的方言, 或编写一个兼容性包, 填补你希望运行的程序所使用但在你的实现中缺失的Common Lisp部分. 我们自己在不同时期也使用过这两种策略, 以在小型微型计算机 (包括基于8086的笔记本电脑) 上运行某些程序. 然而,这确实需要额外的耐心和决心.
是什么使AI程序与其他程序不同? 两个关键差异是知识的显式表示和增强的模块化. 使用知识显式表示的能力或许是AI程序最好的标志. 传统程序, 当然, 在其过程和数据结构中嵌入了知识. 但AI程序包含可以被声明式解释的结构, 也就是说, 独立于任何单一用途, 既可被程序解释, 也可被程序员解释. 程序, 而非程序员, 可以基于特定上下文中的这些知识决定做什么. 这通常使得改进AI程序的过程更像是告诉它一些事情, 而非编程.
AI程序中增强的模块化来自于将过程分解为小型, 细粒度的部分. 这种极端分解使一些人声称AI程序必然由规则组成, 但正如我们将看到的, 情况并非必须如此. 显式知识表示通过提供更丰富的词汇表支持这种过程的细粒度划分, 使程序的不同部分能够相互通信. 这种增强的灵活性并非没有代价: 获取过程执行所需的信息需要比编程语言中常用的简单变量和绑定概念更复杂的引用机制. 这些机制通常涉及某种形式的模式匹配, 但并非总是如此. 程序各部分之间增强的模块化和显式通信增加了其自行决策的能力, 动态地, 而非强制程序员预先预测所有可能性.
问题求解器应该如何组织? 探索这个问题的一种方式是研究传统程序和AI程序的期望特性. 让我们以控制主要城市交通灯的程序为例. 人们可能会抱怨该程序的某些特定运行实例, 同时认同它总体上做得相当不错. 这个程序与AI程序有何不同?
我们假想的原型交通控制程序可能是用Fortran编写的, 经过了一二十年的发展, 由数十位可能从未谋面的人开发. 很可能没有一个人真正详细理解交通控制程序到底做了什么. (不幸的是, 某些AI程序也可能如此.) 它是用Fortran编写的这一事实本身并不重要. 重要的是它由大块的程序代码组成. 我们希望AI程序的构建方式不同, 这有多种原因.
在AI的早期, 人们常常希望能够找到一小组能够为理解智能本质提供基础的宏伟原则, 就像牛顿定律为理解力, 物质和运动的相互作用提供了基础一样. 最先被提出的原则之一是搜索. 为什么是搜索? 认知科学从人类智能是计算过程这一假设开始. 一个自然而然要问的问题是, 它是什么样的计算? 智能似乎与简单的算法, 如排序程序或会计系统完全不同. 此类算法能够非常出色地执行单一任务, 但无法处理下一步行动不明确的情况. 智能似乎需要尝试某事, 观察其表现如何, 然后尝试其他方法直到找到有效的方法的能力. 这就是搜索.
虽然如今很少有人认为搜索是智能背后的唯一关键理念, 但大多数人会同意搜索在构建AI程序中扮演着核心角色. 在此我们将研究如何以清晰且模块化的方式实现问题解决的经典模型——问题空间模型 [5].
从概念上说, CPS由两部分构成: 一个是用户用以提供问题空间的接口, 另一个则是搜索引擎. 显然, 我们需要操纵状态和行动的能力. 但是, 何种操作是我们所需要的呢?
以下是三种我们需要能够对于状态施行的操作.
目标检测的重要性是不言自明的. 状态同一性之所以重要, 是因为重新探索已经检视过的状态并不能算是搜索的进展. 显示状态的重要性在于即便CPS的结果只是由另外的程序使用, 这样的显示对于debug而言往往也是必要的.
针对行动的接口应该长什么样? 从概念上说, 存在四种不同的必要操作:
这些操作经常被合称为扩展(一个状态), 而一个后继状态皆已计算完毕的状态被称为是扩展了的.
搜索引擎本身需要做什么呢? 这种程序的设计对于读者而言应该是相当熟悉了的. 基本上来说, 存在一个队列, 其初始状态即是包含搜索的初始状态. 搜索过程按照以下步骤进行:
队列组织和更新的细节决定了搜索所遵循的策略. 一个无序的FIFO队列对应于广度优先搜索, 而一个无序的LIFO队列对应于深度优先搜索. 给定一个到达目标状态的剩余距离的启发式估计, 更为强大的搜索策略则是可能的. 将队列按照到达目标的最小预估(总)距离排序构成了最佳有限搜索. [注记: 最佳优先搜索 (best-first search), 指的是根据某种标准或者说函数, 总是优先扩展当前(估计)最佳的状态或者说路径, 一致代价搜索和A*搜索都是最佳优先搜索的实例.] beam search是最佳有限搜索的资源限制版本.
在CPS中我们看到, 一个非常简单但通用的搜索引擎确实可以作为问题求解器的有用组成部分. 搜索是否真的是构建问题求解器的核心理念, 因此可能是解释智能的关键计算理念? 对我们CPS示例的更深入分析可以阐明这个问题.
真正的问题是: 在开发问题求解器时, 有多大比例的工作需要投入到开发搜索引擎中? 如果搜索确实是关键理念, 那么作为问题求解器设计者, 我们的大部分精力应该投入到构建更好更智能的搜索程序上. 另一方面, 如果性能的真正决定因素在别处, 那么花在改进和调整搜索程序上的精力可能是浪费的. 如果我们将精力集中在问题解决的其他方面, 我们将获得更大的杠杆效应.
在波士顿地铁问题空间中, 搜索引擎占了代码的相当大部分. 然而, 这是由于领域的简单性质所致. 搜索一个有限的预先枚举的图是一种非常简单的问题. CPS代数问题空间提供了一个更好的测试案例. 在代数系统中, 我们最终创建了两个与搜索引擎复杂度大致相同的系统 (即模式匹配器和简化器). 当然, 解方程需要搜索, 但大部分工作都投入到定义代数的表示和知识上.
这是一个众所周知的AI教训: 知识减少了搜索的需求. 缓存特定问题的结果是一种加速方式, 但更有用的效率来自于对问题类别的仔细分析, 这些分析揭示了可用于指导搜索的结构. Bundy对吸引, 收集和隔离方法的识别是这种分析的一个极佳例子. 实际上, 该领域的语言已经转向谈论领域而非问题空间 (除非在考虑搜索问题时).
在许多情况下, 搜索是不可避免的. 但搜索应被视为当你没有足够的领域知识来更有效地找出答案时所做的事情. 搜索是指数级的, 在计算中不必要地嵌入指数级过程是糟糕的设计. 更快的计算机或大规模并行化无法驯服原始指数搜索的贪婪计算需求. 领域无关搜索策略的改进不会让你战胜指数级增长. 对于某些问题, 存在线性算法可以提供在大多数情况下足够好的近似解决方案 [4]. 但总的来说, 只有领域知识才能驯服指数级增长.
这对于我们这些问题求解器设计者有什么启示? CPS在定义我们所需的控制知识方面没有提供杠杆. 许多有趣的概念最终嵌入到Lisp代码中: 高效但并不清晰. 这样的程序如何才能学会改进其性能, 或向我们解释其结果, 或执行自己的现实检查以确保其推理是合理的? 我们尚未提供支持来构建系统, 可以说, 在这些系统中, 大部分有趣的知识都嵌入在程序头脑
中的一组明确信念中. CPS所缺少的是关于表示的承诺.在本书的其余部分, 我们专注于做出此类承诺的模型, 包括领域信息的知识模型和控制知识的程序模型, 即推理的方法
.
搜索本身不再被视为智能的本质. 显然搜索是其中的一部分, 但仅仅是一部分. 搜索程序就像排序、求平方根或打印数字的程序: 仅仅是作为更大系统一部分使用的组件. 搜索反复出现, 但我们会将这位老朋友仅仅视为一个子程序, 是一个更大系统的一部分, 而有趣的工作在别处.
这里的模式匹配器和化简器受到了Gerald Sussman出于研究目的所写的Scheme版本的启发.
正如我们之前所见, 经典问题空间模型本身并不承诺任何特定形式的表示. 这种限制的缺乏给予了我们通用性, 因为我们可以按照自己喜欢的方式编码问题空间. 但如果没有一些约定, 推理引擎无法为我们提供太多杠杆. 一个很好的折衷方案是选择一种通用的底层媒介
, 在其中可以编码特定的表示. 最常见的选择是使用列表结构来实现断言. 非正式地说, 断言是一种陈述, 将某种知识编码到可用于推理的语言中. 正如我们将看到的, 断言是一种极其强大的媒介, 可用于编码各种各样的表示. 通过使用模式匹配作为参考机制, 很像CPS符号代数系统中使用的重写规则, 我们可以实现更大的模块化. 围绕这一理念组织的系统通常被称为模式导向推理系统 (简称PDIS).
本章探讨模式导向推理系统的理念. 我们首先概述此类系统的基本理念. 接下来, 我们描述实现这一模型的微型规则引擎 (TRE). TRE是一个探索性程序, 设计得极其简单. 这使我们能够在第5章展示如何使它们更强大和更高效之前, 专注于模式导向推理系统的本质. 使用类TRE系统设计问题求解器在某种程度上是一门艺术. 为了说明这一点, 我们使用自然演绎作为例子来源. 我们描述了一个特定的自然演绎方案KM*, 改编自Kalish和Montague的工作 [7], 并展示TRE在多大程度上允许我们实现这一方案. 阻碍TRE提供KM*完整实现的限制将通过第5章中提出的扩展来克服.
前一章中的简单模式导向推理系统模型可以通过多种方式进行扩展. 本章探讨其中三种. 首先, 我们展示如何支持更简洁的语法以简化规则的编写. 其次, 我们展示如何在不损害模式匹配所提供的引用灵活性的情况下提高效率. 为此引入的两种方法是规则编译和开放式合一. 第三, 我们通过扩展模型以包含一个面向栈的上下文机制来解决操作假设的问题. 我们在FTRE (TRE的新版本) 中体现了这些理念. 我们使用经典的N皇后问题来说明如何使用FTRE进行搜索. 最后, 我们证明这些机制的组合使我们能够实现自然演绎系统KM*的完整且高效的版本.
FTRE的结构尽可能地保持与TRE接近, 这样我们可以在此专注于讨论围绕这些扩展的问题. 因此, 在阅读本章之前, 必须先理解前一章的内容.
在前几章中, 我们探讨了两种模式导向推理系统. 我们看到上下文机制在问题求解器中扮演着重要角色, 并使用FTRE说明了一种面向栈的上下文机制. 我们研究了如何使用这种面向栈的上下文机制来解决N皇后问题以及实现KM*. 面向栈的上下文机制允许问题求解器引入假设, 即向数据库添加事实, 这些事实可以在上下文弹出时被撤销.
将假设性地向数据库添加可能稍后被撤销的事实的能力在问题求解中至关重要. 其核心原因是大多数AI任务无法以TRE使用的简单前提驱动方式来解决. 复杂的问题求解器经常面临在相互不兼容的选择之间做出决定, 而没有立即的理由选择其中一个. 为了取得进展, 必须做出某种选择, 而这种选择可能稍后需要被撤销. FTRE的上下文机制实现了一些所需的功能, 类似的方案在许多早期AI问题求解器中被使用. 不幸的是, 上下文机制也存在许多缺点. 真值维护系统是一种通用的问题求解设施, 帮助像TRE和FTRE这样的推理引擎方便且高效地操作假设.
本章是对真值维护系统的总体介绍, 分为两个主要部分. 首先, 我们分析诸如FTRE等系统面临的缺点. 其次, 我们提供对真值维护系统 (TMS) 的总体介绍. 之所以进行总体介绍, 是因为存在几个真值维护系统家族, 每个家族提供somewhat不同的功能. 在本章中, 我们给出三个主要家族的基础知识, 随后的章节将分别处理每个家族.
译注: 本章的内容和SICP的约束传播部分差不多. 当然, 毕竟作者之一是Gerald Sussman的学生.
人工智能的一个长期目标是提供能够自动弥合知道什么
和知道如何
之间差距的语言. 现有语言往往位于什么——如何
光谱的一端或另一端. 传统计算机编程语言是如何
极端的一个例子. 用这些语言编写的程序专注于做什么以及何时做, 而其他类型的知识仅体现在对不透明变量名称的解释和条件测试的排序中. 而什么
极端的例子, 即声明性语言, 是传统数学, 在那里可以以方程式的形式表达约束, 而不正式指定如何以及何时使用这些方程式. 本章研究了一类语言, 前件约束语言, 它提供了一种更接近数学约束概念的计算模型, 同时仍提供有效的计算方案. 如今, 这种约束语言已经进入电子表格, 计算机辅助设计系统和其他面向工程师的计算辅助工具中.
我们首先抽象地描述约束网络模型, 并概述它适用于哪些类型的问题. 然后我们打开引擎盖
, 探索这种抽象模型对其实现中知识模型, 程序模型和执行策略选择的影响. 接下来, 我们描述TCON, 一个简单的约束网络解释器, 并通过两个例子展示如何使用约束. 首先, 我们展示约束网络如何用作在问题解决过程中使用数学关系的草稿本. 其次, 我们说明一种称为约束暂停的重要基于模型推理技术, 该技术已在诊断任务中使用.
最后, 我们描述了关于前提约束系统的几个高级主题, 包括高效实现技术, 自扩展网络和对时间变化的建模.
约束语言是围绕这样一种理念组织的: 用户 (人类或程序) 应该以声明式方式表达数据之间的关系. 虽然必须进行计算来确定和执行这些关系的后果, 但所需的计算应该自动进行, 而不需要用户付出特别的努力.
考虑方程 . 要在传统的过程式的计算机语言中包含这个方程所表达的知识, 我们可能会编写
(setq z (+ x y))找到符号. 这仅捕获了我们原始方程的部分含义. 例如, 给定和, 我们可以使用减法来计算. 类似地, 给定和, 我们可以计算的值. 我们可以通过编写额外的x的值和符号y的值, 将它们相加, 并将结果存储为符号z的值
setq语句来开始捕获使用方程的这两种方式, 但这需要额外的代码来描述每个setq适用的条件. 以临时方式编写此类代码需要太多的簿记工作.在约束隐喻中, 这种簿记在内部发生. 我们使用图形符号来表示约束, 既是为了使它们之间的信息传播更清晰, 也是为了消除类似方程式的语句的声明式和命令式解释之间的潜在歧义. 图15.1说明了我们的约定. 为了描绘约束, 我们使用类似于数字电子学中逻辑电路图中使用的图标. 标记为x, y和z的框是单元格. 单元格的主要特征是其值. 单元格还记录其他几条信息, 包括它与约束网络其余部分的关系以及其值是如何提供的. 约束之间的所有连接都通过单元格进行. 这种连接通过连接单元格和约束的线条来描绘.
许多搜索问题具有共同的结构. 问题的每个方面都可以表示为一组替代方案或选择集. 选择的例子包括选择用于飞机机翼的材料或电子电路中电阻器的值. 从每个选择集中选择一个一致的替代方案集合, 即可得到问题的解决方案. 例如, 在电路合成中, 解决方案是设计中每个组件的一组值, 使得产生的电路按照预期执行.
前几章已经说明了几种解决此类问题的一般方法, 包括按时间顺序和依赖性导向的回溯. 在许多情况下, 用搜索技术解决的问题需要指数级的工作量. 但有时, 问题的特殊特征允许应用更高效的解决方法. 指数行为源于生成或检查解决方案片段的组合. 如果一些片段可以通过廉价的局部计算被排除, 搜索空间就会缩小, 搜索变得更加高效. 在某些情况下, 如果局部处理在每个选择集中只留下一个一致的替代方案, 则可能不需要搜索. 这就是符号松弛法 (也称为Waltz filtering) 背后的直觉.
符号松弛是一种常用且强大的AI技术. 没有它, 关于构建问题求解器的讨论将是不完整的. 此外, 对这种技术的理论分析导致了一种新的问题求解模型, 即约束满足问题 (CSP), 它提供了一种描述和分类某些类型问题的形式化方法. 这种分类提供了关于特定类别问题有多难, 以及解决它们需要什么技术的见解.
本章研究符号松弛. 我们首先概述约束满足问题的形式概念. 接下来, 我们探索如何利用离散CSP的结构来实现非常高效的问题求解器, 使用第15章介绍的约束知识模型的变体. 我们描述了一个特定符号松弛系统WALTZER的实现. 通过使用WALTZER解决一些经典的AI问题, 即积木世界场景分析和关于时间关系的推理, 说明了符号松弛的实用性.
从形式上讲, 我们可以将定义问题的选择集集合视为变量, 这些变量从某个特定域中取值. 域可以是有限的, 如我们已经研究的搜索问题, 也可以是无限的, 如第 15 章中的前提约束网络. 变量之间的连接被描述为关系. 关系定义了哪些变量值的赋值是一致的. 在本章中, 我们专门关注域为有限的情况, 因为这类问题在实践中很重要, 并且其理论相对自成体系.
让我们考虑一个简单的谜题来具体化这些想法. 假设我们有变量pianist, harpist, talker, gambler, money, animals, 它们的取值范围都是groucho, harpo, chico. 也就是说, 变量pianist的值是最喜欢弹钢琴的人, 并且是groucho, harpo或chico中的一个. 谜题包含各种关于变量与值之间关系的线索, 例如:
许多AI问题都具有可以视为有限约束满足问题的方面. 将其识别为此类问题有两个好处. 首先, 可以应用复杂性界限来更好地分析问题求解器的性能. 其次, 在这些情况下, 通常可以应用简化的知识模型和算法, 从而提高效率.
何时将问题建模为通过符号松弛求解的约束网络是合理的? 两个性质是重要的:
单元可能包含积木世界场景解释中的线条或连接点的解释, 符号时序逻辑中两个时间区间之间的关系, 或客厅谜案中凶手的身份. 每个单元都有一个域, 由有限的潜在值集合组成. 线条的值可能是其可能的物理解释, 两个时间区间之间关系的值可能包括Before, After和During, 而客厅谜案中角色的值可能是故事中的具名角色. 单元的值是仍然可能的值的子集. 当单元恰好有一个值时, 它被确定. 例如, 在一个好的客厅谜案结束时, 凶手单元被确定. 当可能值集变为空时, 单元被过度约束. 将硬汉
侦探小说解释为客厅谋杀谜案可能导致这种情况.
如前所述, 约束代表单元之间的关系. 约束的例子包括一组线条在连接点中的参与, 相关时间区间对之间的传递关系, 以及侦探和谋杀受害者都不是凶手的惯例. 每个约束连接一组固定的单元. 这些单元是约束的部分. 与之前的约束模型不同, 此模型中的约束从不分层——它们的所有部分必须是单元.
现在我们已经指定了知识模型, 让我们定义过程模型. 单元上有两种操作:
当单元的值之一发生变化时, 约束将被更新. 我们对更新过程的运行方式没有限制, 除了以下几点:
这些操作组合起来强制弧一致性 (arc consistency), 方法如下: 当创建约束网络时, 每个约束都被排队等待更新. 约束建议的任何exclude或pick操作都被单独排队. 单元操作队列的服务优先级高于约束更新队列, 因为单元限制越紧, 每个约束更新可能产生的信息就越多. 单元值的任何变化都会导致它所属的约束重新排队.
我们在下面实现的算法就是符号松弛方法. 一旦启动, 它将继续进行, 直到某个单元变得过度约束或队列变空. 假设约束按上述定义实现, 它必须终止. 为什么? 更新操作只有在至少一个单元失去至少一个值时才会导致其他更新, 而我们假设只有有限数量的单元和值. 一个静态网络可以是确定的, 意味着每个单元都被确定, 或不确定的, 如果任何单元未被确定. 不确定的网络可以通过外部源 (用户或另一个模块) 选择或排除某些单元值来进一步约束. 当网络被确定时, CSP被解决. 确定网络的每组值都是问题的一个解决方案.
有时整个任务可以被建模为CSP, 但这种情况相对罕见. 通常, 将复杂任务分解为子问题更有意义, 其中一些可以自然地被表述为CSP (例如, 在规划器中提供一组受限的时间推理). 在这些情况下, 符号松弛提供了一个过滤器, 可以显著加速额外的搜索. 这是设计问题求解器的分治方法的又一个例子.
本节描述了一个通用的符号松弛引擎, 称为WALTZER, 以纪念David Waltz, 他是这类算法的先驱. 这里描述的代码是列表中的waltzer.lisp. 它分为三个主要部分: 构建约束网络, 传播和询问.