当前位置：文档之家 › 知识表示方法状态空间法

知识表示方法状态空间法

  • 格式：ppt
  • 大小：1.40 MB
  • 文档页数：15

下载文档原格式

  / 15

合集下载

智能控制—知识表示方法

智能控制—知识表示方法

第二次智能控制作业赵东亮19212030325状态空间法、问题归约法、谓词逻辑法和语义网络法四种方法的要点、联系及本质区别问题的状态空间是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即所有可能的问题初始状态集合S、操作符集合F以及目标状态集合G。

因此，把状态空间记为三元状态（S,F,G）。

要完成某个问题的状态描述，必须确定三件事：一是该状态描述方式，特别是初始状态描述；二是操作符集合及其对状态描述的作用；三是目标状态描述的特性。

推销员旅行问题就属于状态空间法。

问题归约法指的是从目标（要解决的问题）出发逆向推理，建立子问题以及子问题的子问题，直到最后把初始问题规约为一个平凡的本原问题集合。

这就是问题规约的实质。

它由三个部分组成：一是一个初始问题的描述；二是一套把问题变换为子问题的操作符；三是一套本原问题描述。

汉诺塔问题就属于问题归约法。

谓词逻辑法是指采用谓词合适公式和一阶谓词演算把要解决的问题变为一个有待证明的问题，然后采用消解定理和消解反演来证明一个新语句是从已知的正确语句导出的，从而证明这个新语句也是正确的。

谓词逻辑是一种形式语言，能够把数学中的逻辑论证符号化。

谓词逻辑法常与其它表示方法混合使用，灵活方便，可以表示比较复杂的问题。

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

节点用于表示实体、概念和情况等，弧线用于表示节点间的关系。

语义网络表示由四个相关部分组成：一是词法部分，决定表示词汇表中允许有哪些符号，它涉及各个节点和弧线；二是结构部分，叙述符号排列的约束条件，指定各弧线连接的节点对；三是过程部分，说明访问过程，这些过程能用来建立和修正描述以及回答相关问题；四是语义部分，确定与描述相关的意义的方法即确定有关节点的排列及其占有物和对应弧线。

四类方法的要点：（1）状态空间法需要扩展过多的节点，容易出现“组合爆炸”，因而只适用于比较简单的问题；（2）问题规约法比状态空间法更有效地表示问题。

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

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

清华大学
VISITING TEAM
篮球比赛
ISA SCORE
G25
HOME TEAM
北京大学
85:89
语义网络法
❖ 连接词和量词的表示
✓ 合取和析取的表示：可通过
增加合取节点和析取节点来实 现
✓ 例如：用语义网络表示：“参 赛者有教师有学生，参赛者的 身高有高有低”
✓ 分析参赛者的不同情况，可得 到以下四种情况：
✓ 蕴含的表示：通过增加蕴含关系节点来实现。在蕴含关系中，有 两条指向蕴含节点的弧，一条代表前提条件(Antecedent) ，标记为 ANTE；另一条代表结论(Consequence) ，标记为CONSE
✓ 例如：用语义网络表示：“如果学校组织大学生机器人竞赛活动， 那么李强就参加比赛”
智能机器
比赛 AKO
Artificial Intelligence (AI)
人工智能
第4章：知识 表示
内容提要
第4章：知识表示
1.状态空间法 2.问题归约法 3.谓词逻辑法 4.语义网络法 5.其他方法
语义网络法
❖语义网络法（ Semantic Network Representation ）
✓ 语义网络是奎廉(J. R. Quillian) 1968年在研究人类联想 记忆时提出的一种心理学模型，认为记忆是由概念间的 联系实现的。随后，奎廉又把它用作知识表示。
Can
Can
运动
动物
吃
语义网络法
❖ 二元关系：二元语义网络表示
✓ 可用二元谓词P(x,y)表示的关系。其中，x,y为实体，P为实 体之间的关系。
✓ 单个二元关系可直接用一个基本网元来表示 ✓ 对复杂关系，可通过一些相对独立的二元或一元关系的组合

2.2.3 知识表示与问题求解(状态空间法)

2.2.3 知识表示与问题求解(状态空间法)
自动化系仪自教研室 6
2.2.3 状态空间法
2.2.3.1 问题状态空间的构成
2. 算符
•算符：引起状态中某些变量发生变化，从而使问
题由一个状态变为另一个状态的操作。
•算符可分为走步、过程、规则、数学算子、运算
符号、逻辑符号等。
•例如：在产生式系统中，每一条产生式规则就是
一个算符；而在下棋程序中，一个算符就是一个 走步。
时，世界的末日就来临了。
自动化系仪自教研室 14
2.2.3 状态空间法 Hanoi塔
19世纪，法国的一位数学家 Édouard Lucas (1842−1891) 对该课 题进行过研究，他指示，要完成这 个任务，僧侣们搬动金盘的总次数： 18446744073709551615（20位）假 设僧侣们个个身强力壮，每天24小 时不知头疲倦地工作，而且一秒钟 移动一个金盘，那么，完成这个任 务也得花5800亿年。
自动化系仪自教研室
21
2.2.3 状态空间法 在状态空间图中，从初始节点(1，1)(状态S0)到目 标节点(3，3)(状态S8)的任何一条通路都是问题的 一个解。 最短的路径长度是3，它由3个算符组成：A(1，2)、 B(1，3)、A(2，3)。
自动化系仪自教研室
22
2.2.3 状态空间法

问题的初始状态集合为S={S0}，目标状态集合为 G={S8}。 自动化系仪自教研室
18
2.2.3 状态空间法
自动化系仪自教研室
19
2.2.3 状态空间法 ③定义一组算符F 算符A(i，j)表示把盘子A从第i号柱子移到第j号柱 子上的操作； 算符B(i，j)表示把盘子B从第i号柱子移到第j号柱 子上的操作。 算符组F中共有12个算符:

知识表示方法第五部分

知识表示方法第五部分
框架名：<计算机系教师>
类属：<教师> 性格：内向 兴趣：操作计算机
框架名：<方园>
类属：<计算机系教师>
性格：内向
态度：不刻苦
兴趣：？ 举止：？
推理
框架表示法
❖ 框架的推理：在框架网络中，问题求解主要是通过对框
架的继承与匹配来实现的。
❖继承
✓ 下层框架从上层框架继承相关属性、属性值、条件
❖匹配
✓ 框架通常只能与现实做到部分匹配，完全匹配是一个 特殊情况。因为框架是对一类事物的完整或典型的描 述，待匹配的具体个体不可能做到完全一致。
1 2× 3×
×××
Step(4)
123
××
×××
(d)
Step(5)
过程表示法
✓ 过程表示法的例子：八数码问题
பைடு நூலகம்
(6)依次移动棋牌，使得空格位置沿
图 (e)所示的箭头方向移动，直到数
码4在位置f为止，如图Step(6) 中所
(e)
示。若这时刚好数码5在位置i则转
(9)。
(7)依次移动棋牌，使得空格位置沿
✓ 不匹配的情况：某个属性不存在，或与规定的属性值 不符，或属性类型不符
框架表示法
❖ 框架表示法的优点：
✓ 结构性：最突出特点是善于表示结构性知识，它能够把知识 的内部结构关系以及知识间的特殊联系表示出来。
✓ 深层性： 框架表示法不仅可以从多个方面、多重属性表示 知识，而且还可以通过ISA、AKO等槽以嵌套结构分层地对 知识进行表示，因此能用来表达事物间复杂的深层联系。
沿图(c)所示的箭头方向移动，直到
数码3位于e为止。这时空格刚好在

第二章 知识表示方法

第二章 知识表示方法

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

教学重点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第二章知识表示方法

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)

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

人工智能中的知识表示方法

人工智能中的知识表示方法1.一阶谓词逻辑表示方法2.产生式表示方法3.语义网络表示方法4.框架表示方法、5.过程表示方法除了以上五种表示方法，比较常用的还有以下几种表示方法：6.面向对象表示方法：对象是有一组数据和该数据相关的操作构成的实体。

类由一组变量和一组操作组成，它描述了一组具有相同属性和操作的对象。

每个对象都属于某一个类，每个对象都可由相关的类生成，类的生成过程就是例化。

面向对象的基本特征主要体现在模块性、封装性、继承性、多态性、易维护性等。

7.状态空间表示方法：状态空间表示法是以状态和运算符为基础来表示和求解问题的一种方法。

（1）状态描述问题求解过程中任一时刻状况的数据结构，一般用一组变量的有序组合表示。

（2）算符引起状态中某些分量发生变化，从而使问题由一个状态变为另一个状态的操作称为算符。

（3）状态空间由问题的全部状态以及一切可用算符所构成的集合称为问题的状态空间。

空间状态表示方法的应用举例：猴子与香蕉的问题状态空间表示用四元组（W，x,y,z）其中：W-猴子的水平问题；x-当猴子在箱子顶上时取x=1；否则x=0；y-箱子的水平位置；z-当猴子摘到香蕉时取1，否则取0。

算符（1）g oto(U)猴子走到水平位置U；（2）p ushbox(V)猴子把箱子推到水平位置V；（3）c limbbox猴子爬上箱顶；（4）g rasp猴子摘到香蕉。

求解过程令初始状态为（a,0,b,0）。

这时，goto(U)是唯一使用的操作，并导致下一状态（U，0，b，0）。

现在有三个适用的操作，若把所有适用操作继续应用于每个状态，就能得到状态空间图。

8.问题归约表示法：问题归约法的基本思想是从目标出发进行逆向推理，通过一系列变换把初始问题变换为子问题集合和子-子问题集合，直至最后归约为一个平凡的本原问题集合。

采用问题归约表示可由下列3部分组成：一个初始问题的描述；一套把问题变换为子问题的操作符；一套本原问题描述。

第二讲知识表示3.状态空间问题归约表示法

如何把初始棋局变换为目标棋局呢？问题的解答 就是某个合适的棋子走步序列，如"左移棋子12， 下移棋子15，右移棋子4，…"等等。
2024/4/3
10
11 9 4 15
13
12
758 6
123 4 567 8 9 10 11 12
13 2 10 14
13 14 15
（a）初始棋局
（b）目标棋局
十五数码难题
2024/4/3
22
3.状态空间表示举例
各种问题都可用状态空间加以表示，并用状态空 间搜索法来求解。 如果能够用一种不同的表示方法来求解用一问题， 也不必感到惊讶。 产生式系统（Production System）
是描述搜索过程的方法。
2024/4/3
23
一个产生式系统由下面三部分组成：
一个总数据库(global database)：它含有与具体任务有 关的信息；随着应用情况的不同，这些数据库可能小 得像数字矩阵那样简单，或许大得如检索文件结构那 么复杂。
2024/4/3
17
后继节点(descendant node)与父辈节点(parent no de)：如果某条弧线从节点ni指向节点nj，那么节 点nj就叫做节点ni的后继节点或后裔，而节点ni叫 做节点nj的父辈节点或祖先。
路径：某个节点序列(ni1,ni2,…,nik)当j=2，3，…， k时，如果对于每一个ni,j-1都有一个后继节点nij存 在，那么就把这个节点序列叫做从节点ni1至节点n ik的长度为k的路径。
隐式表示：节点的无限集合{si}作为起始节点是已 知的。后继节点算符Γ也是已知的，它能作用于任 一节点以产生该节点的全部后继节点和各连接弧 线的代价。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
图是由节点（不一定是有限个的节点）的集合构
成的
注意：在图论中，图的定义中还包括边的集合
有向图和无向图：
无向图：一对节点可能互为后裔，边用线段
来表示
有向图：一对节点用弧线连接起来，并且从一
个节点指向另一个节点 父辈节点或祖先n i
后继节点或后裔nj
对于某一个节点序列
（ni0 , ni2 , … nij , …, nik） 如果每一个节点 nij-1 都有一个 后继节点 nij 存在，则将这一 序列称为从节点 ni0 到 nik 的 长度为 k 的路径。
利用最优化技术中的算法，可以得到结果： x = y = z = 5.0
解释：长、宽、高都等于5米时，体积最大
说明：在计算数学的课程中，主要关心求解的
具体算法
在人工智能中，重点关注两个方面的内容： ①问题的表示（知识的表示）：即要找到问题的一
种合适的表示方法 在人工智能中，我们要涉及到：
➢ 状态空间法 ➢ 问题归约法 ➢ 谓词逻辑法 ➢ 样本向量法
注：有向弧的旁边可以标以具体算符
状态 操作符
节点 有向弧
问题：寻找从初始状态到目标 状态的某个操作符序列
转 化 为
问题：寻找图中初始节点（对应初 始状态）到目标节点（对应于目标 状态）的一条路径
在某些情况下，每个操作符作用、成本是不一
样的，需要引入代价的概念
ni
c (ni , nj) 表示从节点 ni
寻找从初始状态到目标状态的某一个操作符序列
状态空间法的解：
从初始状态变换到目标状态的操作符序列
11 9 4 15 1 3 12 7586 13 2 10 14
1234 5678 9 10 11 12 13 14 15
2. 状态图示法
状态空间法（求解过程）的表示方法：用图来表 示（借助于图论中某些技术）
②问题的求解：从问题表示方法出发，找到一个合 理的办法来求解 在人工智能中，常有的方法有：
➢搜索法 ➢推理法 ➢计算方法
状态空间法
在日常的一些智力游戏（八数码、走八卦阵、走迷 宫等）中，我们采用的策略：试着向前走，如果走 不通，则往后退，不停地试、试、试，直到成功
124 578 36
123 456 78
利用图论的技术，我们要解决两个问题： 第一、找出初始节点到目标节点的一条路径。对应 于寻找初始状态到目标状态的操作符序列 第二、找出初始节点到目标节点的一条代价最小的 路径。对应于寻找将初始状态变换到目标状态所用 操作符代价之和最小的操作符序列
ni0 nik
如果从节点 ni 到 nj 存在 一条路径，则称节点 nj 是 从节点 ni 可到达的节点， 或者称 nj 是 ni 的后裔节 点、称 ni 是 nj 的祖先。
ni 祖先 后裔 nj
当用有向图来表示状态空间法时，对应关系： ➢图中的一个节点对应于某一个状态 ➢图中的一个有向弧对应于某一个算符
要完成某一个具体问题的状态描述，必须完 成三项工作： ①如何描述状态，特别是初始状态 ②操作符集合及其对状态描述的作用 ③如何描述目标状态 即定义好三元状态（S, F, G）中的三个成分
状态空间法：
从某一个初始状态开始，每次施加一个操作符，递 增地建立操作符序列，直到达到目标状态为止
状态空间法的问题：
例如：走步、规则、数学算子、运算 符号等等。
例：描述在坐的同学（续）
状态变量可以有： 年级 班级 姓名 性别 学号 ……
操作符： 入学 正常升级 毕业
例：八数码问题
123 478 算符： 6 5
1、数字的上、下、左、右移动 2、空格的上、下、左、右移动
问题的状态空间：一个表示问题全部可能状
态及其关系的图，它包含了三个集合： 1. 所有可能的问题初始状态集合S 2. 操作符集合F 3. 目标状态集合G
类似地，在人工智能中，一种最基本的求解方法就 是试探搜索法，即，通过在某个可能的解空间（例 如，所有可能的走法）中寻找一个解
这种基于解空间的问题表示和求解方法就是 状态空间法，其基础是状态和算符（算子）
1. 问题状态描述 状态：
描述某一类不同事物间的差别而引入的一
组最少变量q0 ,q1 ,…, qn的有序集合
知识表示方法 －－状态空间法
用计算机技术解决实际问题的一般思路:
实际 问题
问题表达 知识表达 数学建模
结果的解释
求解的方法 或者算法
例：求侧面积为150平方米的体积最大的长方体？
y x
z
设长、宽、高分别为 x, y, z 侧面积为：2(xy + yz + xz) 体积为：xyz 数学模型
max xyz s.t. 2(xy + yz + xz)=150
具体状态：给每一个状态变量一个具体的 值（符号、数值等）。
矩阵形式
q11 ... q 1n
Q
Hale Waihona Puke q m1 ... q mn
例：八数码问题
123
矢量形式的状态表示：
478
1 ,2 ,3 ,4 ,7 ,8 ,6 ,5 ,0 6 5
矩阵形式的状态表示：
1 2 3
4
7
8
6 5 0
算符（操作符）：使问题从一个状态 变换到另一状态的手段。
状态空间记作三元状态：（S, F, G）
例：十五数码问题
11 9 4 15
13
12
7586
13 2 10 14
1234 5678 9 10 11 12 13 14 15
初始状态：左图 目标状态：右图 操作符集合F＝[空格的左移、上移、右移、下移]
可能的求解过程
注：在程序和图示求解过程中，需要规定好操作符 的使用顺序
指向节点 nj （相邻）的
那一段弧的代价
nj
（不相邻的）两个节点
间路径的代价等于连接
该路径的各个节点的所
有弧线的代价之和
k 1
c(ni , ni1)
i0
n0 c(n0,n1)
c(nk-1,nk) nk
引入代价的概念后，我们的问题可能是：
寻找初始节点到目标节点之间的代价最小的 路径
对应的原始问题：寻找从初始状态到目标状 态的操作符代价之和最小的操作符序列
例：描述在坐的同学
变量可以有: 年级 班级 姓名 性别 学号 ……
根据要解决的问题、从 中选择最少的一组变量 例：
✓ 区分哪一个班：年级、 班级
✓ 区分哪一位同学：姓 名、性别、学号
矢量形式： Q=[ q0, q1, …, qn ]T
其中，元素 qi ( i=0, 1,…, n)为集合的分 量，称为状态变量。