下载文档原格式
人工智能导论丁世飞第三版答案1．什么是推理，请从多种角度阐述推理？(1)推理：按照某种策略从已有事实和知识推出结论的过程。
(2)正向推理正向推理（事实驱动推理）是由已知事实出发向结论方向的推理。
基本思想是：系统根据用户提供的初始事实，在知识库中搜索能与之匹配的规则即当前可用的规则，构成可适用的规则集RS，然后按某种冲突解决策略从RS 中选择一条知识进行推理，并将推出的结论作为中间结果加入到数据库DB 中作为下一步推理的事实，在此之后，再在知识库中选择可适用的知识进行推理，如此重复进行这一过程，直到得出最终结论或者知识库中没有可适用的知识为止。
正向推理简单、易实现，但目的性不强，效率低。
需要用启发性知识解除冲突并控制中间结果的选取，其中包括必要的回溯。
由于不能反推，系统的解释功能受到影响。
(3)反向推理反向推理是以某个假设目标作为出发点的一种推理，又称为目标驱动推理或逆向推理。
反向推理的基本思想是：首先提出一个假设目标，然后由此出发，进一步寻找支持该假设的证据，若所需的证据都能找到，则该假设成立，推理成功；若无法找到支持该假设的所有证据，则说明此假设不成立，需要另作新的假设。
与正向推理相比，反向推理的主要优点是不必使用与目标无关的知识，目的性强，同时它还有利于向用户提供解释。
反向推理的缺点是在选择初始目标时具有很大的盲目性，若假设不正确，就有可能要多次提出假设，影响了系统的效率。
反向推理比较适合结论单一或直接提出结论要求证实的系统。
(4)推理方式分类演绎推理、归纳推理、默认推理确定性推理、不精确推理单调推理、非单调推理启发式推理、非启发式推理2．什么是逆向推理？它的基本过程是什么？解：逆向推理是以某个假设目标作为出发点的推理方法过程：（1）将问题的初始证据和要求证的目标（称为假设）分别放入综合数据库和假设集；（2）从假设集中选出一个假设，检查该假设是否在综合数据库中，若在，则该假设成立。
此时，若假设集为空，则成功退出。
习题11.1什么是智能？什么是人工智能？解：略。
1.2什么是图灵测试？它有什么重要特征？解：略。
1.3一台机器要通过图灵测试，它必须具备哪些能力？解：自然语言处理: 实现用自然语言与计算机进行交流。
知识表示: 存储它知道的或听到的、看到的。
自动推理：能根据存储的信息回答问题，并提出新的结论。
机器学习：能适应新的环境，并能检测和推断新的模式。
计算机视觉：可以感知物体。
机器人技术：可以操纵和移动物体。
1.4人工智能的发展经历哪几个阶段？解：人工智能的产生和发展过程，可大致分为孕育期(20世纪50年代中期以前)、形成及第一个兴旺期(20世纪50年代中期－60年代中期)、萧条波折期(20世纪60年代中期－70年代中期)、第二个兴旺期(20世纪70年代中期－80年代中期)、稳步增长期(20世纪80年代中期－至今)。
1.5人工智能研究有哪几个主要学派？其特点是什么？解：略。
1.6人工智能的主要研究内容和应用领域是什么？解：略。
习题22.1什么是知识表示？知识表示有哪些要求？解：略。
2.2简述一阶谓词逻辑表示法表示知识的一般步骤。
解：略。
2.3简述一阶谓词逻辑表示法的优缺点。
解：略。
2.4 简述产生式系统的基本组成部分以及它们之间的关系。
解：略。
2.5什么是语义网络？它的基本语义关系哪些？解：略。
2.6 什么是框架？框架表示法的特点是什么？解：略。
2.7 什么是脚本？脚本一般由几部分构成？解：略。
2.8 面向对象表示法中封装和继承各有什么含义？解：略。
2.9 设有一些语句，请用相应的谓词公式分别把他们表示出来。
(1) 有的人喜欢梅花，有的人喜欢菊花，有的既喜欢梅花又喜欢菊花。
解：(∃x)(Human(x)∧Like(x, Club(x)))(∃x)(Human(x)∧Like(x, Mum(x)))(∃x)(Human(x)∧Like(x, club(x))∧Like(x, Mum(x)))(2) 他每天下午都去玩足球；解：(∀x) (Day(x)→PlayFootball(Ta))(3) 兰州市的夏天既干燥又炎热；解：Dry(Summer(Lanzhou))∧Hot(Summer(Lanzhou))(4) 所有人都有饭吃；解：(∀x) (Human(x)→Eat(x))(5) 喜欢玩篮球的人必喜欢玩排球；解：(∀x) (Human(x)∧Like(x, basketball))→Like(x, volleyball))(6) 要想出国留学，必须通过外语考试；解：Abroad(x)→Pass(x)(7) 每个学生都要参加考试解：(∀x) (Student(x)→Test(x))(8) 任何整数或是正的或是负的解：(∀x) (Integer(x)→PositiveNum (x)∨NegativeNum (x))2.10 房内有一只猴子、一个箱子，天花板上挂了一串香蕉，其位置关系如图2.20所示，猴子为了拿到香蕉，它必须把箱子推到香蕉下面，然后再爬到箱子上。
人工智能技术导论第三版教学大纲课程简介本门课程是一门介绍人工智能技术基础的入门课程，主要涵盖人工智能的概念、技术、算法、应用等方面。
通过该课程的学习，学生将掌握人工智能的基本理论、方法和应用，培养人工智能技术的思想和方法，为深入研究人工智能领域奠定基础。
课程目标1.了解人工智能的基本概念，了解人工智能的历史和发展；2.了解人工智能的技术体系和持续发展趋势；3.掌握人工智能的算法和函数，学习人工智能的数学基础；4.理解人工智能在现实生活中的应用和可行性；5.培养独立思考，为进一步研究人工智能技术奠定基础。
教学内容第一章人工智能技术概述•人工智能的定义、目标和基本原理；•人工智能的历史和发展。
第二章人工智能技术体系•人工智能技术体系的框架和组成部分；•人工智能技术体系的分类和应用领域。
第三章人工智能数学基础•数据结构和算法；•数学基础，包括线性代数和概率统计。
第四章人工智能算法和函数•人工智能算法：遗传和进化算法、神经网络、模糊系统、支持向量机等；•人工智能函数：评估、归一化、压缩、规范化等。
第五章人工智能应用•人工智能在游戏、机器人、生产和自动化控制等方面的应用；•人工智能在医学、金融、法律和教育等领域的应用。
学习方法•授课和讲解之间交替，注重图示和例子；•课后推荐学习资料，包括论文、书籍、课程和视频；•课题研究和实践纪要。
评估方式•平时成绩：30%，出席情况和课堂表现；•期中考试：30%，考察理论与其应用；•期末考试：40%，综合性考试。
参考资料1.《人工智能导论》，彼得·诺弗斯（Peter Norvig）、斯图尔特·罗素（Stuart Russell）著，唐娟、杨洋译，人民邮电出版社，2004年。
2.《人工智能多种技术和应用》（第2版），叶蓉、李新民等编著，高等教育出版社，2009年。
3.《人工智能基础及其进展》，赵瑞曼、叶汉君著，人民邮电出版社，2015年。
4.《机器学习》，周志华著，清华大学出版社，2016年。
人工智能第三版课件第3章搜索的基本策略搜索引擎是当今互联网时代不可或缺的工具，而人工智能技术在搜索引擎中起着举足轻重的作用。
本文将介绍《人工智能第三版课件》中第3章的内容，讨论搜索的基本策略。
基于这些策略，搜索引擎能够更加高效、准确地满足用户的信息需求。
1. 初始搜索空间在进行搜索之前，需要建立一个初始的搜索空间，即包含可能相关信息的一组文档或网页。
这个搜索空间的建立可以通过爬虫程序和抓取技术来收集网络上的信息，并将其存储在搜索引擎的数据库中。
2. 关键词匹配搜索引擎通过用户输入的关键词与搜索空间中的文档进行匹配，以找到与用户需求相关的内容。
关键词匹配可以使用词频、倒排索引等算法来实现。
其中，词频是指对于一个给定的关键词，在搜索空间中出现的频率；倒排索引则是一种将关键词与对应的文档进行关联的索引结构。
3. 分析用户意图搜索引擎还需要通过分析用户的搜索历史、点击行为等数据来了解用户的真实意图。
这可以通过机器学习算法来实现，例如基于用户行为的推荐系统。
通过了解用户的意图，搜索引擎可以更加准确地推荐相关内容。
4. 搜索结果排序搜索引擎会对匹配到的文档进行排序，以便将最相关的结果显示在前面。
排序算法通常通过计算文档与用户查询的相似度来实现。
相似度计算可以使用向量空间模型、BM25等算法。
5. 反馈与迭代搜索引擎不断根据用户的反馈进行迭代，以提供更好的搜索结果。
用户的反馈可以包括点击率、停留时间等指标，这些指标可以通过机器学习算法来进行分析和预测。
搜索引擎可以根据用户的反馈来调整排序算法，从而不断改进搜索结果的准确性和相关性。
综上所述，搜索引擎的基本策略包括建立初始搜索空间、关键词匹配、分析用户意图、搜索结果排序以及反馈与迭代。
这些策略通过人工智能技术的应用，使得搜索引擎能够更加智能化地满足用户的信息需求。
未来随着人工智能技术的不断发展，搜索引擎将会变得更加准确、个性化，并为用户提供更多智能化的服务。
人工智能导论第三版答案【篇一：人工智能-课后作业】人工智能人工智能就是用人工的方法在机器（计算机）上实现的智能，或称机器智能第二章：p515.（1）有的人喜欢打篮球，有的人喜欢踢足球，有的人既喜欢打篮球又喜欢踢足球。
定义谓词：like(x,y):x喜欢y。
play(x,y):x打（踢）y。
man(x):x是人。
定义个体域：basketball，soccer。
（?x)(man(x) → like(x,play(x,basketball))) ∨（?y)(man(y) → like(y,play(y,soccer))) ∨（ ?z)(man(z)→like(z,play(z,basketball)) ∧ like(z,play(z,soccer)) (2)并不是每个人都喜欢花。
定义谓词：like（x,y)：x喜欢y。
p(x)：x是人定义个体词：flower?(?x)(p(x) → like(x,flower)) (3)欲穷千里目，更上一层楼。
定义谓词：s(x)：x想要看到千里远的地方。
h(x):x要更上一层楼。
（?x)(s(x) → h(x))6. 产生式通常用于表示具有因果关系的知识，其基本形式是：p→q 或者 ifpthenq[else s]其中，p是前件，用于指出该产生式是否可用的条件。
q是一组结论或者操作，用于指出当前提p满足时，应该得出的结论或者应该执行的操作。
区别：蕴含式只能表示精确知识；而产生式不仅可以表示精确知识，还可以表示不精确知识。
产生式中前提条件的匹配可以是精确的，也可以是非精确的；而谓词逻辑蕴含式总要求精确匹配。
7. 一个产生式系统一般由三部分组成：规则集、全局数据库、控制策略。
步骤：1）初始化全局数据库，把问题的初始已知事实送入全局数据库中2）若规则库中存在尚未使用的规则，而且它的前提可与全局数据库中的已知事实匹配，则转3），若不存在则转5）3）执行当前选中的规则，并对该规则做标记，把该规则执行后得到的结论送入全局数据库中。
人工智能基础第三版课程设计一、课程介绍本课程旨在介绍人工智能的基本概念及其应用，包含人工智能的起源、发展历程、基础理论及其实践应用。
本课程将涵盖人工智能的基础理论，如机器学习、自然语言处理、计算机视觉等，并使用Python等编程语言进行实践演练。
二、教学目标1.了解人工智能的概念、基础理论、应用和发展历程；2.掌握机器学习、自然语言处理、计算机视觉等基础理论；3.熟悉使用Python等编程语言进行实践；4.能够通过实践案例，了解人工智能的应用场景和应用前景。
三、教学大纲第一章人工智能概述•人工智能概述•人工智能的应用场景和前景第二章机器学习基础•机器学习基础•KNN算法•决策树算法•随机森林算法•SVM算法•神经网络算法第三章自然语言处理•自然语言处理•中文分词•词性标注•命名实体识别•情感分析第四章计算机视觉•计算机视觉•图像处理基础•物体检测•人脸识别第五章人工智能的应用•人工智能的应用案例•智能客服•无人驾驶技术•人工智能医疗四、教学方法本课程采用讲授、案例分析、实践演练等教学方法。
授课将结合案例分析，使学生了解实际应用场景和应用前景。
实践演练中，学生将亲自实践并完成相关项目，以提高学习效果。
五、考核方式课程终评：期末考试（占50%）+实践项目（占40%）+课堂实训（占10%）六、参考教材•《Python机器学习基础教程》•《自然语言处理导论》•《OpenCV计算机视觉》七、教学团队主讲教师：张老师助教：李同学、王同学八、教学资源本课程教学资源将通过学校教务系统、在线资源库等渠道提供。
人工智能技术导论
(IntroductiontoArtificia1Inte11igenceTechno1ogy)
总学时：48学时理论：48学时实验（上机、实习等）：0学时
学分：3
课程主要内容：
《人工智能技术导论》是计算机科学与技术专业的一门专业必修课程。
本课程主要内容包括人工智能的基本概念，人工智能技术的发展及应用领域，PRO1OG语言及基本程序设计，状态图搜索的基本概念及基本算法（启发式搜索、加权状态图搜索和A算法、A*算法等），遗传算法及应用，确定性及不确定性知识表示方法，产生式系统，确定性推理与不确定性推理，机器学习及专家系统等。
先修课程：
《离散数据》、《程序设计语言》、《数据结构》等。
适用专业：
计算机科学与技术专业
教材：
廉师友.《人工智能技术导论》（第三版）.西安：西安电子科技大学出版社，2007教学参考书：
[1]蔡自兴，徐光佑.《人工智能及其应用》.北京：清华大学出版社，1996
[2]沟口理一郎，石田亨编，卢伯英译.《人工智能》.北京：科学出版社，2003
[3]王万森.《人工智能原理及其应用》.北京：电子工业出版社，2000
[4]邵军力.《人工智能基础》.北京：电子工业出版社，2000
[5]田盛丰.《人工智能原理与应用：专家系统、机器学习、面向对象的方法》.北京:北京理
工大学出版社，1993。
人工智能》教学大纲2．掌握Prolog语言的基本语法和常用操作；3．能够编写简单的Prolog程序，并能够运行和调试；4．了解Prolog语言在人工智能中的应用。
第三章搜索算法基本内容和要求：1．掌握深度优先搜索、广度优先搜索、启发式搜索等搜索算法的基本思想和实现方法；2．能够应用搜索算法解决一些典型问题；3．了解搜索算法在人工智能中的应用。
第四章知识表示与推理基本内容和要求：1．掌握命题逻辑、一阶逻辑等知识表示方法；2．了解基于规则、框架、语义网络等知识表示方法；3．掌握归结方法、前向推理、后向推理等推理方法；4．能够应用知识表示与推理解决一些典型问题。
第五章不确定性推理基本内容和要求：1．了解不确定性推理的基本概念和方法；2．掌握贝叶斯定理及其应用；3．掌握条件概率、独立性、条件独立性等概念；4．能够应用不确定性推理解决一些典型问题，如垃圾邮件过滤等。
五、教材和参考书目1）主教材：Stuart Russell。
Peter Norvig。
Artificial Intelligence: A Modern Approach。
3rd n。
Prentice Hall。
2009.2）参考书目：___。
机器研究。
___。
2016.___。
统计研究方法。
___。
2012.___。
___。
2017.六、教学进度安排第一周人工智能概述第二周逻辑程序设计语言Prolog第三周搜索算法第四周知识表示与推理第五周不确定性推理第六周期中考试第七周至第十周课程实验第十一周至第十三周课程实验第十四周课程总结与复第十五周期末考试一实验（实训）内容产生式系统实验学时分配4目的与要求：熟悉和掌握产生式系统的运行机制，掌握基于规则推理的基本方法。
实验（实训）内容：主要包括产生式系统的正、反向推理、基于逻辑的搜索等10余个相关演示性、验证性和开发性设计实验。
二实验（实训）内容搜索策略实验学时分配4目的与要求：熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A*算法求解N数码难题，理解求解流程和搜索顺序。
人工智能科学第三版试读在当今科技飞速发展的时代，人工智能（AI）无疑是最引人瞩目的领域之一。
当我们拿到《人工智能科学》第三版时，仿佛打开了一扇通往未来的智慧之门。
这本书的开篇就以通俗易懂的方式为我们阐述了人工智能的基本概念。
它并非那种让人望而生畏的高深理论堆砌，而是通过生动的例子和简洁的语言，让我们对人工智能的定义和范畴有了清晰的认识。
比如说，书中提到了日常生活中常见的智能语音助手，通过解释其背后的工作原理，让我们一下子就明白了人工智能是如何融入我们的生活，并为我们提供便捷服务的。
随着阅读的深入，我们会发现第三版在内容的深度和广度上都有了显著的提升。
在知识体系的构建上，它不仅涵盖了传统的机器学习算法，如决策树、聚类分析等，还紧跟时代步伐，引入了深度学习、强化学习等前沿技术。
对于这些技术的讲解，作者并没有陷入复杂的数学公式和理论推导，而是通过实际的应用案例，让我们直观地感受到它们的强大威力。
以深度学习为例，书中列举了图像识别领域的重大突破。
过去，让计算机准确识别各种图像是一个巨大的挑战，但通过深度学习算法，计算机能够像人类一样准确地识别出物体、场景甚至是细微的表情变化。
这不仅让我们惊叹于技术的进步，更让我们对人工智能的未来充满了无限的遐想。
在探讨人工智能的应用方面，第三版可谓是面面俱到。
从医疗保健领域的疾病预测、智能诊断，到金融行业的风险评估、欺诈检测，再到交通领域的自动驾驶、智能交通管理，人工智能的触角已经深入到了我们生活的方方面面。
每一个应用案例都配有详细的分析和实际的数据，让我们能够清楚地看到人工智能是如何实实在在地改变着我们的世界。
值得一提的是，书中还专门用了一个章节来讨论人工智能带来的伦理和社会问题。
随着人工智能技术的广泛应用，隐私保护、就业结构调整、算法偏见等问题日益凸显。
作者以客观公正的态度，引导我们思考这些问题的解决方案，提醒我们在追求技术进步的同时，不能忽视其可能带来的负面影响。
人工智能技术导论（第三版）第3章1、何为状态图和与或图？图搜索与问题求解有什么关系？解：按连接同一节点的各边间的逻辑关系划分，图可以分为状态图和与或图两大类。
其中状态图是描述问题的有向图。
在状态图中寻找目标或路径的基本方法就是搜索。
2、综述图搜索的方式和策略。
解：图搜索的方式有：树式搜索，线式搜索。
其策略是：盲目搜索，对树式和不回溯的线式是穷举方式，对回溯的线式是随机碰撞式。
启发式搜索，利用“启发性信息”引导的搜索。
3、什么是问题的解？什么是最优解？解：能够解决问题的方法或具体做法成为这个问题的解。
其中最好的解决方法成为最优解。
4、什么是与或树？什么是可解节点？什么是解树？解：与或树:一棵树中的弧线表示所连树枝为“与”关系,不带弧线的树枝为或关系。
这棵树中既有与关系又有或关系，因此被称为与或树。
可解节点:解树实际上是由可解节点形成的一棵子树,这棵子树的根为初始节点，叶为终止节点，且这棵子树一定是与树。
解树:满足下列条件的节点为可解节点。
①终止节点是可解节点；②一个与节点可解，当且仅当其子节点全都可解；③一个或节点可解，只要其子节点至少有一个可解。
5、设有三只琴键开关一字排开，初始状态为“关、开、关”，问连接三次后是否会出现“开、开、开”或“关、关、关”的状态？要求每次必须按下一个开关，而且只能按一个开关。
请画出状态空间图。
注：琴键开关有这样的特点，若第一次按下时它为“开”，则第二次按下时它就变成了“关”。
解：设0为关，1为开6、有一农夫带一只狼、一只羊和一筐菜欲从河的左岸乘船到右岸，但受下列条件限制：1）船太小，农夫每次只能带一样东西过河。
2）如果没农夫看管，则狼要吃羊，羊要吃菜。
请设计一个过桥方案，使得农夫、狼、羊、菜都不受损失地过河。
画出相应状态空间图。
提示：（1）用四元组（农夫、狼、羊、菜）表示状态，其中每个元素都可为0或1，用0表示在左岸，用1表示在右岸。
（2）把每次过河的一次安排作为一个算符，每次过河都必须有农夫，因为只有他可以划船。
解：设A=（A1，A2，A3，A4）为状态A1：表示农夫的位置，=0：未过河、=1：已过河A2：表示狼的位置，=0：未过河、=1：已过河A3：表示菜的位置，=0：未过河、=1：已过河A4：表示羊的位置，=0：未过河、=1：已过河具体的过河方案为：（1）农夫、羊从左岸-》右岸，留下羊-》一人回到左岸（2）农夫、菜从左岸-》右岸，留下菜-》农夫、羊回到左岸（3）农夫、狼从左岸-》右岸，留下菜、狼-》农夫一人回到左岸（4）农夫、羊从左岸-》右岸相应的状态空间图为：（0，0，0，0） (1，0，0，1）（0，0，0，1）（1，0，1，1）（0，0，1，0）（1，1，1，0）（0，1，1，0）（1，1，1，1）其中（0，0，0，0）为初始状态，（1，1，1，1）为终止状态。
7、请阐述状态空间的一般搜索过程。
OPEN表与CLOSED表的作用是什么？解：OPEN表：用于存放刚生成的节点；CLOSE表：用于存放将要扩展或已扩展的节点8、广度优先搜索与深度优先搜索各有什么特点？解：（1）广度优先搜索就是始终先在同一级节点中考查,只有当同一级节点考查完之后,才考查下一级节点。
或者说，是以初始节点为根节点，向下逐级扩展搜索树。
所以,广度优先策略的搜索树是自顶向下一层一层逐渐生成的。
（2）深度优先搜索就是在搜索树的每一层始终先只扩展一个子节点,不断地向纵深前进,直到不能再前进（到达叶子节点或受到深度限制）时，才从当前节点返回到上一级节点，沿另一方向又继续前进。
这种方法的搜索树是从树根开始一枝一枝逐渐形成的。
深度优先搜索亦称为纵向搜索。
由于一个有解的问题树可能含有无穷分枝，深度优先搜索如果误入无穷分枝(即深度无限)，则不可能找到目标节点。
所以，深度优先搜索策略是不完备的。
另外，应用此策略得到的解不一定是最佳解(最短路径)。
广度优先搜索与深度优先搜索都属于盲目搜索。
9、图3-32是五大城市间的交通示意图，边上的数字是两城市间的距离。
用图搜索技术编写程序，求解以下问题：（1）任找一条西安到北京的旅行路线，并给出其距离。
（2）找一条从西安到北京，必须经途上海的路径。
（3）找一条从西安到北京，必须经途上海，但不能去昆明的路径。
解：domainsp=stringd=integerpp=p*predicatesroad(p,p,d)path(p,p,pp,d)member(p,pp)clausespath(X,Y,L,D):-road(X,Y,D),L=[X|[Y]].path(X,Y,L,D):-road(X,Z,D1),%从当前点向前走到下一点Znot(member(Z,L)),path(Z,Y,［Z|L］,D2),D=D1+D2.%再找Z到出口Y的路径member(X,［X|_］).member(X,［_|T］)if member(X,T).road(A,B,D):-road(B,A,D). %因为没向图road(“西安”,”北京”,1165). road(“西安”,”上海”,1511).road(“西安”,“广州” ,2129). road(“西安”,”昆明”,1942).r oad(“昆明”,”北京”,3179). road(“昆明”,”上海”,2677).road(“昆明”,“广州”,2216). road(“北京”,”广州”,2510).road(“上海”,”北京”,1462). road(“广州”,“上海”,1511).（1）path(“西安”,”北京”,L,D),write(L,D).（2）path(“西安”,”北京”,L,D),member(“上海”,L),write(L,D).（3）path(“西安”,”北京”,L,D),member(“上海”,L),not(member(“昆明”,L)), write(L,D).10、何谓估价函数？在估价函数中，g(x)和h(x)各起什么作用？解：估价函数的任务是估计待搜索节点的重要程度，给它们排定次序。
g(n)是起始点到达n的实际路径代价，h(n)就是n到达目标点最短路径的启发函数。
11、局部择优搜索与全局择优搜索的相同处与区别是什么？解：（1）相同：利用启发函数制导的一种启发式搜索方法。
在OPEN表中保留所有已生成而未考察的节点，并用启发函数h（x）对它们全部进行估价，从中选出最优节点进行扩展，而不管这个节点出现在搜索树的什么地方。
（2）区别：局部择优搜索扩展节点N后仅对N的子节点按启发函数值大小以升序排序，再将它们依次放入OPEN表的首部。
12、设有如图3-24所示的一棵与或树，请指出解树；并分别按和代价及最大代价求解树代价；然后，指出最优解树。
解：按和代价的解树：左树：G(D)=4、G(A)=7、G(S0)=12右树：G(B)=8、G(S0)=15按最大代价的解树：左树：G(D)=2、G(A)=6、G(S0)=11右树：G(B)=8、G(S0)=15两种方法均说明右树是最优解树。
14、传教士和野人问题。
有三个传教士和三个野人一起来到河边准备渡河，河边有一条空船，且传教士和野人都会划船，但每次最多可供两人乘渡。
河的任何一岸以及船上一旦出现野人人数超过传教士人数，野人就会把传教士吃掉。
为安全地渡河，传教士应如何规划渡河方案？试给出该问题的状态图表示，并用PROLOG语言编程求解之。
若传教士和野人的数目均为五人，渡船至多可乘三人，请定义一个启发函数，并给出相应的搜索树。
解：（1）设计该问题的状态。
例如：((左岸牧师数，左岸野人数),(右岸牧师数，右岸野人数),船的位置)。
（2）定义目标状态。
这里是：((0,0),(3,3),1)（3）描述可能的动作。
船上所能够载人的状态就是可能的操作。
用谓词move/2表示。
（4）判断合法状态（5）深度优先搜索三个传教士和三个野人的示例程序如下：move(1,0).move(0,1).move(0,2).move(2,0).move(1,1).legal((X,Y,_)):-legal1(X),legal1(Y).legal1((X,Y)):-X=:=0,Y>=0,!.legal1((X,Y)):-Y=:=0,X>=0,!.legal1((X,Y)):-X>=Y,X>=0,Y>=0.update((X,Y,0),Move,Statu1):-(A,B)=X,(C,D)=Y,(E,F)=Move,C1 is C+E,D1 is D+F,A1 is A-E,B1 is B-F,Statu1=((A1,B1),(C1,D1),1).update((X,Y,1),Move,Statu1):-(A,B)=X,(C,D)=Y,(E,F)=Move,C1 is C-E,D1 is D-F,A1 is A+E,B1 is B+F,Statu1=((A1,B1),(C1,D1),0). connect(Statu,Statu1):- move(X,Y),update(Statu,(X,Y),Statu1), legal(Statu1).findroad(X,X,L,L):-write(L). findroad(X,Y,L,L1):- connect(X,Z),not(member(Z,L)),findroad(Z,Y,[Z|L],L1).。
