下载文档原格式
第三章搜索推理技术3-1什么是图搜索过程?其中，重排OPEN表意味着什么，重排的原则是什么?图搜索的一般过程如下：(1) 建立一个搜索图G(初始只含有起始节点S)，把S放到未扩展节点表中（OPEN表）中。
(2) 建立一个已扩展节点表（CLOSED表），其初始为空表。
(3) LOOP：若OPEN表是空表，则失败退出。
(4) 选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。
称此节点为节点n，它是CLOSED表中节点的编号(5) 若n为一目标节点，则有解并成功退出。
此解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第7步中设置)(6) 扩展节点n，生成不是n的祖先的那些后继节点的集合M。
将M添入图G中。
(7) 对那些未曾在G中出现过的(既未曾在OPEN表上或CLOSED表上出现过的)M成员设置一个通向n的指针，并将它们加进OPEN表。
对已经在OPEN或CLOSED表上的每个M成员，确定是否需要更改通到n的指针方向。
对已在CLOSED表上的每个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方向。
(8) 按某一任意方式或按某个探试值，重排OPEN表。
(9) GO LOOP。
重排OPEN表意味着，在第(6)步中，将优先扩展哪个节点，不同的排序标准对应着不同的搜索策略。
重排的原则当视具体需求而定，不同的原则对应着不同的搜索策略，如果想尽快地找到一个解，则应当将最有可能达到目标节点的那些节点排在OPEN表的前面部分，如果想找到代价最小的解，则应当按代价从小到大的顺序重排OPEN表。
3-2 试举例比较各种搜索方法的效率。
宽度优先搜索(1) 把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。
(2) 如果OPEN是个空表，则没有解，失败退出；否则继续。
(3) 把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED扩展节点表中。
(4) 扩展节点n。
⼈⼯智能课程习题与部分解答《⼈⼯智能》课程习题与部分解答第1章绪论1.1 什么是⼈⼯智能? 它的研究⽬标是什么?1.2 什么是图灵测试?简述图灵测试的基本过程及其重要特征.1.3 在⼈⼯智能的发展过程中，有哪些思想和思潮起了重要作⽤？ 1.5 在⼈⼯智能的发展过程中，有哪些思想和思潮起了重要作⽤？1.7 ⼈⼯智能的主要研究和应⽤领域是什么？其中，哪些是新的研究热点？第2章知识表⽰⽅法2.1 什么是知识？分类情况如何？2.2 什么是知识表⽰？不同的知识表⽰⽅法各有什么优缺点? 2.4 ⼈⼯智能对知识表⽰有什么要求? 2.5 ⽤谓词公式表⽰下列规则性知识：⾃然数都是⼤于零的整数。
任何⼈都会死的。
[解] 定义谓词如下:N(x): “x 是⾃然数”, I(x): “x 是整数”, L(x): “x ⼤于0”, D(x): “x 会死的”, M(x): “x 是⼈”,则上述知识可⽤谓词分别表⽰为: )]()()()[(x I x L x N x ∨→? )]()()[(x D x M x →?2.6 ⽤谓词公式表⽰下列事实性知识：⼩明是计算机系的学⽣，但他不喜欢编程。
李晓新⽐他⽗亲长得⾼。
2.8 产⽣式系统由哪⼏个部分组成? 它们各⾃的作⽤是什么?2.9 可以从哪些⾓度对产⽣式系统进⾏分类? 阐述各类产⽣式系统的特点。
2.10简述产⽣式系统的优缺点。
2.11 简述框架表⽰的基本构成，并给出框架的⼀般结构 2.12框架表⽰法有什么特点？2.13试构造⼀个描述你的卧室的框架系统。
2.14 试描述⼀个具体的⼤学教师的框架系统。
[解] ⼀个具体⼤学教师的框架系统为：框架名：<教师-1> 类属：<⼤学教师>姓名：张宇性别：男年龄：32职业：<教师>职称：副教授部门：计算机系研究⽅向：计算机软件与理论⼯作：参加时间：2000年7⽉⼯龄：当前年份-2000⼯资：<⼯资单>2.16把下列命题⽤⼀个语义⽹络表⽰出来(1)树和草都是植物；(2)树和草都是有根有叶的；(3)⽔草是草，且⽣长在⽔中；(4)果树是树，且会结果；(5)苹果树是果树的⼀种，它结苹果。
【⼈⼯智能】《⼈⼯智能》课程习题《⼈⼯智能》课程习题第⼀章绪论1-1. 什么是⼈⼯智能？试从学科和能⼒两⽅⾯加以说明。
1-2. 在⼈⼯智能的发展过程中，有哪些思想和思潮起了重要作⽤？1-3. 为什么能够⽤机器（计算机）模仿⼈的智能？1-4. 现在⼈⼯智能有哪些学派？它们的认知观是什么？1-5. 你认为应从哪些层次对认知⾏为进⾏研究？1-6. ⼈⼯智能的主要研究和应⽤领域是什么？其中，哪些是新的研究热点？第⼆章知识表⽰⽅法2-1状态空间法、问题归约法、谓词逻辑法和语义⽹络法的要点是什么？它们有何本质上的联系及异同点?2-2设有3个传教⼠和3个野⼈来到河边，打算乘⼀只船从右岸渡到左岸去。
该船的负载能⼒为两⼈。
在任何时候，如果野⼈⼈数超过传教⼠⼈数，那么野⼈就会把传教⼠吃掉。
他们怎样才能⽤这条船安全地把所有⼈都渡过河去?再定义描述过河⽅案的谓词：L-R(x, x1, y, y1,S)：x1个修道⼠和y1个野⼈渡船从河的左岸到河的右岸条件：Safety(L,x-x1,y-y1,S’)∧Safety(R,3-x+x1,3-y+y1,S’)∧Boat(L,S)动作：Safety(L,x-x1,y-y1,S’)∧Safety(R,3-x+x1,3-y+y1,S’)∧Boat(R,S’)R-L (x, x1, y, y1,S)：x2个修道⼠和y2个野⼈渡船从河的左岸到河的右岸条件：Safety(R,3-x-x2,3-y-y2,S’)∧Safety(L,x+x2,y+y2,S’)∧Boat(R,S)动作：Safety(R,3-x-x2,3-y-y2,S’)∧Safety(L,x+x2,y+y2,S’)∧Boat(L,S’)(2) 过河⽅案Safety(L,3,3,S0)∧Safety(R,0,0,S0)∧Boat(L,S0)L-R(3, 1, 3, 1,S0) L-R(3, 0, 3, 2,S0)Safety(L,2,2,S1)∧Safety(R,1,1,S1)∧Boat(R,S1)Safety(L,3,1,S1’)∧Safety(R,0,2,S1’)∧Boat(R,S1’)R-L (2, 1, 2, 0,S1) R-L (3,0, 1, 1,S1’)Safety(L,3,2,S2)∧Safety(R,0,1,S2)∧Boat(L,S2)L-R(3, 0, 2, 2,S2)Safety(L,3,0,S3)∧Safety(R,0,3,S3)∧Boat(R,S3)R-L (3, 0, 0, 1,S3)Safety(L,3,1,S4)∧Safety(R,0,2,S1)∧Boat(L,S4)L-R(3, 2, 1, 0,S4)Safety(L,1,1,S5)∧Safety(R,2,2,S5)∧Boat(R,S5)R-L (1, 1, 1, 1,S5)Safety(L,2,2,S6)∧Safety(R,1,1,S6)∧Boat(L,S6)L-R(2, 2, 2, 0,S6)Safety(L,0,2,S7)∧Safety(R,3,1,S7)∧Boat(R,S7)R-L (0, 0, 2, 1,S7)Safety(L,0,3,S8)∧Safety(R,3,0,S8)∧Boat(L,S8)L-R(0, 0, 3, 2,S8)Safety(L,0,1,S9)∧Safety(R,3,2,S9)∧Boat(R,S9)R-L (0, 1, 1, 0,S9)Safety(L,1,1,S10)∧Safety(R,2,2,S10)∧Boat(L,S10)2-3利⽤图2.3，⽤状态空间法规划⼀个最短的旅⾏路程：此旅程从城市A开始，访问其他城市不多于⼀次，并返回A。
