人工智能 总结 小抄 重点.doc

人工智能第一章 绪论本课程的学习内容1、智能体如何求解问题搜索2、智能体如何进行推理决策谓词逻辑与归结原理3、智能体如何描述和保存各种信息知识表示4、智能体如何通过训练获取和更新知识机器学习5、人工智能语言简介prolog人类的智能什么是智能 智能是个体有目的的行为、合理的思维, 以及有效的适应环境的综合性能力人类个体的智能感知环境：认识客观事物、客观世界与自我学习能力：取得经验、积累知识理解能力：理解知识，并能联想、推理、判断、决策预测能力：洞察事物发展变化的趋势语言能力：运用语言进行描述和概括应对能力：实时、迅速、合理的采取行动人类的智能人工智能与智能人工智能就其本质而言，是对人的思维的信息过程的模拟。对于人的思维模拟可以从两条道路进行，一是结构模拟，仿照人脑的结构机制，制造出“类人脑”的机器；二是功能模拟，暂时撇开人脑的内部结构，而从其功能过程进行模拟。“人工智能”同人类智能的本质区别：人工智能纯系无意识的机械的物理的过程，人类智能主要是生理和心理的过程人工智能与人类智能Stuart Russell和Peter Norvig把当前有关AI的定义分成四类人工智能与人类智能类人行为与理性行为类人：按照人类模式思考和行为理性：在一定条件下正确的思考和行为理性与全知过马路例子中的智能体2：驾驶员计算危险距离与次危险距离 如果危险距离内有行人，则紧急刹车如果次危险距离内有行人，则减速慢行否则，保持匀速前进什么是人工智能人工智能（Artificial Intelligence,简称AI）定义：P21、模拟人类的智能活动，即：感知、学习、理解、预测、应对外部世界的能力2、建造人造的智能系统，能够代替人类完成特定的智能行为人工智能的发展史先驱神话, 幻想和预言中的AI在古代的神话传说中, 技艺高超的工匠可以制作人造人, 并为其赋予智能或意识中世纪出现了使用巫术或炼金术将意识赋予无生命物质的传说Samuel Butler的“机器中的达尔文”一文(1863)探讨了机器通过自然选择进化出智能的可能性. Pamela McCorduck在其著作“会思考的机器”中指出的, AI的起源是“古人成为造物神的愿望”形式推理中国, 印度和希腊哲学家均已在公元前的第一个千年里提出了形式推理的结构化方法，如亚里士多德的三段论人工智能的发展史先驱自动机器1642年，数学家Pascal 发明了加法机1694年，数学家莱布尼兹Leibniz 发明了世界上第一台计算器人工智能的发展史先驱1834年，查尔斯?巴贝奇 (Charles Babbage) 构想和设计了一台完全可编程的用于公式演算的多功能计算机巴贝奇分析仪由于技术条件，经费限制，以及无法忍耐对设计不停的修补，这台计算机在他有生之年 始终未能问世。尽管如此，巴贝奇分析仪仍然 被公认是第一台打孔卡片计算 机 人工智能的发展史现代人工智能的孕育期（1943-1955年）1943年， 麦克克劳奇W.McCulloch和皮兹W.Pitts提出了人工神经元模型，被认为是AI的最早工作，并指出神经元网络可以学习海布D.Hebb，对神经元网络提出了一种更新规则，被称为海布学习1951年， 普林斯顿大学的博士研究生明斯基M.Minsky建造了一台神经元网络计算机1950年，阿兰图灵A.M.Turing发表论文计算机器与智能，描绘了AI的完整景象 人工智能的发展史图灵（1912-1954）英国数学家和逻辑学家，二十世纪最杰出的科学家之一，计算机科学之父，人工智能之父，可与美国的冯?诺依曼相媲美的电脑天才冯?诺依曼生前曾多次谦虚地说：现代计算机的概念当属于阿兰?图灵人工智能的发展史图灵英年早逝。在他42年的人生历程中，他的创造力是丰富多彩的。24岁提出图灵机理论，28岁破解德国密码系统，31岁开发计算机Colossus33岁设想仿真系统，35岁提出自动程序设计概念，38岁设计“图灵测试”。这一朵朵灵感浪花无不闪耀着他在计算机发展史上的预见性。在他短暂的生涯中，图灵在量子力学、数理逻辑、生物学、化学方面都有深入的研究。1948年起，图灵因为个人生活方面的问题受到一系列不公正的待遇。1954年，图灵死在自己的卧室里，床头有一只咬了一小半的苹果。人工智能的发展史图灵最高的成就是在计算机和人工智能方面，他是这一领域开天辟地的大师。为表彰他的贡献，美国计算机学会 ACM 1966年设立了“图灵奖”，颁发给最优秀的电脑科学家。这枚奖章就像“诺贝尔奖”一样，代表了计算机学科的最高荣誉。到目前为止，唯一获此殊荣的华人是，Andrew Chi-Chih Yao(姚期智)。2000年由于在伪随机数的生成算法、加密算法和通讯复杂性方面的贡献获得图灵奖人工智能的发展史图灵机一条无限长的纸带 TAPE一个读写头 HEAD一套控制规则 TABLE一个状态寄存器“图灵机”不是一种具体的机器，而是一种思想模型。但是现代电脑确实是用相应的程序来完成设定好的任务。“图灵机”奠定了整个现代计算机的理论基础。在电脑史上与“冯?诺依曼机”齐名人工智能的发展史图灵测试第一次给出了检验计算机是否具有智能的哲学思想设想一个人类提问测试者，一个声称自己是人的计算机A和一个人类被测试者B测试者提出问题，A与B分别回答。如果A与B的回答，使得人类测试者无法区分是人的回答还是计算机的回答，则计算机具有了智能。人工智能的发展史图灵认为：如果在30%的实验中，机器迷惑了测试者，那么它就通过了测试。并且预言，到2000年将会有足够好的计算机通过图灵测试。目前仍然没有能够成功通过图灵测试的电脑，但已有电脑在测试中“骗”过了测试者要通过图灵测试，要求计算机具有更多的技能 自然语言处理、自动推理、计算机感知能力、知识表示、机器学习等能力，甚至能够模拟人类的情感和弱点 人工智能的发展史人工智能的诞生1956: 世界上第一次正式的AI会议美国的Dartmouth College，为期2月John McCarthy 正式提出“Artificial Intelligence”这一术语, “computional rationality” 著名参加者：J.McCarthy(1971)、C.Shannon、M.Minsky(1969)、A.Newell(1975) 、A.Simon(1975)、 W.McCulloch、S.Papert人工智能的发展史早期的期望与繁荣由于根深蒂固的相信“一台机器永远不可能做 X ”，一点点的人工智能的实现都是令人震惊的1959: Frank Rosenblatt提出感知器模型（Perceptron Model) 1959: MIT(麻省理工) AI Lab正式成立（Minsky和McCarthy）1958: Newell和Simon的四个预测十年内，计算机将成为世界象棋冠军十年内，计算机将发现或证明有意义的数学定理十年内，计算机将能谱写优美的乐曲十年内，计算机将能实现大多数的心理学理论人工智能的发展史困难与黑暗时期 虽然机器能够解决一些极其错综复杂的难题，但有很多对人来说简单到不能再简单的事情，对电脑却难似上青天 理解 机器翻译问题：无限计算能力的幻觉 尝试各种步骤可能组合组合爆炸 智能体结构的限制 简单神经元网络虽然能够学习，但表示能力有限人工智能的发展史知识的力量专家系统的兴起1977年，费根鲍姆E.Feigenbaum(1994) 提出了“知识工程”的概念，标志着AI研究从传统的以推理为中心，进入到以知识为中心的新阶段。用大量的规则描述专业知识，采用启发式的解题方法。专家系统在医疗、自然语言理解、工程、军事和商业 等各个领域80年代初，美、英、日等国先后投资数十亿美元用于AI工业，人工智能重新获得人们的普遍重视然而，商业的投机动机导致了过分承诺，野心勃勃的目标从来没有实现过，投资者在八十年代末重新撤回了投资. 人工智能的发展史近年人工智能的发展趋势神经元网络的回归（1986-今） 多层反向神经元网络成为热点里程碑1997年，IBM计算机深蓝击败卡斯帕罗夫；2005年，Stanford 开发的一个自动驾驶机器人成功的在一条沙漠小路上行驶131公里；2009年，Blue Brain Project 宣称成功模拟部分鼠脑智能体技术兴起(intelligent agents)AI比以往的任何时候都更加谨慎, 却也更加成功人工智能的研究目标感知外部环境传感器设计通过学习获得和更新知识设计学习方法和元件存储和使用知识知识的形式化描述根据环境和知识进行分析、判断、预测和决策 设计推理决策方法和元件根据决策作出动作和行为设计执行器人工智能的研究目标人工智能的应用知识工程 以知识本身为处理对象，研究如何运用人工智能和软件技术，设计、构造和维护知识系统专家系统智能搜索引擎机器翻译和自然语言理解数据挖掘和知识发现 人工智能的应用自动工程 代替人类进行野外勘探、自动驾驶、高危操作等工作自动驾驶自动装配海洋探索太空探索人工智能的应用机器视觉，模式识别指纹识别；视网膜识别；掌纹识别；人像识别；文字识别；图像识别；车牌识别；人工智能的应用机器思维与推理人机博弈定理证明自动程序设计人工智能的研究方法 符号主义逻辑推理 连接主义仿生学、心理学 行为主义进化、控制论 人工智能的研究方法符号主义传统人工智能是符号主义，它以Newell和 Simon提出的物理符号系统假设为基础。物理符号系统假设认为物理符号系统是智能行为充分和必要的条件。该系统可以进行建立、修改、复制、删除等操作，以生成其它符号结构符号智能是以知识为基础，通过推理进行问题求解人工智能的研究方法连接主义研究非程序的、适应性的、大脑风格的信息处理的本质和能力。人们也称它为神经计算。1873年，神经科学的发展使人们认识了神经元，这一技术很快被运用于研究大脑结构和人类智能近年来的神经元网络迅速发展,大量的神经网络的机理、模型、 算法不断地涌现出来以数据为基础，通过训练建立联系，进行问题求解。包括人工神经网络、遗传算法、模糊系统、进化程序设计、人工生命等人工智能的研究方法行为主义Brooks提出了无需知识表示的智能、无需推理的智能。他认为智能只是在与环境的交互作用中表现出来，人们称为基于行为的人工智能，简言之，称为行为主义在许多方面是行为心理学观点在现代人工智能中的反映刺激反应性原理广泛的应用于简单智能体的构建中人工智能的学科基础人工智能是一门集大成的新兴学科，涉及到许多领域的知识哲学规则能否得到合理的结论意识是什么知识是从哪里来的知识如何导致行动人工智能的学科基础数学什么是合理的规则什么样的问题可以通过计算求解不确定的知识如何进行推理经济学与运筹学如何行为能够获得最好的结果博弈行为决策理论人工智能的学科基础神经科学大脑的结构人类神经系统的结构人类神经系统如何处理信息心理学人类和动物如何思考和行动语言学自然语言如何产生语言与思维的关系人工智能的学科基础控制论如何控制人工制品的按照预定的目标工作计算机工程如何制造具有能干的计算机人工智能第二章 与或图搜索问题与或图基本概念耗散值的计算C(n)为k连接符的路径耗散值，N为目标节点集合，n1 ,n2 ,.ni 为由k连接符连接的i个节点，k(n,N)为节点n到N的耗散值，则：与或图基本概念耗散值的计算h(s0)=12,h(s1)=9, h(s2)=3,h(s3)=2节点耗散计算公式为： f(n)=g(n)+h(n) f(s0)=12 f(s1)=2+9=11 f(s2)=2+6+2=10 f(s3)=2+5+3=10K连接符需要考虑其全部分支 f(k) =f(s2)+f(s3) =20; 该算例中s0s1的路径耗散加了2次，应根据实际问题确定 与或图基本概念可解性判别一个节点是可解，则节点须满足下列条件之一： 终止节点是可解节点； 一个与节点可解，当且仅当其子节点全都可解； 一个或节点可解，只要其子节点至少有一个可解。与或图基本概念一个节点是不可解，则节点须满足下列条件之一： 非终止节点的端节点是不可解节点； 一个与节点不可解，只要其子节点至少有一个不可解； 一个或节点不可解，当且仅当其子节点全都不可解。与或图基本概念解图解图（树）是由可解节点形成的一个子图（树），这个个子图（树）的根是初始节点，叶为终止节点，且这个子图（树）还一定是与或图（树）。从初始节点到目标节点集的路径解图中叶节点集就是目标节点集解图中每一个非终止节点都有后继节点与或图基本概念与或图基本概念与或图应用例：事故树触电事故一般由人的不安全行为和物的不安全状态共同引发。人的不安全状态是指人接触带电体，包括操作对象带电、触及相邻带电体三种情况。物的不安全状态包括防护失效和接地不合格两种情况。与或图的启发式算法与或图搜索与状态图搜索类似，也是不断地扩展节点，并配以返回指针，而形成一棵不断生长的搜索树。与或图搜索也分为盲目搜索和启发式搜索两大类。盲目搜索常用的方法也是深度优先和广度优先两种基本策略。 与或图的启发式搜索同样依赖于评价函数，其形式一般定义为f(n)=g(n)+h(n)与或图的启发式搜索同样可以用open表和closed表实现，但是open表根据K连接符的耗散排序， closed表中多了一列“可解性”判别与或图的启发式算法步1 把初始节点S0放入OPEN表；步2 移出OPEN表的耗散值最小的K连接符对应的节点N放入CLOSED表，并冠以序号n；步3 若节点N可扩展，则做下列工作：(1)扩展N:将其子节点配上指向父节点的指针后放入OPEN表； (2)可解性判别：考察这些子节点中是否有终止节点。若有，则标记它们为可解节点，并将它们放入CLOSED表，然后由它的可解返回推断其先辈节点的可解性，并对其中的可解节点进行标记。如果初始节点S0也被标记为可解节点，则搜索成功，结束。 (3)删去OPEN表中具有可解先辈的节点（因为其先辈节点已经可解，故已无再考察该节点的必要），转步2；与或图的启发式算法步4 若N不可扩展，则做下列工作： (1)不可解判别：标记N为不可解节点，然后由它的不可解返回推断其先辈节点的可解性，并对其中的不可解节点进行标记。如果初始节点S0也被标记为不可解节点，则搜索失败，退出。(2)删去OPEN表中那些具有不可解先辈的节点（因为其先辈节点已不可解，故已无再考察这些节点的必要），转步2；与或图的启发式算法例:初始节点为n0，目标节点为n7,n8。任意单步路径耗散恒定为1博弈与对抗搜索问题1：假如你正跟恋人用手机通电话，突然信号断了。这时，你会立即拨电话过去，还是等你的恋人拨电话过来? 问题2：两个饥饿的人从神仙那里得到了一根鱼竿和一篓鲜鱼。.如果是你，你会选择哪个，怎么行动？博弈与对抗搜索博弈(game) ：研究类似于棋类、赌博、游戏的，具有斗争、竞争性质的决策行为对决双方（各方）的目标是往往冲突的各方在决策时都必须考虑对方的行动各方都以自身利益最大化为决策的准则可以分为合作博弈与非合作博弈两类 博弈论(game theory)创始人:冯?诺依曼 博弈与对抗搜索博弈与对抗搜索你每天都在博弈学生阶段：跟同学博弈，跟老师博弈工作了：跟老板、同事博弈，面临优胜劣汰的残酷竞争谈恋爱：跟竞争对手博弈，跟恋人博弈结婚后：跟配偶博弈，跟孩子博弈任何时候：心理博弈，即自己和自己博弈博弈与对抗搜索经典的博弈模型囚徒困境两人因盗窃被捕，可以判他们犯盗窃物品的轻罪。警方怀疑其有抢劫行为但未获得确凿证据，除非有一人供认或两人都供认。囚徒被分离审查，不允许他们之间通信，交代政策如下：如果两人都供认，每个人都将因抢劫加盗窃被判2年监禁；如果两人都拒供，则两人都将因盗窃罪被判半年监禁；如果一人供认而另一个拒供，则供认这被认为有功而免受处罚，拒供者将因抢劫罪、盗窃罪以及拒供重判5年。博弈与对抗搜索弱者的生存之道智猪博弈有两头非常聪明的猪，一大一小，共同生活在一个猪圈里。猪圈的一端有一个踏板，另一端有一个食槽。踏板连着开放饲料的机关，踏一下踏板，食槽里就会出现10个单位食物。任何一头猪去踏这个踏板都会付出相当于两个单位食物的成本每只猪都可以选择“踏”或者“不踏”踏板。博弈与对抗搜索博弈与对抗搜索猪的选择两智猪一起踏踏板，再一起回槽边进食 大猪：8单位食物；小猪：2单位食物； 减掉踏踏板的2个成本，大猪收益6，小猪收益0大猪踏踏板，小猪槽边守候 大猪：6单位食物，4；小猪：4单位食物，4小猪踏踏板，大猪槽边守候 大猪：10单位食物，10；小猪：0单位食物，-2两猪都不去踏踏板，则都得不到食物，0 博弈与对抗搜索博弈与对抗搜索弱者的生存之道三人决斗A、B、C三人决斗，每人有2颗子弹，每次发一枪。A、B、C的命中概率分别为0.3、0.8、1.0。三人按A、B、C顺序依次发射，两轮后对决结束。每次可以选择向对手发射，也可以放空枪。射中即死。问在这场博弈中A的最优策略。博弈与对抗搜索先考虑A对手会采取什么行动C，命中率为1，可选射A、射B、射空 如果轮到C发射时只剩一个对手，则一枪解决对手；如果A、B都存活，C会选择射谁？博弈与对抗搜索A，命中率0.3，可选射B，射C，射空如果A射B如果A射C博弈与对抗搜索对空发射博弈与对抗搜索弱者的生存之道珍珑棋局博弈与对抗搜索二人零和博弈人工智能的博弈一般指二人零和博弈两位游戏者参与完整信息轮流行动游戏者有输有赢，一方所赢正是另一方所输，而游戏的总成绩永远为零一个笑话：两个经济学家与 X X 博弈与对抗搜索博弈问题初始状态：当前系统状态（棋盘局面）、轮到哪个游戏者行动后继函数: (行动，状态)，一个规则允许的行动与该行动引起系统状态的变化终止测试：判断游戏是否结束收益函数：对系统状态的评价博弈与对抗搜索极大极小值算法搜索过程分为搜索树生成和格局值估计两部分先生成搜索树，然后用评价函数对每种局面进行评估，评价函数值越大，对我方（MAX）越有利，对敌方（MIN）越不利，反之亦然当MAX行棋时，将选择对我方最有利的步骤，也就是可选步骤中评价函数值极大的一步当MIN行棋时，会选择对我方最不利的步骤，也就是可选步骤中评价函数值极小的一步最终找到对MAX最有利的行棋步骤博弈与对抗搜索分钱币游戏（Grundy博弈）规则：一堆钱币，两位选手甲方先将钱币分成数目不同的两小堆乙方再选其中一堆，将其分成数目不同的两小堆甲方接着分，。依此类推直到一方无法将钱币再分成不同的两小堆时认输博弈与对抗搜索7个硬币的Grundy博弈博弈与对抗搜索三子棋的极大极小值过程规则：井字棋盘，两人对弈任意三子一线即为获胜评价函数,对局面p：f(p)=e(+p)-e(-p)e(+p)是p上有可能使MAX成三子为一线的数目e(-p)是p上有可能使MIN成三子为一线的数目博弈与对抗搜索具有对称性的棋盘可认为是同一局面。博弈与对抗搜索极大极小值算法的特点优点先按照深度优先方法生成树，再标记评价，思路简单具有完备性缺点空间复杂度和时间复杂度巨大，不具备实用性 以中国象棋为例，一盘棋平均走50步，总状态数约为10的161次方，假设计算机1毫微秒走一步，约需10的145次方年但该算法是博弈问题数学分析和其他算法的基础博弈与对抗搜索极大极小值算法的改进博弈与对抗搜索- 剪枝对极大极小值算法的改进一边生成节点一边对节点评价，剪去一些没用的分枝 有限深度优先:对于MAX节点， 是该节点生成的若干子节点的最大评价值:对于MIN节点， 是该节点生成的若干子节点的最小评价值博弈与对抗搜索剪枝若MIN节点n的值小于或等于它先辈节点的值，则n 以下的分枝可停止搜索，并令节点n的倒推值为。剪枝若MAX节点n的值大于或等于它先辈节点的值，则n 以下的分枝可停止搜索，并令节点n的倒推值为。博弈与对抗搜索问题1：该剪枝是剪枝还是剪枝？问题2：该剪枝为有限深度优先算法，深度是多少？博弈与对抗搜索例：P75 2.14要求： 剪枝用， 剪枝用X在图上标出步骤：1、先标出MAX （）节点和MIN（ ）节点2、从最左边的一枝开始，倒推其先辈节点的、 值3、按照从左到右的顺序，依次对相邻枝，按照 剪枝条件进行剪枝本章重点与或图的基本概念、解图、可解节点与不可解节点简单问题的与或图表示极大极小值算法的基本思想剪枝、剪枝人工智能第二章 搜索问题本章的内容与目标搜索与搜索问题搜索问题的求解步骤 无信息（盲目）搜索有信息（启发式）搜索搜索与搜索问题人类的实际搜索行为人工智能所要解决的问题大部分不具备明确的解题步骤，而只能是利用已有的知识一步一步地摸索前进。 根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，使问题得到圆满解决的过程称之为搜索 。搜索方法的经典应用8数码问题传教士和野人问题旅行商问题4皇后问题迷宫问题博弈问题搜索方法的一般步骤1、定义状态描述形式2、定义算符是把问题从一种状态变换到另一种状态的方法代号，即状态演变规则3、确定初始状态（初始节点）和目标状态（目标节点）4、状态更新根据算符更新当前状态5、目标测试判断更新后的状态是否为目标状态，若不是则转到4，否则转到66、搜索成功,记录搜索路径用open表和closed表保存搜索经过的各个节点open表和closed表的一般结构无信息搜索又称盲目搜索/穷举式搜索，只能按照预先规定的搜索控制策略进行搜索，没有任何中间信息来改变这些控制策略。具有盲目性，效率不高，不便于复杂问题的求解。常用方法有广度优先搜索和深度优先搜索以及这两种搜索方法的改良方法。宽度优先搜索最简便的图的搜索算法之一，属于一种盲目搜寻法。目的是系统地展开并检查图中的所有节点，以找寻结果。基本思想是首先搜索和初始节点距离为1的所有顶点，然后再去搜索和出始节点距离为2的其他顶点，依次类推它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。 宽度优先搜索广度优先搜索算法：步1 把初始节点S0放入OPEN表中。步2 若OPEN表为空, 则搜索失败,退出。 步3 取OPEN表中前面第一个节点N放在CLOSED表中, 并冠以顺序编号n。步4 若目标节点Sg= N,则搜索成功, 结束。 步5 若N不可扩展, 则转步2。步6 扩展N, 将其所有子节点配上指向N的指针依次放入OPEN表尾部, 转步2。宽度优先搜索例： 8数码问题九宫格中有8个数码，其中只有一个空格规则是一次只能把一个数码移动到空的格子中要求从一个初始状态移动到一个目标状态 宽度优先搜索宽度优先搜索优点完备性：如果问题有解，广度优先搜索总能够在有限步内找到目标节点最优性：在不考虑路径耗散的前提下，广度优先搜索总能够找到最浅的目标节点缺点：遍历各个节点，搜索效率差，消耗大量内存和时间宽度优先搜索的拓展代价树宽度搜索代价树宽度搜索（代价一致搜索）对于任意单步路径耗散都是最优的搜索策略其基本思想是优先扩展路径耗散最小的节点对于任意节点n，用f(n)来表示n到初始节点的路径耗散，即代价代价树宽度搜索例： 旅行商问题设A、B、C、D、E五个城市，旅行者从A出发，到达城市E，旅行费用如图所示，走怎样的路线费用最小？要求画出代价树、OPEN表和CLOSED表深度优先搜索深度优先搜索总是先扩展搜索树的当前边缘中最深的节点一种最原始的仿生学算法，来源于爬虫在树枝的搜索过程深度优先搜索深度优先搜索算法：步1 把初始节点S0放入OPEN表中。步2 若OPEN表为空, 则搜索失败, 退出。 步3 取OPEN表中前面第一个节点N放入CLOSED表中,并冠以顺序编号n。步4 若目标节点Sg=N, 则搜索成功,结束。 步5 若N不可扩展, 则转步2。步6 扩展N, 将其所有子节点配上指向N的返回指针依次放入OPEN表的首部, 转步2。深度优先搜索例：传教士和野人问题有3个传教士和3个野人过河只有一条能装下两个人的船在河的任何一方或者船上，如果野人的人数大于传教士的人数，那么传教士就会有危险. 要求安全渡河深度优先搜索分析：由于传教士与野人的总数目是一常数, 所以只要表示出河的某一岸上的情况就可以了另外还需要表示出船的位置因此用一个三元组(M, C, B), 来表示系统状态M表示河左岸传教士的人数C表示河左岸野人的人数B表示船的位置，1表示船在左岸，0表示船在右岸于是，初始状态为 目标状态为深度优先搜索深度优先搜索优点：对内存需求比较少，如果一个节点的全部后代都被完全探索过，那么这个节点和它的全部后继都可以从内存(open表和closed表)中删掉了缺点：不完备，也不最优回溯搜索策略回溯策略属于深度优先搜索的一种变形与深度优先搜索的区别：扩展一个节点时，每次只产生一个后继节点，而不是全部后继回溯策略只保存单一的解路径，占用内存空间很少，只需要一张表即可完成搜索回溯搜索策略例：四皇后问题在×方格的棋盘内，放置四个皇后使任意两个皇后不在同一行、同一列、同一对角线（斜线）上要求：找出所有的摆法回溯搜索策略状态描述：单个皇后位置的描述： 用(i,j)表示皇后在第i行j列系统状态的描述 四个皇后(i1,j1), (i2,j2), (i3,j3), (i4,j4)深度优先搜索的拓展深度有限搜索深度有限搜索预先设定一个搜索深度l，用以解决搜索树无边界的问题搜索过程中认为深度为l的节点没有后继节点，必须回溯缺点：增加了算法的不完备性双向搜索双向搜索同时进行两个搜索，可以采用任意搜索方法一个从初始状态向前搜索另一个从目标状态向后搜索当两个搜索在某个节点相遇时，搜索成功无信息搜索的讨论算法评判完备性是否一定能找到目标节点最优性搜索得到的解是否最优解时间复杂度算法的时间需求空间复杂度算法对计算机内存的需求无信息搜索的讨论重复状态扩展一个节点时，新生成的节点已经在open表或者closed表中存在了，这种情况称为重复状态有些情况下，重复状态会导致搜索失败；有些情况下，重复状态可以保留，但是会带来额外的计算资源的消耗因此，一般期望尽可能避免重复状态这时，有可能出现节点指针重新定向的情况无信息搜索的讨论问题的形式化描述状态描述 用数学方法定义系统状态初始状态、目标状态行动规则 产生后继节点目标测试判断当前节点是否就是目标节点路径耗散为每一条搜索路径定义数值化的消耗值无信息搜索的讨论状态描述八数码问题3X3的二维数组行动规则假设rij=0,则它跟相邻元素可以互换无信息搜索的讨论状态描述4皇后问题状态：在棋盘上任意放置1-4个皇后，每一种放置都是一个状态状态描述：逐一给出各个皇后的放置位置行动规则：增加一个皇后到棋盘上的任何空格无信息搜索的讨论状态描述四色问题，又称四色猜想，世界近代三大数学难题之一要求：只用四种颜色对平面地图染色，要求每两个相同区域不能染成相同颜色1976年美国数学家阿佩尔（K.Appel）与哈肯（W.Haken）宣告借助电子计算机获得了四色定理的证明，又为用计算机证明数学定理开拓了前景 无信息搜索的讨论四色问题的状态描述若干地区，四种颜色状态：对任意地区的进行染色，任意染色结果都是一种状态状态描述：用sk表示第k个地区的染色，逐一列出所有地区的染色就是系统的状态描述行动规则：给一个没有染色的地区染色无信息搜索的讨论吸尘器的世界只有两个房间A和B每个房间有可能有灰尘也可能没有吸尘器可以在两个房间里移动如果有灰尘，则吸取；否则移动到另一个房间无信息搜索的讨论课堂练习自动抓药系统三个勺子，容量分别为8克、5克和2克可以从药箱把勺子装满或倒空，也可以从一个勺子倒进另一个勺子目标是从药箱抓1克药给出状态描述、初始状态、目标状态以及行动规则启发式搜索启发式搜索，也称为有信息搜索，借助问题的特定知识来帮助选择搜索方向在搜索过程中对待扩展的每一个节点进行评估，得到最好的位置，再从这个位置进行搜索直到目标。启发式搜索的目的是省略大量无谓的搜索路径，提到效率。在启发式搜索中，对节点的评价是十分重要的，评价函数是搜索成败的关键。 启发式搜索评价函数，也称为启发函数提供问题的启发性信息，按其用途划分，可分为以下三类：用于扩展节点的选择，即用于决定应先扩展哪一个节点，以免盲目扩展用于生成节点的选择，即用于决定应生成哪些后续节点，以免盲目地生成过多无用节点用于删除节点的选择，即用于决定应删除哪些无用节点，以免造成进一步的时空浪费启发式搜索一个节点n的评价函数的构造通常由两部分构成从初始节点到当前节点n的路径耗散从当前节点n到目标节点的期望耗散即：评价函数可表示为：这两部分里， 通常是比较明确的，容易得到而 难以构造，也没有固定的模式，需要根据具体问题分析启发式搜索贪婪搜索优先扩展距离目标最近的节点例：西安到上海的贪婪搜索启发式搜索贪婪搜索的启发函数只考虑待扩展节点到目标节点的期望耗散，而不考虑初始节点到待扩展节点的实际耗散贪婪搜索类似于深度优先搜索，总是先沿着一条枝搜索下去贪婪搜索既不是完备的，也不是最优的启发式搜索A算法代价树宽度搜索只考虑初始节点到待扩展节点的路径耗散贪婪搜索只考虑待扩展节点到目标节点的期望耗散A算法既考虑待扩展节点到目标节点的期望耗散，又考虑初始节点到待扩展节点的路径耗散启发式搜索A搜索算法的步骤步1 把初始节点So放入OPEN表。步2 若OPEN表为空, 则搜索失败, 退出。 步3 移出OPEN表中第一个节点N放入CLOSED表中, 并冠以顺序编号n。步4 若目标节点Sg=N, 则搜索成功, 结束。 步5 若N不可扩展, 则转步2。步6 扩展N,生成一组子节点,并利用评价函数为子节点估值，对这组子节点做如下处理： (1) 处理重复状态(2)对其余子节点配上指向N的返回指针后放入OPEN表中, 并对OPEN表按f(n)值以升序排序, 转步2。启发式搜索A 算法举例八数码问题确定 用节点深度，也就是初始节点到待扩展节点移动的数码的步数确定 不在位数码的总数启发式搜索A算法的表现极大地依赖于评价函数，特别是h(n),即：从节点n到目标节点最佳路径的估计耗散 假定h*(n)表示节点n到目标节点最佳路径的实际耗散 如果 h(n)> h*(n) , 搜索的节点数少，搜索范围小，效率高，但不能保证得到最优解。如果h(n)<= h*(n) ，这种情况下，搜索的节点数多，搜索范围大，效率低，但能得到最优解启发式搜索满足h(n)<= h*(n) 条件的A搜索，称为A* (A-star)搜索A* 搜索中，h(n)越接近h*(n) ，搜索效率越高宽度优先算法可以看作A*算法的特例，即：g(n)是节点所在的层数，h(n)=0 代价树宽度搜索也可以看作A*算法的特例，即：g(n)是节点n的实际路径耗散，h(n)=0跟前两个算法一样，A*算法也具有完备性和最优性启发式搜索例：八数码问题启发函数1：h1(n)=不在位的数码的总数问题1：图中S0状态h(S0)是什么， h*(S0) 又是什么问题2：这个启发函数是否一定满足h(n)<= h*(n) 问题3：对于八数码问题，还能提出其他的启发函数吗？启发式搜索例：八数码问题启发函数2： h2(n)=所有数码到目标位置的距离和（曼哈顿距离）问题1：图中S0状态h(S0)是什么， h*(S0) 又是什么问题2：这个启发函数是否一定满足h(n)<= h*(n) 启发式搜索A*算法当h(n)<= h*(n) 时，同时满足完备性和最优性要求h(n)越接近于真实耗散h*(n)，算法的搜索效率越高，对内存和时间的需求越小如果满足h(n)= h*(n)，是最完美的A*算法h(n)的设计是A*算法的核心，也是最困难的地方启发式搜索启发式函数的构造思想之一松弛法 放松行动规则约束的思想方法八数码问题： 行动规则：如果以下条件成立，则一个数码可以从A方格移动到B方格 1、 B为空 2、 A与B相邻 放松约束1：A可以移动到B 放松约束2：如果A与B相邻，则A可以移动到B 放松约束3：如果B为空，则A可