人工智能：一种现代方法学习笔记（第六章）——约束满足问题
定义每一次赋值都会影响下一次的选择范围
约束满足问题指的是针对给定的一组变量及其需要满足的一些限制或一些约束条件，找出符合这些满足这些约束关系的一个解、全部解或是最优解。CSP可分为两个子领域也就是表示（Representation）与推理（Reasoning）。表示可分为通用的及应用特点的方法；推理分为搜索与推断。推断方法，指的是基于约束传播(ConstraintPropagation)的一种特殊推理方法——在推理过程中，使用约束来减少一个变量的合法取值范围，并将这种影响通过CSP网络施加给与之存在约束关系的变量上。而搜索指的是，从变量的所有可能取值中，选取服从约束的取值。约束传播与搜索可以交替进行，或者，也可以将约束传播作为搜索前的预处理步骤，此时，约束传播可以消除不满足约束的子空间（压缩）。在搜索过程中，使用约束传播，可以避免对不满足约束的子空间或子树进行搜索，从而大大提高了搜索效率。
约束传播（constraintpropagation）VS局部搜索约束传播：
partialassignment(部分赋值)初始状态赋空值在剩余的没有被选择的变量选一个进行操作给其赋值，操作满足对应约束条件局部搜素：
fullassignment(一次性将所有变量全部赋值)每次选择一个变量修改值CSP问题形式化csp形式化实例八皇后问题地图着色问题那个定义域里WA,NT之类的是他那个地名代表的缩写
约束的类型绝对约束一元约束：只限制单个变量的取指二元约束：限制多个变量的取指高阶约束（也叫作全局约束）：多个变量的约束（n≥2）偏好约束（约束优化问题，COP）定理：任何有限值域的约束都可以通过加入条件转化为二元约束
约束图和约束超图约束传播概念约束传播的基本思想是，将一个CSP转换为等价的、更简单且易于求解的CSP。其主要技术手段是，消去变量中无效冗余的取值，并将这种变化通过约束变量进行传播，从而也消去那些变量中的无效冗余取值。约束传播可以在不同的粒度上执行，从而形成了不同的约束传播方法。当对问题中变量的赋值满足所有约束时，该赋值是相容的
结点相容上图例子中的那个约束条件：
弧相容路径相容K相容全局约束相容性检查CSP回溯搜索形式化一个标准搜索初始状态：空赋值转移模型：选择一个变量赋值目标测试：所有变量是否都约束满足条件路径代价行动
回溯搜索提高回溯搜素的效率变量次序最少剩余值变量优先选择那个可以符合约束条件赋值的数量最少的那个变量来进行赋值但是，如果几个变量有相同的赋值数量剩余值，那么就选择会影响其他变量数最多的那个变量进行赋值（即：最大度变量优先），这样可以有效的减少之后的分支因子
最大度变量优先
值的次序变量优先选择哪一个值（推理），从选择值的角度来看，要尽可能的使得剩余变量他们可以选择的值最多（即：最少约束值优先）
推理算法提前发现失败：前向检验比如上图：第四步的时候，SA可以选择的值域变为空，进行回溯
更早的发现失败：维护弧相容CSP局部搜索CSP的问题结构树形结构的CSP构造树形结构：基于删除结点的办法构造树形结构：基于合并结点办法总结约束满足问题：环境：单agent、延续、静态、完全可观察一种特殊的搜索问题
约束满足问题vs.经典搜索问题：状态s：一组变量(彼此之间有约束)的部分或全部赋值{x1,x2,…,xn}动作：给每个变量赋不同的值assignment(xi,v)状态转移：Result(s,assignment(xi,v))=s’,s’中xi=v,其它变量赋值与s一致目标：所有变量都被赋值，且满足约束
当对问题中变量的赋值满足所有约束时，该赋值是相容的CSP问题的解是所有变量的相容的、完整的赋值
约束满足问题的特性可交换性:对变量赋值的顺序不影响最终结果约束传播：一个变量的赋值将改变其它变量的值域
约束满足问题的描述需要描述状态、后继函数、目标测试最重要的是描述约束
任何CSP都可以转变为只含二元约束的CSP高阶约束变为二元约束：引进新变量表示变量对的值，引进约束如“X是Y中第一个元素”改变变量值域消除一元约束
标准搜索过程：状态为到目前为止的赋值初始状态:空赋值,{}后继函数:对一个未赋值的变量赋一个可能值目标检测:完整的满足所有约束的赋值
与经典搜索的不同之处Idea1:一次只考虑一个变量Idea2:扩展节点时，只考虑当前变量的合法赋值考虑以上两点的深度优先搜索称为回溯搜索
约束满足问题如何求解CSP的关键特性:可交换性和约束传播
下一次选择哪个变量来赋值?选择值域最小的约束变元
策略1：最小剩余值(Minimumremainingvalues,MRV)试图缩小分支因子
策略2：度启发式选择最受约束的变量先赋值减少后续变量的分支
在变量的值域中尝试的顺序是什么?
最少约束值（Leastconstrainingvalue）选择当前变量的所有可能值中对未赋值变量的值域约束最小的值
我们能否早些检测到失败?向前检测跟踪未赋值变量值域变化当某个变量值域为空时，算法结束弧相容X—>Y是相容的当且仅当x的每一个取值y都有可选的值可以在每次赋值之前做一次弧相容检测弧相容能够比前向检查更早地检测到失败
人工智能发展悠久，并且经历过两次寒冬
现在几乎没有一家公司不说自己在研究人工智能的。一些小公司可能通过人工智能实现了一些具体应用，但是真正在人工智能上有积累的，还是微软、Google这样的大公司。
伴随着人工智能概念的火热，相关的人才竞争也非常激烈。百度就是一个例子，在今年年初从微软招来了陆奇担任集团总裁和COO全面负责人工智能，但首席科学家吴恩达却从百度离职。
对于人工智能方面人才的流动，微软全球资深副总裁、微软亚太研发集团主席洪小文在接受凤凰科技专访时表示，这是无法避免的事情。他说科技行业的人才流动在25%-30%左右，而微软亚洲研究院人才流失比例远远低于行业平均。
“人才的流动是很自然的。你可以提供更好的工作环境，更好的待遇，别人也可以做到。所以应该用平常心去看。”洪小文说，然后补充道：“这不代表我们就不努力去吸引最优秀的人了。”
人工智能也是微软研究的重要方向，洪小文表示，20年前微软亚洲研究院成立的时候，人工智能就是重点研究领域之一。现在人们提到人工智能，会联想到一些人的名字，但在这背后，有更多研究人员、科学家并不为人所知。
洪小文特别指出，我们看到人工智能的现在，更应该看到人工智能过去的发展。“人工智能发展了60年，还经历了两次寒冬。”他说。
按维基百科的介绍，1956年，在达特茅斯学院举行的一次会议上正式确立了人工智能的研究领域。这是人工智能的开始。
人工智能的两段寒冬分别是1974-1980年和1987-1993年。第一段低潮的原因是之前过于乐观，但发现了一些障碍无法克服，导致对人工智能的资金支持减少，也影响了人们在这个领域研究的积极性。第二段低潮的原因是和之前那次类似，都是因为发展不及预期，而遇到资金困难。
但这些年来，也有很多人并没有放弃人工智能的研究，这才导致今天人工智能的爆发。未来会怎么样呢？洪小文做了两个预测，他表示，未来机器可能会具有情感，对不同的人展现出不同的个性。这一点在微软小冰身上已经有了一点点迹象，比如和她对话的时候，她有时候会故意不正面回答你的问题。
洪小文的另一个预测可能略为悲观，他认为人工智能不会发展出创造力。他认为创造力是生物独有的，而且人类有时候可以从很微小的地方推断出惊人的东西，比如爱因斯坦，对引力波的判断，当时他并没有太多数据，直到今天人们才探测到了一点点引力波的信号。“我认为我有生之年看不到机器有创造力，也许永远不会有。”他说。
人工智能的前世今生
今年3月份发生了一件可入选年度新闻的大事——计算机程序“AlphaGo”在五番棋中战胜了世界围棋冠军、职业九段选手李世石。整个比赛跌宕起伏，引人注目。起初人们几乎一边倒地预测AlphaGo会大比分败给李世石，但最终李世石却1∶4不敌AlphaGo，这就如同在平静水面丢进巨石，掀起了人工智能的新一轮研究热潮。
预测失败主要是人们认为AlphaGo还停留在多年前的智能水平上，认为其仍然采用穷举搜索法，而围棋复杂的局面将让这种搜索难以为继。人工智能已发生了不为人知的深刻变化，在搜索算法、机器学习算法和综合统计分析方面获得了飞速发展，正是AlphaGo让这种变化浮出水面，也让人们看到了人工智能的发展与变迁。
围棋世界冠军李世石输给机器令世人震惊，机器因此被视为洪水猛兽，甚至有人断言机器统治人类的时代到来了。其实，计算机远没有想象中强大，尽管人类开发的程序在某些游戏上打败了人类自己，但计算机还远远不能掌控开放结局的游戏。在感情交流和沟通、有陷阱的推理等领域，计算机远远赶不上人类的思维。直到2014年才有计算机程序勉强通过了英国数学家图灵（1912—1954）给出的“图灵测试”。
图灵与图灵测试
图灵1912年6月23日出生于英国伦敦，1931年进入剑桥大学学习数学，并对英国数学家罗素和怀特海创立的数理逻辑很感兴趣，从而迷上了《数学原理》。1931年哥德尔提出了著名的“不完全定理”，而图灵也提出设想：是否有机器能通过某种一般的机械步骤，在原则上逐个解决所有数学问题。
1936年图灵对“可计算性”给出了严格数学定义，并提出“图灵机”设想。1950年10月图灵发表论文《机器能思考吗？》，第一次提出“机器思维”，反驳了机器不能思维的论调。正是这篇划时代的文章为图灵赢得了“人工智能之父”的荣誉。他提出假想：一个人在不接触计算机的情况下，通过特殊方式和计算机进行一系列问答，如果在相当长时间内，无法判断对方是人还是计算机，那就可以认为这台计算机具有与人相当的智力，即这台计算机是能思维的，这就是著名的“图灵测试”。一个等价说法是，如果电脑能在5分钟内回答测试者提出的一系列问题，且其超过30%的回答让测试者误认为是人类所答，则电脑就通过了图灵测试。图灵预言：在20世纪末一定会有电脑通过图灵测试。
1951年图灵当选为英国皇家学会会员，就在他事业步入辉煌之际灾难降临了。1952年图灵遭到警方拘捕，原因是他是一个同性恋者。图灵在入狱和治疗两者中选择了后者，但治疗却是致命的。他丢掉了工作，脾气变得躁怒不安，性格更为阴沉怪僻。1954年6月7日，再也无法忍受的图灵在咬了一口在氰化物溶液中浸泡过的苹果后走完了短暂的一生。
1966年美国计算机协会设立图灵奖，专门奖励那些对计算机事业作出重要贡献的个人。图灵奖对获奖者要求极高，评奖程序极严，一般每年只奖励一名计算机科学家，尽管“图灵奖”的奖金数额不算高，但它却是计算机界最负盛名的奖项，有“计算机界诺贝尔奖”之称。随着图灵的理论和设想对现代计算机发展越来越显露出重要的作用，人们也开始反思当年对图灵的审判和治疗。2009年时任英国首相戈登·布朗承认图灵因同性恋问题而遭受的对待方式骇人听闻。2012年6月23日，图灵诞辰一百周年之际，伦敦奥运会的火炬传递特意将一个交接仪式选择在曼彻斯特市图灵塑像前进行，以示对他的致敬。
人工智能的浪潮和寒冬
1956年人工智能之父麦卡锡（1927—2011）和一批数学家、信息学家、心理学家、神经生理学家和计算机科学家在达特矛斯大学召开了一个会议，首次提出了“人工智能”（简称AI）这一术语，这标志着人工智能作为一门新兴学科正式诞生。以此为标志，1956年到1974年出现了第一次人工智能的发展浪潮。
中国学者也在人工智能的早期发展中作出了突出贡献。1959年洛克菲勒大学教授王浩（1921—1995）用计算机在不到9分钟时间里将《数学原理》的全部定理证明完毕。数学大师罗素得知此事后感慨万分，他写道：“我真希望，在怀特海和我浪费了10年的时间用手算来证明这些定理之前，就知道有这种可能。”王浩因此被国际公认为机器定理证明的开拓者之一。1976年我国著名数学家吴文俊院士也开始了定理证明机械化的研究。他从理论上证明：初等几何主要一类定理可以机械化证明，创立了机器证明的“吴方法”，首次实现了高效的几何定理的机器证明。他的工作获得了自动推理学界的高度赞扬，1997年吴文俊荣获国际自动推理领域的最高奖“埃尔布朗自动推理杰出成就奖”。
20世纪60年代，在算法方面出现了很多世界级的发明，其中包括一种叫做增强学习的雏形（即贝尔曼公式），增强学习就是谷歌AlphaGo算法核心思想内容。除此之外，第一次浪潮还在硬件方面有了突破，科学家制造出了更加聪明的机器。一台叫做STUDENT（1964）的机器能证明应用题，一台叫做ELIZA（1966）的机器可以实现简单的人机对话。人工智能界踌躇满志地认为照这样的发展速度，人工智能真的可以代替人类。
但情况并不如此乐观。人们发现逻辑证明器、感知器、增强学习等只能做简单、非常专门的任务，稍微超出范围就无法应对。一方面，人工智能所基于的数学模型和数学手段有一定的缺陷；另一方面，计算复杂度以指数程度增加后，会成为不可能完成的任务。先天缺陷导致人工智能遇到瓶颈，20世纪70年代“人工智能寒冬”到来了。在这段近20年的“冬天”里，人工智能的科学活动和相关商业活动大大衰退，直到80年代卡耐基梅隆大学制造出专家系统。很快专家系统就应用到了工业领域，这些成功的应用又进一步刺激了专家系统的发展，许多企业（DEC、IBM、TI、Xerox和HP）和大学（MIT、Stanford）都参与到专家系统开发中来。80年代出现了人工智能数学模型方面的重大突破，如1986年的多层神经网络和BP反向传播算法等。80年代末，世界500强企业中近一半都研制或使用了专家系统——人工智能第二次高潮又到来了。
然而，1987年到1993年现代PC的出现让人工智能再次陷入寒冬。当时苹果、IBM开始推广第一代台式机，计算机开始进入寻常百姓家庭，其费用远低于专家系统的软硬件开销。于是，政府经费开始缩减，寒冬又一次来临。不过，这次寒冬并未持续很长时间，即便是在寒冬期，领域内也悄然发生着某些变化。
人工智能的春天
20世纪八九十年代，人工智能领域的数学理论有了翻天覆地的变化。贝叶斯网络、隐马尔科夫模型以及其他大量的统计模型广泛地应用到了模式识别、医疗诊断、数据挖掘、机器翻译和机器人设计等领域。与此同时，摩尔定律的积累效应导致计算机（计算能力）越来越强大。这两方面的暗流一旦汇集，立即就掀起了应用浪潮。
标志着人工智能新的春天到来的是一个大事件——1997年5月11日，在一场国际象棋的人机大战中，超级计算机“深蓝”（DeepBlue）首次击败了当时等级分世界第一的棋手卡斯帕罗夫。“深蓝”由美国IBM公司制造，重达1270公斤，每秒钟可以计算2亿步棋。说起来，中国人还在“深蓝”的研制中有着巨大的贡献。
1988年卡耐基梅隆大学的台湾人许峰雄设计了一款对弈计算机“深思”（DeepThought），赢得了北美计算机国际象棋冠军，并在次年赢得世界计算机国际象棋冠军。1989年10月在与卡斯帕罗夫的首次较量中，“深思”惨败。经过若干改进，1995年“深蓝”诞生了，并于1996年与卡斯帕罗夫再度交手。尽管这次“深蓝”仍以1胜2平3负输掉比赛，但棋王卡斯帕罗夫赢得并不轻松，这也是计算机首次在国际象棋上有战胜人类的记录。接下来“深蓝”被再次改造，学习了两百多万局对局，还有四位国际象棋特级大师陪练。终于“深蓝”在1997年彻底击败了棋王卡斯帕罗夫。“深蓝”的胜利标志着人工智能的一个新阶段，也意味着人类将不得不认真地思考人与电脑的关系。
在更广泛领域内，人工智能逐渐展现了越来越多的优势，达到甚至超过了人类的认知水平。反过来人工智能也在相当程度上促进了计算机硬件的发展，并从高高在上的阳春白雪变成了影响百姓生活的技术。20世纪的最后20年，互联网异军突起，深刻地影响了人类的文明进程。人工智能也因此和大数据紧密地结合在一起，发生了理论和技术性的突破，并因此带来了方向性的转变。
（作者单位：河北科技大学理学院数学系；河北地质大学数学系）