下载文档原格式
⼈⼯智能练习题答案1、什么是⼈⼯智能？⼈⼯智能有哪些研究领域？何时创建该学科，创始⼈是谁？（1）AI（Artificial Intelligence）是利⽤计算机技术、传感器技术、⾃动控制技术、仿⽣技术、电⼦技术以及其他技术仿制⼈类智能机制的学科（或技术），再具体地讲就是利⽤这些技术仿制出⼀些具有⼈类智慧（能）特点的机器或系统（2）⼈⼯智能的研究领域主要有专家系统、机器学习、模式识别、⾃然语⾔理解、⾃动定⼒证明、⾃动程序设计、机器⼈学、博弈、智能决策⽀持系统、⼈⼯神经⽹络等（3）⼈⼯智能于1956年夏季，由麦卡锡，明斯基、洛切斯特、⾹农等发起创建2、产⽣式系统的由哪三部分组成？各部分的功能是什么？课本29页（1）产⽣式系统由综合数据库、产⽣式规则和控制系统三部分组成（2）综合数据库⽤于存放当前信息，包括初始事实和中间结果；产⽣式规则⽤于存放相关知识；控制系统⽤于规则的解释或执⾏程序。
3、设有三枚硬币，其初始状态为（反，正，反），允许每次翻转⼀个硬币（只翻⼀个硬币，必须翻⼀个硬币）。
必须连翻三次。
⽤知识的状态空间表⽰法求出到达状态（反，反，反）的通路。
画出状态空间图。
课本51页问题求解过程如下：（1）构建状态⽤数组表⽰的话，显然每⼀硬币需占⼀维空间，则⽤三维数组状态变量表⽰这个知识：Q=（q1 , q2 , q3）取q=0 表⽰钱币的正⾯; q=1 表⽰钱币的反⾯构成的问题状态空间显然为：Q0=（0，0，0），Q1=（0，0，1），Q2=（0，1，0）, Q3=（0，1，1），Q4=（1，0，0），Q5=（1，0，1），Q6=（1，1，0），Q7=（1，1，1）（2）引⼊操作f1：把q1翻⼀⾯。
f2：把q2翻⼀⾯。
f3：把q3翻⼀⾯。
显然：F={f1，f2，f3}⽬标状态：（找到的答案）Qg=（0，0，0）或（1，1，1）（3）画出状态图从状态图可知：从“反，正，反”（1，0,1）到“正，正，正”（0,0,0）没有解题路径；从“反，正，反”（1，0,1）到“反，反，反”（1,1,1）有⼏条解题路径f3 f2 f3,f1 f2 f1,…4、⼋数码问题：已知⼋数码的初始状态和⽬标状态如下：=>。
第三章知识的状态空间表示法1 课前思考：人类的思维过程，可以看作是一个搜索的过程。
某个方案所用的步骤是否最少？也就是说它是最优的吗？如果不是，如何才能找到最优的方案？在计算机上又如何实现这样的搜索？这些问题实际上就是本章我们要介绍的搜索问题。
2 学习目标：掌握回溯搜索算法、深度优先搜索算法、宽度优先搜索算法和A搜索算法，对典型问题，掌握启发式函数的定义方法。
3 学习指南：了解算法的每一个过程和细节问题，掌握一些重要的定理和结论，在有条件的情况下，程序实现每一个算法，求解一些典型的问题。
4 难重点：回溯搜索算法、算法及其性质、改进的Ａ＊算法。
5 知识点：本章所要的讨论的问题如下：有哪些常用的搜索算法。
问题有解时能否找到解。
找到的解是最佳的吗？什么情况下可以找到最佳解？求解的效率如何。
3.1 状态空间表示知识一、状态空间表示知识要点1．状态状态（State）用于描述叙述性知识的一组变量或数组，也可以说成是描述问题求解过程中任意时刻的数据结构。
通常表示成：Q={q1，q2，……，qn}当给每一个分量以确定的值时，就得到一个具体的状态，每一个状态都是一个结点（节点）。
实际上任何一种类型的数据结构都可以用来描述状态，只要它有利于问题求解，就可以选用。
2．操作（规则或算符）操作（Operator）是把问题从一种状态变成为另一种状态的手段。
当对一个问题状态使用某个可用操作时，它将引起该状态中某一些分量发生变化，从而使问题由一个具体状态变成另一个具体状态。
操作可以是一个机械步骤、一个运算、一条规则或一个过程。
操作可理解为状态集合上的一个函数，它描述了状态之间的关系。
通常可表示为：F={ f1 , f2,……… fm}3．状态空间状态空间（State Space）是由问题的全部及一切可用算符（操作）所构成的集合称为问题的状态空间。
用三元组表示为：（{Qs}，{F}，{Qg}）Qs：初始状态，Qg：目标状态，F：操作（或规则）。
状态空间表示法的要素
状态空间表示法是一种用于描述系统或问题的符号体系，它包含状态变量和操作符号。
该方法主要用于描述系统的状态以及状态之间的转换。
状态空间表示法的要素包括：
1.状态变量：表示系统状态的符号或数据，可以是物理量、状态描述符等。
2.操作符号：描述状态之间转换的操作符号，可以是函数、算子等。
3.初始状态集合：描述系统初始状态的状态集合。
4.目的状态集合：描述系统目标状态的状态集合。
5.状态转换路径：从初始状态集合到目的状态集合的路径，由操作符号连接各个状态变量。
6.操作序列：求解路径上的操作算子序列，对应于实际系统中的操作过程。
7.数据结构：用于描述状态变量的数据结构，可以是矩阵、向量、树、图等。
这些要素共同构成了状态空间表示法，可以用来描述和分析各种系统和问题。
（人工智能）人工智能基础考试大纲（人工智能）人工智能基础考试大纲人工智能基础（8017）考试大纲壹、课程性质和设置目的（一）课程性质和特点“人工智能”是21世纪计算机科学发展的主流，为了培养国家建设跨世纪的有用人才，于计算机专业本科开设《人工智能基础》课程是十分必要的。
《人工智能基础》是计算机专业本科的壹门必修课程，本课程中涉及的理论、原理、方法和技术有助于学生进壹步学习其他专业课程。
开设本课程的目的是培养学生软件开发的“智能”观念；掌握人工智能的基本理论、基本方法和基本技术；提高解决“智能”问题的能力，为今后的继续深造和智能系统研制，以及进行关联的工作打下人工智能方面的基础。
（二）本课程的基本要求（课程总目标）《人工智能基础》是理论性较强，涉及知识面较广，方法和技术较复杂的壹门学科。
通过对本课程的学习，学生应掌握人工智能的壹个问题和三大技术，即通用问题求解和知识表示技术、搜索技术、推理技术。
具体要求是：学生于较坚实打好的人工智能数学基础（数理逻辑、概率论、模糊理论、数值分析）上，能够利用这些数学手段对确定性和不确定性的知识完成推理；于理解Herbrand域概念和Horn 子句的基础上，应用Robinson归结原理进行定理证明；应掌握问题求解（GPS）的状态空间法，能应用几种主要的盲目搜索和启发式搜索算法（宽度优先、深度优先、有代价的搜索、A算法、A*算法、博弈数的极大—极小法、α―β剪枝技术）完成问题求解；且能熟悉几种重要的不确定推理方法，如确定因子法、主观Bayes方法、D—S证据理论等，利用数值分析中常用方法进行正确计算。
另外，学生仍应该了解专家系统的基本概念、研究历史、系统结构、系统评价和领域应用。
学生仍应认识机器学习对于智能软件研制的重要性，掌握机器学习的关联概念，机器学习的方法及其相应的学习机制，几个典型的机器学习系统的学习方法、功能和领域应用。
（三）本课程和关联课程的联系、分工或区别和本课程关联的课程有：离散数学、算法设计、数值分析、程序设计语言等。
第三章知识的状态空间表示法1 课前思考：人类的思维过程，可以看作是一个搜索的过程。
某个方案所用的步骤是否最少？也就是说它是最优的吗？如果不是，如何才能找到最优的方案？在计算机上又如何实现这样的搜索？这些问题实际上就是本章我们要介绍的搜索问题。
2 学习目标：掌握回溯搜索算法、深度优先搜索算法、宽度优先搜索算法和A搜索算法，对典型问题，掌握启发式函数的定义方法。
3 学习指南：了解算法的每一个过程和细节问题，掌握一些重要的定理和结论，在有条件的情况下，程序实现每一个算法，求解一些典型的问题。
4 难重点：回溯搜索算法、算法及其性质、改进的Ａ＊算法。
5 知识点：本章所要的讨论的问题如下：有哪些常用的搜索算法。
问题有解时能否找到解。
找到的解是最佳的吗？什么情况下可以找到最佳解？求解的效率如何。
3.1 状态空间表示知识一、状态空间表示知识要点1．状态状态（State）用于描述叙述性知识的一组变量或数组，也可以说成是描述问题求解过程中任意时刻的数据结构。
通常表示成：Q={q1，q2，……，qn}当给每一个分量以确定的值时，就得到一个具体的状态，每一个状态都是一个结点（节点）。
实际上任何一种类型的数据结构都可以用来描述状态，只要它有利于问题求解，就可以选用。
2．操作（规则或算符）操作（Operator）是把问题从一种状态变成为另一种状态的手段。
当对一个问题状态使用某个可用操作时，它将引起该状态中某一些分量发生变化，从而使问题由一个具体状态变成另一个具体状态。
操作可以是一个机械步骤、一个运算、一条规则或一个过程。
操作可理解为状态集合上的一个函数，它描述了状态之间的关系。
通常可表示为：F={ f1 , f2,……… fm}3．状态空间状态空间（State Space）是由问题的全部及一切可用算符（操作）所构成的集合称为问题的状态空间。
用三元组表示为：（{Qs}，{F}，{Qg}）Qs：初始状态，Qg：目标状态，F：操作（或规则）。
4．状态空间（转换）图状态空间也可以用一个赋值的有向图来表示，该有向图称为状态空间图，在状态空间图中包含了操作和状态之间的转换关系，节点表示问题的状态，有向边表示操作。
二、状态图搜索1.搜索方式用计算机来实现状态图的搜索，有两种最基本的方式：树式搜索和线式搜索。
2.搜索策略大体可分为盲目搜索和启发式（heuristic）搜索两大类。
搜索空间示意图例3.1 钱币翻转问题设有三枚硬币，其初始状态为（反，正，反），允许每次翻转一个硬币（只翻一个硬币，必须翻一个硬币）。
必须连翻三次。
问是否可以达到目标状态（正，正，正）或（反，反，反）。
问题求解过程如下：用数组表示的话，显然每一硬币需占一维空间，则用三维数组状态变量表示这个知识：Q=（q1 , q2 , q3）取q=0 表示钱币的正面q=1 表示钱币的反面构成的问题状态空间显然为：Q0=（0，0，0），Q1=（0，0，1），Q2=（0，1，0），Q3=（0，1，1）Q4=（1，0，0），Q5=（1，0，1），Q6=（1，1，0），Q7=（1，1，1）引入操作：f1：把q1翻一面。
f2：把q2翻一面。
f3：把q3翻一面。
显然：F={f1，f2，f3}目标状态：（找到的答案）Qg=（0，0，0）或（1，1，1）例3.2 分油问题。
有两只空油瓶，容量分别为8斤和6斤，另有一个大油桶，里面有足够的油。
我们可以任意从油桶中取出油灌满某一油瓶，也可以把某瓶中的油全部倒回油桶，两个油瓶之间可以互相灌。
问如何在8斤油瓶中精确的得到4斤油。
问题的求解显然用2维数组或状态空间描述比较合适，第一位表示8斤油瓶油量，第二位表示6斤油瓶油量，构成整数序列偶（E，S）E：=0，1，2，3，4，5，6，7，8 。
表示8斤油瓶中含有的油量。
S：=0，1，2，3，4，5，6。
表示6斤油瓶中含有的油量。
总结出如下分油操作规则：f1：8斤油瓶不满时装满（E，S）且E < 8—→（8，S）f2：6斤油瓶不满时装满（E，S）且S < 6—→（E，6）f3：8斤油瓶不空时倒空（E，S）且E > 0—→（0，S）f4：6斤油瓶不空时倒空（E，S）且S > 0—→（E，0）f5：8斤油瓶内油全部装入6斤油瓶内（E，S）E > 0 且E+S ≤6—→（0，E+S）f6：6斤油瓶内油全部装入8斤油瓶内（E，S）S > 0 且E+S ≤8—→（E+S，0）f7：用6斤油瓶内油去灌满8斤油瓶（E，S）且E < 8 且E+S ≥8—→（8，E+S-8）f8：用8斤油瓶内油去灌满6斤油瓶（E，S）且S < 6 且E+S ≥6—→（E+S-6，6）3.2 搜索问题讨论（1）求任一解路的搜索策略回溯法（Backtracking）爬山法（Hill Climbing）宽度优先法（Breadth-first）深度优先法（Depth-first）限定范围搜索法（Beam Search）好的优先法（Best-first）（2）求最佳解路的搜索策略大英博物馆法（British Museum）分枝界限法（Branch and Bound）动态规划法（Dynamic Programming）最佳图搜索法（A﹡）（3）求与或关系解图的搜索法一般与或图搜索法（AO﹡）极小极大法（Minimax）α－β剪枝法（Alpha-beta Pruning）启发式剪枝法（Heuristic Pruning）3.3 图搜索用计算机进行状态空间问题求解的基本思路：首先把问题的初始状态（即初结点）作为当前状态，选择合适的算符对其进行操作，生成一组子状态，然后检查目标状态是否在其中出现。
若出现，则搜索成功，若不出现，则按某种搜索策略从已生成的状态中再选一个状态作为当前状态，重复上述过程，直到目标状态出现，或者不在有可供操作的状态为止。
一、显示图与隐式图1．显式图（显式存储）把与问题有关的全部状态空间以及相应的有关知识（叙述性知识、过程性知识、控制性知识)都直接存入知识库，称为显式图，或“显式存贮”。
2．隐式图（隐式存贮）只存贮与问题有关的部分知识，存贮的状态由初始状态开始运用相应的知识，逐步生成所需的部分状态空间，通过搜索推理，逐渐转移到要求的目标状态，只需在知识库中存贮局部的状态空间，称为“隐式图”或“隐式存贮”。
通常采用隐式图进行解题（搜索推理）。
二、“隐式图”求解问题的一般过程open表：用于存放刚生成的结点closed表：用于存放将要扩展或者已扩展的结点open表closed 表搜索过程如下：1：把初始结点s0放入open表中。
2：检查open表是否为空，若空，问题无解，退出。
3：把open表中的第一个结点取出放入closed表中，并证实该结点为n结点。
4：考察结点n为是否为目标结点，若是，退出。
5：扩展结点n,生成一组子结点，把其中不是先辈的那些结点加入open表的尾部，并配以指向父结点的指针。
6：按某种搜索策略对open表中的结点进行排序7：转入第2步。
一般的图搜索算法1、G=G0(G0=s)，OPEN:= (s);2、CLOSED:=( );3、LOOP:IF OPEN=( ) THEN EXIT(FAIL);4、n:=FIRST(OPEN),REMOVE(n,OPEN),ADD (n,CLOSED),5、IF GOAL(n) THEN EXIT(SUCCESS);6、EXPAND(n)→{mi},G:=ADD{mi,G};7、标记和修改指针:ADD (mi,OPEN),并标记mi到n的指针;计算是否要修改mk、ml到n的指针；计算是否修改ml到其后续节点的指针；8、对OPEN中的节点按某种原则重新排序；9、GO LOOP；一些基本概念节点深度根节点深度=0其它节点深度=父节点深度+1路径设一节点序列为（n0，n1 ，…，nk）,对于i=1,…,k，若节点ni-1具有一个后续节点ni，则该序列称为从n0到nk的路径。
路径的耗散值一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。
用C(ni, nj)表示从ni 到nj的路径的耗散值。
扩展一个节点生成该节点的所有后续节点,并给出它们之间的耗散值.这一过程称为“扩展一个节点”. 三、广度优先搜索流程图广度优先搜索的含义：在对第n层结点没有搜索考察完之前，不对第n+1层结点进行搜索，但在隐式图优先搜索中是讲：从初始结点s0开始，按生成规则逐步生成下一级各子结点，在检查同级子结点同时，生成下级子结点并放在open表的末尾，而后再检查下一个同级结点，如不是目标结点，则按规则生成下级子结点，并放在open表末尾，如此下去，直到找到目标为止。
广度优先搜索算法流程①G:=G0（G0=s）,OPEN:=(s), CLOSED:=（）；②LOOP：IF OPEN＝（）THEN EXIT（FAIL）；③n:＝FIRST（OPEN）；④IF GOAL（n）THEN EXIT（SUCCESS）；⑤REMOVE（n，OPEN），ADD（n，CLOSED）；⑥EXPAND（n）→{mi}，G:＝ADD（mi ，G）；⑦IF 目标在{mi} 中，THEN EXIT（SUCCESS）；⑧ADD（OPEN，mj ），并标记到n的指针；⑨GO LOOP宽度优先搜索示例8数码问题的宽度优先搜索树广度优先搜索的性质当问题有解时,一定能找到解当问题为单位耗散值时,且问题有解时,一定能找到最优解方法与问题无关,具有通用性效率较低属于图搜索方法四、深度优先搜索流程从初始结点s0开始，按生成规则逐步生成下一级各子结点，在检查同级子结点同时，生成下级子结点并放在open表的首部，而后再检查下一个同级结点，如不是目标结点，则按规则生成下级子结点，并放在open表首部，如此下去，直到找到目标为止。
深度优先搜索1、G=G0(G0=s)，OPEN:= (s);，CLOSED:=( );2、LOOP:IF OPEN=( ) THEN EXIT(FAIL);3、n:=FIRST(OPEN),4、IF GOAL(n) THEN EXIT(SUCCESS);5、REMOVE(n,OPEN), ADD (n,CLOSED),6、IF DEPTH(n)>Dm GO LOOP;7、EXPAND(n) →{mi},G:=ADD{mi,G};8、IF 目标在{mi}中THEN EXIT(SUCCESS);9、ADD(mi,OPEN),并标记mj到n指针;10、将mi重排序到open表头部。
11、GO LOOP;深度优先搜索性质一般不能保证找到最优解当深度限制不合理时,可能找不到解,可以将算法改为可变深度限制最坏情况时, 搜索空间等于穷举与回溯法的差别:图搜索是一个通用的与问题无关的方法3.4 回溯策略所谓回溯策略，简单地说是这样一种策略：首先将规则给出一个固定的排序，在搜索时，对当前状态（搜索开始时，当前状态是初始状态）依次检测每一条规则，在当前状态未使用过的规则中找到第一条可触发规则，被应用于当前状态，得到的新状态重新设置为当前状态，并重复以上搜索。
