当前位置：文档之家 › 人工智能第2章(知识表示方法1-状态空间法)

人工智能第2章(知识表示方法1-状态空间法)

  • 格式：ppt
  • 大小：498.00 KB
  • 文档页数：55

下载文档原格式

  / 55

合集下载

人工智能习题&答案-第2章-知识表示方法

人工智能习题&答案-第2章-知识表示方法

第二章知识表示方法2-1 状态空间法、问题归约法、谓词逻辑法和语义网络法的要点是什么？它们有何本质上的联系及异同点?2-2 设有3个传教士和3个野人来到河边，打算乘一只船从右岸渡到左岸去。

该船的负载能力为两人。

在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。

他们怎样才能用这条船安全地把所有人都渡过河去?用S i(nC, nY) 表示第i次渡河后，河对岸的状态，nC表示传教士的数目，nY表示野人的数目，由于总人数的确定的，河对岸的状态确定了，河这边的状态也即确定了。

考虑到题目的限制条件，要同时保证，河两岸的传教士数目不少于野人数目，故在整个渡河的过程中，允许出现的状态为以下3种情况：1. nC=02. nC=33. nC=nY>=0 (当nC不等于0或3)用d i(dC, dY)表示渡河过程中，对岸状态的变化，dC表示，第i次渡河后，对岸传教士数目的变化，dY表示，第i次渡河后，对岸野人数目的变化。

当i为偶数时，dC,dY同时为非负数，表示船驶向对岸，i为奇数时，dC, dY同时为非正数，表示船驶回岸边。

初始状态为S0(0, 0)，目标状态为S0(3, 3)，用深度优先搜索的方法可寻找渡河方案。

在此，用图求法该问题，令横坐标为nY, 纵坐标为nC，可行状态为空心点表示，每次可以在格子上，沿对角线移动一格，也可以沿坐标轴方向移动1格，或沿坐标轴方向移动2格。

第奇数次数状态转移，沿右方，上方，或右上方移动，第偶数次数状态转移，沿左方，下方，或左下方移动。

从(0,0)开始，依次沿箭头方向改变状态，经过11步之后，即可以到达目标状态(3,3)，相应的渡河方案为：d1(1,1)--→d2(-1,0)--→d3(0,2)--→d4(0,-1)--→d5(2,0)--→d6(-1,-1)--→d7(2,0)--→d8(0,-1)--→d9(0,2)--→d10(-1,0)--→d11(1,1)2-3 利用图2.3，用状态空间法规划一个最短的旅行路程：此旅程从城市A 开始，访问其他城市不多于一次，并返回A 。

第二章 知识表示方法

第二章 知识表示方法

第二章知识表示方法教学内容智能系统问题求解所采用的几种主要的知识表示方法(状态空间法.问题归约法.谓词逻辑法.语义网络法)以及基于不同表示法的问题求解方法。

教学重点1. 状态空间表示法中问题的状态描述.改变状态的操作和问题目标状态的搜索;2. 问题规约的一般步骤.规约的与或图表示;3. 谓词逻辑的语法和语义.量词的辖域.谓词公式的置换与合一;4. 语义网络的构成.语义基元的选择.语义网络的推理等。

教学难点状态描述与状态空间图示.问题归约机制.置换与合一。

教学方法课堂教学为主,同时结合《离散数学》等已学的内容实时提问.收集学生学习情况,充分利用网络课程中的多媒体素材来表示抽象概念。

教学要求1. 重点掌握用状态空间法.问题归约法.谓词逻辑法.语义网络法来描述问题.解决问题;2. 掌握这些表示方法之间的差别;并对其它表示方法有一般了解2.1 状态空间法教学内容本节讨论基于解答空间的问题表示和求解方法,即状态空间法,它以状态和操作符为基础来表示和求解问题。

教学重点问题的状态描述,操作符。

教学难点选择一个好的状态描述与状态空间表示方案。

教学方法以课堂教学为主;充分利用网络课程中的多媒体素材来阐述抽象概念。

教学要求重点掌握对某个问题的状态空间描述,学会组织状态空间图.用搜索图来求解问题。

2.1.1 问题状态描述1.基本概念状态(state)它是为描述某类不同事物间的差别而引入的一组最少变量q0,q1,…,qn的有序集合,其矢量形式如下:Q=[q0,q1,…,qn]' (2.1)式中每个元素qi(i=0,1,…,n)为集合的分量,称为状态变量。

给定每个分量的一组值就得到一个具体的状态,如Qk=[q０k,q1k,…,qnk]' (2.2)操作符(operator)称使问题从一种状态变化到另一种状态的手段为操作符或算符。

状态空间(state space)它是表示一个问题全部可能状态及其关系的图,它包含所有可能的问题初始状态集合S、操作符集合F以及目标状态集合G。

第2章 知识表示(人工智能)

第2章 知识表示(人工智能)

A(1,2)
3,3
1,3
1,2
2,2
A(1,2)
例 传教士和野人问题。假设3个传教士带领3个野人划 船渡河，其约束条件是船每一次最多只能运载两个人， 同时在任何时候（A岸、B岸、船上）野人的数目一定不 能比传教士多。 解：设用A和B表示河的两岸，初始状态下传教士、野人 和船都在A岸，目标状态下这三者都到达B岸。我们用m 表示传教士在A岸的数目，用c表示野人在A岸的数目，那 么问题的状态可以表示为三元组（m,c,a）。其中a=1，表 示船在A岸；a=0，表示船在B岸。根据这个约束条件， 在A岸、B岸和船上，野人的数目都不能比传教士多，除 非只有野人的情况。
2. 知识的分类

按其应用范围可分为常识性知识和领域性知识。 按其确定性来可分为确定性知识和不确定性知识。 按其结构及表现形式分为逻辑性知识和形象性知识。
按其形式可分为显性知识和隐性知识。
按静态或动态特性可分为陈述式知识和过程式知识。
2.1.1 知识的概念
3.知识的特性
合适性或可利用性：适用就好。 相对正确性。在一定的条件及环境下，知识一般来说都是正确
6
2012-5-8
可知共有如下12个操作算子： A(1, 2)，A(1, 3)，A(2, 1)，A(2, 3)，A(3, 1)，A(3, 2) B(1, 2)，B(1, 3)，B(2, 1)，B(2, 3)，B(3, 1)，B(3, 2) 根据上述9种可能状态及12种操作算子，可构成二阶梵 塔问题的一个状态空间图。
(2) 可解节点 ①终叶节点是可解节点； ②若节点x有一外向k-连接指向子节点x1, x2, …, xk，且这些子 节点都是可解节点，则x是可解节点。 (3) 不可解节点 ①非终叶节点的叶节点是不可解节点； ②若节点x的每一个外向k-连接都至少指向一个不能可节点， 则x是不可解节点。

第02章知识表示方法

第02章知识表示方法

1. 状态空间法（11）
作业：用状态空间搜索法求解农夫、狼、 羊、菜问题。
A farmer with his goat, wolf and cabbage come to a river that they wish to cross. There is a boat, but it only has room for two, and the farmer is the only one that can row. If the goat and cabbage get in the boat at the same time, the cabbage gets eaten. Similarly, if the wolf and goat are together without the farmer, the goat is eaten. Devise a series of crossings of the river so that all concerned make it across safely.
概 述
知识的特性
1、相对正确性 2、不确定性 3、可表示性 4、可利用性
概 述
知识的分类
1、知识的作用范围：常识知识和领域知识 2、知识的作用及表示： 事实知识：有关领域内的概念、事实、 客观事物的属性、状态及其关系的描述。 规则知识：事物的行动、动作相联系的 因果关系知识。 3、知识的确定性：确定和不确定 4、思维和认识方法：逻辑和形象
2）综合数据库 又称为事实数据库，用于存放输入的事 实、中间的运行结果和最后结果的工作区。 当规则库中的某条产生式前提与综合数据 库的某些已知事实匹配时，该产生式就被 激活，推理出结论放入综合数据库中，作 为后面推理的已知事实。显然综合数据库 是动态变化的。

第二章 知识表示方法(1)

第二章 知识表示方法(1)

第二章知识表示方法人类的智能活动主要是获得并运用知识。

知识是智能的基础，为了使计算机具有智能，能模拟人类的智能行为，就必须使它具有知识。

但人类的知识需要用适当的模式表示出来，才能存储到计算机中并能够被运用第一节知识与知识表示的概念●什么是知识数据与信息➢数据和信息这两个概念是不可以分开的，它们是有关联的。

➢数据：用一组符号及其组合表示的信息称为数据，泛指对客观事物的数量、属性、位置及其相互关系的抽象表示。

例：27.6 53 ABCD 黎明➢数据和信息之间的关系⏹数据是信息的载体和表示，信息是数据在特定场合下的具体含义，即信息是数据的语义。

⏹如：6个人（6是个数据，人是一种信息） 6本书（6是个数据，书是一种信息）⏹对同一个数据，它在某一场合下可能表示这样一个信息，但在另一场合下却表示另一个信息。

知识➢知识：是把有关信息关联在一起所形成的信息结构称为知识。

⏹知识是人们在长期的生活及社会实践中、科学研究及实验中积累起来的对客观世界的认识与经验，人们把实践中获得的信息关联在一起，就获得了知识。

信息之间有多种关联形式，最常见的且便于计算机利用的一种表达形式为：”如果……,那么……” 或”如果……,则……”，它反映了信息间的某种因果关系。

例如把“大雁向南飞”与“冬天就要来临了”这两个信息关联在一起，就得到了如下一条知识：如果大雁向南飞，则冬天就要来临了。

➢不同事物或者相同事物间的不同关系形成了不同的知识。

例如，“雪是白色的”是一条知识，它反映了“雪”与“颜色”之间的一种关系。

又如“如果头痛且流涕，则有可能患了感冒”是一条知识，它反映了“头痛且流涕”与“可能患了感冒”之间的一种因果关系。

知识的特性1、相对正确性知识是否正确是有前提条件的如：1+1=2，但是它是在十进制前提下才是正确的2、不确定性⏹例如：甲有一头秀发，乙是两鬓如霜。

您认为甲一定是青年人，乙就是老年人吗？不能完全确定，因为相反的事例是很多的。

比如：当年的白毛女并不是老人，而现在的老人有一头黑发并不足奇。

人工智能_第2章 知识表示方法

人工智能_第2章 知识表示方法

14
标准槽名
6) Infer槽：指出两个框架所描述的事物间的逻辑推理关系， 用它可以表示相应的产生式规则。 【例】设有下面知识：如果咳嗽，发烧且流涕，则八成是患 了感冒，需服用感冒清，一日三次，每次2-3粒。并要多喝开 水。对该知识 ，可用如下两个框架表示： 框架名：<诊断规则> 框架名：<结论> 病名：感冒 症状1：咳嗽 治疗方法：服用感冒清，一日三 症状2：发烧 次，每次2-3粒 症状3：流涕 注意事项 ：多喝开水 Infer: <结论> 愈后：良好 可信度：0.8 7) Possible-Reason槽：与Infer槽作用相反，用来把某个结论 与可能的原因联系起来。 15
12
标准槽名
2) AKO槽：用于具体的指出事物间的类属关系。其直观含义 是“是一种”，下层框架可以继承其上层框架所描述的属性及值。 对上面的例子，可将棋手框架中的ISA改为AKO。 3)Subclass槽：用于指出子类与类之间的类属关系。 上例中，由于“棋手”是“运动员的一个子类，故可将ISA该为 Subclass。 4) Instance槽：用来建立AKO槽的逆关系。 用它作为某框架的槽时，可用来指出它的下层框架是哪些。 【例】框架名：<运动员> Instance:<棋手>，<足球运动员>，<排球运动员> 姓名：单位（姓，名） 年龄：单位（岁） 性别：范围（男，女） 缺省：男
18
剧本表示-例
【例】餐厅剧本 (1) 开场条件： (a)顾客饿了，需要进餐。(b)顾客有足够的钱。 (2) 角色：顾客，服务员，厨师，老板。 (3) 道具：食品，桌子，菜单，钱。 (4) 场景： 场景1 进入餐厅 (a) 顾客走入餐厅。(b) 寻找桌子。 (c) 在桌子旁坐下。 场景2 点菜 (a) 服务员给顾客菜单。(b) 顾客点菜。 (c) 顾客把菜单还给服务员。(d) 顾客等待服务员送菜。 场景3 等待 (a) 服务员把顾客所点的菜告诉厨师。(b) 厨师做菜。

人工智能2第二章知识表示方法

人工智能2第二章知识表示方法

2.状态空间表示详释
我们先用数码难题(puzzle problem)来 说明状态空间表示的概念。由15个编有1至 15并放在4×4方格棋盘上的可走动的棋子 组成。
11 9 4 15
13
12
7586
13 2 10 14
初试棋局
1 2 34 5 6 78 9 10 11 12 13 14 15
目标棋局
是有关知识的知识，是知识库中的高层知识。 包括怎样使用规则、解释规则、校验规则、解释 程序结构等知识。元知识与控制知识是有重迭的， 对一个大的程序来说，以元知识或说元规则形式 体现控制知识更为方便，因为元知识存于知识库 中，而控制知识常与程序结合在一起出现，从而 不容易修改。
知识表示是研究用机器表示知识的可行
题
求解过程实际上是一个搜索过程。
那么如果进行搜索呢？为了进行搜索，就必须
用某种形式把问题表示出来，其表示是否适当，将
直接影响到搜索效率。
状态空间法就是用来表示问题及其搜索过程的 一种方法。它是人工智能中最基本的形式化方法， 用“状态”和“算符”来表示问题。
状态空间法三要素
(1) 状态（state）：表示问题解法中每一步问题状 况的数据结构；
·显式表示：各节点及其具有代价的弧线由 一张 表明确给出。此表可能列出该图中的每 一节点、它的后继节点以及连接弧线的代价。
Q [q0,q1,...qn ]T
式中每个元素qi(i=0,1，…，n)为集合的量，称 为状态变量。
·算符：使问题从一种状态变化为另一种状态的手 段称为操作符或算符。操作符可为走步、过程、规 则、数学算子、运算符号或逻辑符号等。
· 问题的状态空间(state space)：是一个表示该问题 全部可能状态及其关系的图，它包含三种说明的 集合，即所有可能的问题初始状态集合S、操作符 集合F以及目标状态集合G。可把状态空间记为三 元状态(S，F，G)。

人工智能第二章知识表示方法

人工智能第二章知识表示方法

人工智能第二章知识表示方法答：状态空间法：基于解答空间的问题表示和求解方法，它是以状态和算符为基础来表示和求解问题的。

一般用状态空间法来表示下述方法：从某个初始状态开始，每次加一个操作符，递增的建立起操作符的试验序列，直到达到目标状态为止。

问题规约法：已知问题的描述，通过一系列变换把此问题最终变成一个子问题集合：这些子问题的解可以直接得到，从而解决了初始问题。

问题规约的实质：从目标（要解决的问题）出发逆向推理，建立子问题以及子问题的子问题，直至最后把出示问题规约为一个平凡的本原问题集合。

谓词逻辑法：采用谓词合式公式和一阶谓词算法。

要解决的问题变为一个有待证明的问题，然后采用消解定理和消解反演莱证明一个新语句是从已知的正确语句导出的，从而证明这个新语句也是正确的。

语义网络法：是一种结构化表示方法，它由节点和弧线或链组成。

节点用于表示物体、概念和状态，弧线用于表示节点间的关系。

语义网络的解答是一个经过推理和匹配而得到的具有明确结果的新的语义网络。

语义网络可用于表示多元关系，扩展后可以表示更复杂的问题2-2利用图2.3，用状态空间法规划一个最短的旅行路程：此旅程从城市A开始，访问其他城市不多于一次，并返回A。

选择一个状态表示，表示出所求得的状态空间的节点及弧线，标出适当的代价，并指明图中从起始节点到目标节点的最佳路径。

710910D图2.32-3试用四元数列结构表示四圆盘梵塔问题，并画出求解该问题的与或图。

用四元数列(nA,nB,nC,nD)来表示状态，其中nA表示A盘落在第nA号柱子上，nB表示B盘落在第nB号柱子上，nC表示C盘落在第nC号柱子上，nD表示D盘落在第nD号柱子上。

初始状态为1111，目标状态为3333如图所示，按从上往下的顺序，依次处理每一个叶结点，搬动圆盘，问题得解。

2-4把下列句子变换成子句形式：(1)某y(On(某,y)→Above(某,y))(2)某yz(Above(某,y)∧Above(y,z)→Above(某,z))(1)(ANY某)(ANYy){On(某,y)Above(某,y)}(ANY某)(ANYy){~On(某,y)ORAbove(某,y)}~On(某,y)ORAbove(某,y)最后子句为~On(某,y)ORAbove(某,y)(2)(ANY某)(ANYy)(ANYz){Above(某,y)ANDAbove(y,z)Above(某,z)}(命题联结词之优先级如下:否定→合取→析取→蕴涵→等价)(ANY某)(ANYy)(ANYz){~[Above(某,y)ANDAbove(y,z)]ORAbove(某,z)}~[Above (某,y)ANDAbove(y,z)]ORAbove(某,z)最后子句为~[Above(某,y),Above(y,z)]ORAbove(某,z)2-5用谓词演算公式表示下列英文句子(多用而不是省用不同谓词和项。

人工智能_第2章知识表示方法(1)

人工智能_第2章知识表示方法(1)
6
框架间的继承
◆框架的继承性，就是当子节点的某些槽值或侧面值没有被 直接记录时，可以从其父节点继承这些值。 继承性是框架表示法的一个重要特性，它不仅可以在两个框 架之间实现继承关系，而且还可以通过两两的继承关系，从 最低层追搠到最高层，使高层的信息逐层向低层传递。 例如，椅子一般都有4条腿，如果一把具体的椅子没有说明它 有几条腿，则可以通过一般椅子的特性，得出它也有4条腿。 如果一个在上层框架中描述的属性在下层框架需作进一步说 明时，则需要在下层框架中再次给出描述。 如果在下层框架中对某些槽没有作特别的声明，那么它将自 动继承上层框架相应槽的槽值。
缺省：男
框架名：<棋手> ISA: <运动员> 脑力：特好
12
标准槽名
2) AKO槽：用于具体的指出事物间的类属关系。其直观含义 是“是一种”，下层框架可以继承其上层框架所描述的属性及值。 对上面的例子，可将棋手框架中的ISA改为AKO。 3)Subclass槽：用于指出子类与类之间的类属关系。 上例中，由于“棋手”是“运动员的一个子类，故可将ISA该为 Subclass。 4) Instance槽：用来建立AKO槽的逆关系。 用它作为某框架的槽时，可用来指出它的下层框架是哪些。 【例】框架名：<运动员>
缺省：教师 开始工作时间：单位(年，月) 截止工作时间：单位(年，月)
缺省：现在 离退休状况：范围(离休，退休)
9
框架络-例
教师框架为： 框架名：<教师> 继承：<教职工> 部门：单位(系，教研室) 语种：范围(英语,法语,日语,
德语,俄语)
缺省：英语 外语水平：范围(优，良， 中，差)
缺省：良 职称：范围(教授,副教授,讲师,

人工智能 状态空间法 第二章主讲

人工智能 状态空间法 第二章主讲

2.2 问题规约法
• 不可解节点的一般定义
–没有后裔的非终叶节点为不可解节点。 –全部后裔为不可解的非终叶节点且含有或后继节点， 此非终叶节点才是不可解的。 –后裔至少有一个为不可解的非终叶节点且含有与后 继节点，此非终叶节点才是不可解的。
• 与或图构成规则
2.2 问题规约法
3.定义图解
有解节点
A
B
C D
G E F N
A
M
H
B
C D E F G
2.2 问题规约法
2.一些关于与或图的术语
父节 点
A
或节 点 弧线 与节 点 B 终叶节 点 C D
子节 点
H
N
M
E
F
G
3.定义
一些关于与或图的术语： 父节点、子（后继）节点、弧线、起始节点。 终叶节点：对应于原问题的本原节点。 或节点：只要解决某个问题就可解决其父辈问题的节点 集合，如（M，N，H）。 与节点：只有解决所有子问题，才能解决其父辈问题的 节点集合，如（B,C)和（D,E,F）各个结点之间用一端小圆弧 连接标记。
主讲人： XXX
状态空间法
第2 章 知识表示方法
（一）
问题归约法 谓词逻辑表示
语义网络表示
框架表示
第2 章 知识表示方法
（二）
本体技术 过程表示
小结
2.1状态空间法 （State Space Representation）
• 问题求解技术主要是两个方面：
– 问题的表示 – 求解的方法
• 状态空间法
2.3 谓词逻辑法
• 前面具有符号～的公式叫做否定。一个合适公式的否定也是 合适公式。 例：～INROOM(ROBOT，r2)(机器人不在2号房间内。)

人工智能导论第二章

人工智能导论第二章
第二章 知识表示方法
• 2.1 知识和知识表示 • 2.2 状态空间表示 • 2.3 问题归约表示 • 2.4 谓词逻辑表示 • 2.5 语义网络表示 • 2.6 产生式表示 • 2.7 框架表示 • 2.8 面向对象表示
2021/2/28
人工智能导论第二章-
1
产生式
2.6 产生式表示
• 产生式通常用于表示事实、规则以及它们 的不确定性度量，适合于表示事实性知识 和规则性知识。
THEN 该动物是食肉动物
r7： IF 该动物是哺乳动物 AND 有蹄 THEN 该动物是有蹄类动物
r 8： IF 该动物是哺乳动物 AND 是反刍动物
THEN 该动物是有蹄类动物
2021/2/28
人工智能导论第二章- 刘珊
12
规则库
2.6 产生式表示
r9： IF 该动物是哺乳动物 AND 是食肉动物 AND 是黄褐色
2021/2/28
人工智能导论第二章- 刘珊
5
产生式的形式描述及语义
——巴科斯范式BNF
2.6 产生式表示
<产生式>::= <前提> <结论> <前 提> :: = <简单条件>|<复合条件> <结 论> :: = <事实>|<操作> <复合条件> :: = <简单条件>AND<简单条件>[AND<简单
AND 身上有暗斑点
THEN 该动物是金钱豹
r10：IF 该动物是哺乳动物 AND 是食肉动物 AND 是黄褐色 AND 身上有黑色条纹 THEN 该动物是虎
r11： IF 该动物是有蹄类动物 AND 有长脖子 AND 有长腿 AND 身上有暗斑点 THEN 该动物是长颈鹿

人工智能课件 --02知识的表示与推理-1

人工智能课件 --02知识的表示与推理-1
P=>P ٧ Q • 析取三段论
¬P, P ٧ Q =>Q
第一节 知识表示的一般方法
• 假言推理
P, P → Q =>Q
• 拒取式 ¬Q, P→Q=> ¬P
• 假言三段论 P→Q, Q→R => P→R
• 二难推论 P ٧ Q, P → R, Q → R => R
• 全称固化 (∀x) P(x) => p(y) 其中,y是个体域中的任一个体。
第一节 知识表示的一般方法
三、谓词表示法 1、复习(命题逻辑与谓词逻辑) (1) 命题
定义：命题是具有真假意义的语句。
命题代表人们进行思维的一种判断，或者为肯定，或 者为否定。
在命题逻辑中，通常用大写的英文字母表示。例如， 可用英文字母P表示“西安是个古老的城市”这个命题。
第一节 知识表示的一般方法
第一节 知识表示的一般方法
④ 谓词公式的解释 在命题逻辑中，对命题公式中各个变元的一次真值指
派，称为命题公式的一个解释。
⑤ 谓词公式的永真性、可满足性、不可满足性 如果谓词公式P对个体域D上的任何一个解释都取真值
T，则称P在D上永真的。 对于谓词公式P，如果至少存在一个解释使得公式P为
真值T,则称公式P是可满足的。 如果谓词公式P对于个体域D上的任何一个解释都取真
(2)谓词 在谓词逻辑中，命题用谓词来表示。
谓词的一般形式：P(x1,x2,…,xn) 其中P是谓词名，xi是个体。个体可以是变量、常 量或函数。
在P(x1,x2,…,xn)中，如果xi是变量、常量或 函数,则称为一阶谓词；如果xi本身又是一个一阶 谓词，则称为二阶谓词。
第一节 知识表示的一般方法
第2章 知识的表示与推理(1)

2第二讲 第二章 知识表示(状态空间法)

2第二讲 第二章 知识表示(状态空间法)
1
一、问题状态描述 2、算符：
使问题从一种状态变化为另一种状态的手段，操作 符可为走步、过程、规则、数学算子、运算符号 或逻辑符号等。
3、状态空间：
一个表示该问题全部可能状态及其关系的图，包含 三种说明的集合，即所有可能的问题初始状态集 合S、 操作符集合F以及目标状态集合G。可把状 态空间记为三元状态(S，F，G)。
2 3 1 8 4 7 6 5
2 3 4 1 8 7 65
2.2状态空间法
求解的方法：首先把适用的算符用于初始状态，
以产生新的状态；然后，再把另一些适用算符 用于这些新的状态；这样继续下去，直至产生 目标状态为止。
初始 状态 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 1 2 3 8 4 7 6 5 目标状态 2 8 3 1 4 7 6 5
1
状态空间表示概念详释
初始状态
操 作
中间状态
操 作
目标状态
对一个问题的状态描述，必须确定3件事： ①该状态描述方式，特别是初始状态描述； ②操作符集合及其对状态描述的作用； ③目标状态的描述。 例如：数码难题。
1
例1:三数码难题（3 puzzle problem）
2 3
1 3 2 1 初始棋局
2 3 1 8 4 7 6 5 2
图论的基本概念
如果从节点ni到节点n 4）路径：某个节点序列 (n j存在有一条路经，则称 1,n2,…,nk)，当 j=2， nj 是从 ni时，如果对于每一个 可达到的节点。 3，… ，k nj-1都有一个后继节点 寻找从一种状态变换成另一种状态的某个算符 nj存在，那么就把这个节点序列叫做从节点 n1至节点 序列问题等价于寻求图的某一路径问题。 nk的长度为 k的路径。

第2章 知识表示方法

第2章 知识表示方法

图2.1 猴子和香蕉问题
状态空间表示： 用四元组（W，x，Y，z） 其中： W－猴子的水平位置； x－当猴子在箱子顶上时取x=1； 否则取x=0； Y－箱子的水平位置； z－当猴子摘到香蕉时取z=1； 否则取z=0。
操作符 ：
(1) goto(U)猴子走到水平位置U，或者用产生式规则表示为
goto (U ) (W ,0, Y , Z ) (U ,0, Y , z)
从问题的初始状态集S出发，经过一系列的 算符运算，到达目标状态。由初始状态到目标 状态所用的算符的序列就构成了问题的一个解。 由上可知，对一个问题的状态描述，必须确 定3件事： (1) 该状态描述方式，特别是初始状态描述； (2) 操作符集合及其对状态描述的作用； (3) 目标状态描述的特性。
2、状态空间表示详释
第2章 知识表示方法
传统的人工智能主要运用知识进行问题求解，从实用的观点 看，人工智能是一门知识工程学：以知识为对象，研究知识的表 示方法，知识的运用和知识获取。 知识作为机器智能的一部分，就必须能够让机器知道什么是 知识，那就涉及到了知识的表示问题，这个问题就象人记录某一 事实有不同的方法一样，知识表示的方法很多，有图示法和公式 法，结构化方法，陈述式表示和过程式表示等。 图示法：状态空间法、问题归约法等。 公式法：谓词逻辑法等。 陈述式表示：语义网络表示法、框架表示法、剧本表示法等。 过程式表示：过程表示。
2
目标状态
问题的解答就是某个合适的棋子走步序列。 三数码的任何一种摆法即为一个状态。所有的 摆法构成状态集，共有4！个状态，即24个状态。 状态之间的变化可通过算符来实现。 算符： （1)定义为棋子走动：3个数码×4种方向＝12种 （2)定义为空格移动：4种，即F＝[f1, f2, f3, f4]T,
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

T(k)：表示第 k 根柱子上（最上面）的盘的大小。
操作符集合为： O={m( i , j ) | T( i )<T( j )}
2013-8-7
部分状态空间图
2013-8-7
例4：猴子与香蕉问题
a
c
b
2013-8-7
用一个四元组（W，x, Y, z）来表示问题的状态 W：猴子的水平位置 x： 当猴子爬到箱子顶上取1，否则取0 Y： 箱子的水平位置 z： 当猴子摘到香蕉时取1，否则取0
利用最优化技术中的算法，可以得到结果： x = y = z = 5.0
解释：长、宽、高都等于5米时，体积最大
说明：在计算数学的课程中，主要关心求解的
具体算法
2013-8-7
在人工智能中，重点关注两个方面的内容：
①问题的表示（知识的表示）：即要找到问题的一
种合适的表示方法
在人工智能中，我们要涉及到：
来表示
2013-8-7
有向图：一对节点用弧线连接起来，并且从一
个节点指向另一个节点
父辈节点或祖先n i
后继节点或后裔nj
2013-8-7
对于某一个节点序列 （ni0, ni2, … nij, …, nik） 如果每一个节点 nij-1 都有一个 后继节点 nij 存在，则将这一
ni0
序列称为从节点 ni0 到 nik 的
状态空间法
问题归约法 谓词逻辑法 样本向量法
2013-8-7
②问题的求解：从问题表示方法出发，找到一个
合理的办法来求解
在人工智能中，常有的方法有： 搜索法 推理法 计算方法
2013-8-7
2.1 状态空间法
在日常的一些智力游戏（八数码、走八卦阵、走 迷宫等）中，我们采用的策略ik
ni
祖先
如果从节点 ni 到 nj 存在 一条路径，则称节点 nj 是
从节点 ni 可到达的节点，
或者称 nj 是 ni 的后裔节 点、称 ni 是 nj 的祖先。
后裔
2013-8-7
nj
当用有向图来表示状态空间法时，对应关系：
图中的一个节点对应于某一个状态
2013-8-7
操作符：
③猴子爬到箱子上：climbbox：
（W, 0, W, z） (W，1, W, z) ④猴子摘到香蕉：grasp： （c, 1, c, 0） (c, 1, c, 1)
2013-8-7
初始状态
(a, 0, b, 0) goto(b) (b, 0, b, 0) climbbox pushbox (c, 0, c, 0) (b, 1, b, 0)
实际
问题
结果的解释
2013-8-7
问题表达
知识表达
数学建模
求解的方法
或者算法
例：求侧面积为150平方米的体积最大的长方体？ y x 侧面积为：2(xy + yz + xz) z 体积为：xyz 数学模型
设长、宽、高分别为 x, y, z
max xyz
s.t.
2013-8-7
2(xy + yz + xz)=150
图中的一个有向弧对应于某一个算符
注：有向弧的旁边可以标以具体算符
2013-8-7
状态
节点
操作符
2013-8-7
有向弧
问题：寻找从初始状态到目标 状态的某个操作符序列
转 化 为
问题：寻找图中初始节点（对应初
始状态）到目标节点（对应于目标
状态）的一条路径
2013-8-7
在某些情况下，每个操作符作用、成本是不 一样的，需要引入代价的概念
2013-8-7
例2：迷宫问题
2013-8-7
给图上加一个坐标系，定义每一个分叉路口 为一个状态。
2013-8-7
目标状态为（4，4） 操作符为人的上、
下、左、右走动
初始状态为（1，1）
2013-8-7
部分状态空间图
2013-8-7
例3：梵塔问题（三个盘）
对于 n 个盘的问题，我们用 n 维向量 （a1 a2…an）
2.1.1 问题状态描述
状态：
描述某一类不同事物间的差别而引入的一 组最少变量q0 ,q1 ,…, qn的有序集合
2013-8-7
例：描述在坐的同学 根据要解决的问题、从 变量可以有 年级 班级 姓名 性别 学号 ……
2013-8-7
中选择最少的一组变量 例： 区分哪一个班：年级、 班级 区分哪一位同学：姓 名、性别、学号
1 2 3
P≠1,4,7 P≠1,2,3 P≠3,6,9
4
下移
P≠7,8,9
P+3
1 表示位置
2013-8-7
2 5 8
3 6 9
4 7
初始状态：(2，0，3，1，8，4，5，6，7）
部分状态空间图
目标状态:（1，2，3，8，0，4，7，6，5）
2013-8-7
注意：
事先规定操作符的前后顺序，便于编程 不要生成已有的状态（节点），防止进入死循环
路径。对应于寻找将初始状态变换到目标状态所用
操作符代价之和最小的操作符序列
2013-8-7
2.1.3 例子
例1：八数码问题 八数码的任何一种摆法是一个状态，状态总数
为9！。用一个长度为9的一维数组来描述状态：
（q1, q2, …,q9） 其中，qi 取0, 1, …, 8个数，0表示空格，且取值互 不相同。 算符是空格的上、下、左、右移动
初始状态是（a, 0, b, 0），目标状态是（c, 1, c, 1）
2013-8-7
操作符：
①猴子当前位置W走到水平位置U：goto(U)：
（W, 0 , Y, z）(U, 0 , Y, z)
注：猴子必须不在箱子上
② 猴 子 将 箱 子 从 W 位 置 推 到 水 平 位 置 V： pushbox(V)： （W, 0, W, z） (V, 0, V, z) 注：猴子与箱子必须在同一位置
2013-8-7
如果记空格的位置为P，这时空格的移动规则是： 1 2 3 1 2 3 8 5 6 7 4 0 P
1 2 3 4 5 6 7 8 9
8 7
5 4
6
P-3
表示位置
P-1
P
P+1
2013-8-7
P+3
空格移动规则
代码
规则 左移 上移 右移
前提条件
应用结果
P 位置与 P-1 位置上的元素互换 P-3 P+1
矢量形式：
Q=[ q0, q1, …, qn ]
T
其中，元素 qi ( i=0, 1,…, n)为集合的分
量，称为状态变量。 具体状态：给每一个状态变量一个具体的
值（符号、数值等）。
2013-8-7
矩阵形式
q11 ... q 1n Q qm1 ... qmn
2013-8-7
例：八数码问题
矢量形式的状态表示：
1
2
3
4
6
2 7 5
7
5
3 8 0
8
1,
2, 3, 4, 7, 8, 6, 5, 0
1 4 6
矩阵形式的状态表示：
2013-8-7
算符（操作符）：使问题从一个状态 变换到另一状态的手段。 例如：走步、规则、数学算子、运算 符号等等。
an ... a2 a1
表示问题的一个状态
其中ai = 1, 2, 3 表示第i个盘位于第一、二、 三个柱子上，a1 an中盘的大小从大到小
2013-8-7
初始状态为（1…1），目标状态为（3…3） 操作符m(i, j)：表示一个盘从 i 根柱子搬到第 j 根 柱子。
考虑如何在计算机上加以实现？
2013-8-7
1 5 9
2 6
3 7
4 8
10 11 12
13 14 15
2.1.2 状态图示法
状态空间法（求解过程）的表示方法：用图来表 示（借助于图论中某些技术）
图是由节点（不一定是有限个的节点）的集合
构成的
注意：在图论中，图的定义中还包括边的集合
2013-8-7
有向图和无向图：
2013-8-7
无向图：一对节点可能互为后裔，边用线段
2013-8-7
可能的求解过程
注：在程序和图示求解过程中，需要规定好操作符
的使用顺序 2013-8-7
要完成某一个具体问题的状态描述，必须完 成三项工作： ①如何描述状态，特别是初始状态
②操作符集合及其对状态描述的作用
③如何描述目标状态 即定义好三元状态（S, F, G）中的三个成分
2013-8-7
2013-8-7
例：描述在坐的同学（续） 状态变量可以有 年级 班级 姓名 性别 学号 ……
2013-8-7
操作符
入学 正常升级 毕业
例：八数码问题
1
4
算符：
2
7
3
8
6
5
1、数字的上、下、左、右移动 2、空格的上、下、左、右移动
2013-8-7
问题的状态空间：一个表示问题全部可能状
态及其关系的图，它包含了三个集合：
人
工
智
能
Artificial Intelligence (AI)
许建华 xujianhua@
南京师范大学计算机科学与技术学院
2011年秋季
2013-8-7
第2章 知识表示方法
2.1 状态空间法 2.2 问题归约法 2.3 谓词逻辑法
2013-8-7
用计算机技术解决实际问题的一般思路: