确定性知识表示法
知识的概念：一种普遍说法是：知识是人们在改造客观世界的实践中积累起来的认识和经验。
知识的分类：按知识的确定性分为确定性知识和不确定性知识。确定性知识是指其真假是可以明确表示的知识。其表示方法包括：谓词逻辑表示法，产生式表示法，语义网络表示法，框架表示法等。
知识表示：是对知识的描述。用一些约定的符号把知识编码成一组可以被计算机直接识别、并便于系统使用的数据结构。
知识系统是一种拥有知识并且可以使用知识进行推理的智能系统。—>由概念知道两大要素是：知识表示、知识推理。
产生式表示法产生式表示法是一种知识的表示方法，所表示的知识是确定性知识。产生式表示法已经成为人工智能中应用最多的一种知识表示模式。尤其在专家系统方面应用广泛。
产生式的表示的基本原则（方法）产生式表示法非常容易表示事实和规则。
事实的产生式表示：什么是事实？事实是：断言一个语言变量的值或断言多个语言变量之间关系的陈述句，
产生式中：事实可以使用三元组或四元组来表示。
对于确定性事实用一个三元组表示：
(对象，属性，值)或者(关系，对象1，对象2)对象是语言变量。这种表示方式可以在机器内部用一张表来表示。
例如：如事实“老李年龄是35岁”，便写成（Lee,age,35）事实“老李、老张是朋友”，可写成（friend,Lee,Zhang）
规则的产生式表示规则是：规则描述的是事物间的因果关系。含义是：如果…则…
规则的产生式表示形式常称为产生式规则，简称产生式，或称规则。
规则的基本形式：IFTHEN前件是该规则可否使用的先决条件。前件由单个事实或者多个事实的逻辑组合构成。后件是一组结论或操作。指出当前件满足的时候，应该推出的结论或应该执行的操作。r1（规则序号）：ifTHEN产生式表示的特性优点：
自然性：产生式表示法使用如果…则…形式表示知识，与人类相像，直观，自然，便于推理。
模块性：每条规则都是一个独立的知识单元，描述前提与结论之间的一种静态关系，其正确性能够独立的得到保证。各个规则之间不相互调用。
有效性：产生式表示法除了表示确定知识外，稍作变形可以表示不确定性知识。
缺点：
效率低下。在产生式表示中，各规则之间的联系必须以综合数据库为媒介。其求解过程是反复的“匹配–冲突消解–执行”过程。
先用规则前提与综合数据库中的已知事实匹配。
从规则库中选用可用规则。
当有多条规则可用的时候，按照一定的策略进行冲突消解。然后执行选中的规则。
对于具有结构关系或层次关系的知识，用产生式难以将其表示。
人工智能导论 第二章 搜索技术
2.1搜索的基本概念搜索：一种求解问题的一般方法
问题求解的基本方法：搜索法、归约法、归结法、推理法及产生式
基本问题：1、是否一定能找到一个解
2、找到的是否是最佳解
3、时间和空间复杂度
4、是否会终止运行or死循环
主要过程：1、从初始或目的状态出发，并将其作为当前状态
2、扫描操作算子集，将适用当前状态的一些操作算子作用于当前状态而得到新的状态，并建立指向父节点的指针
3、检查所生成的新状态是否满足结束状态。若满足，反向得出解答路径；否则将新状态定义为当前状态返回2
概念术语搜索方向（1）数据驱动：初始状态出发正向搜索
（2）目的驱动：从目的状态出发逆向搜索
（3）双向搜索找到汇合点
盲目搜索与启发式搜索（1）盲目搜索：不针对特定问题任何有关信息，按照固定步骤搜索
（2）启发式搜索：考虑特定问题可应用的知识，动态确定算子，优先选择合适算子，减少步骤
状态表示系统状态、事实等叙述性知识的一组变量或数组
操作表示引起状态变化的过程型知识的一组关系或函数
2.2状态空间的搜索策略状态空间：利用状态变量和操作符号，标识系统或问题的有关知识的符号体系，三元组（S、F、G）
S：状态集合F：操作算子的集合G：目的状态集合
求解路径从S0到G结点的路径，状态空间的一个解是一个有限的操作算子序列
表示方法：图描述八数码问题的图描述
TSP问题的图描述
2.3盲目搜索回溯策略从初始状态出发不停试探路径，直到到达目的或“不可解节点”。若遇到不可解节点就回溯到路径中最近的父节点上，查看该节点是否还有其他子节点未被扩展。
算法：
1、PS表：保存当前搜索路径上的状态，如果找到目的，PS就是解路径上的状态有序集
2、NPS表：新的路径状态表，包含等待搜索的状态，后裔状态还未被搜索到
3、NSS表：不可解状态集，列出找不到接替路径的状态。如果在搜索中扩展出他的元素，可立即排除
图搜索算法（DFSBFS最好优先搜索）的回溯思想
（1）用NPS使算法可以回归到任意状态
（2）用NSS避免算法重新搜索无解路经
（3）PS表中记录当前搜索路径状态，满足目的时可以将其作为结果返回
（4）为避免死循环，需要对子状态及性能检查，看是否在3张表中
广度优先搜索策略例题：机器人积木动作序列问题
算子MOVE（X，Y）的先决条件：
1、被搬动积木顶必为空
2、若Y是积木，Y顶部也必须为空
3、同状态下操作算子运用次数不得多于1次
深度优先搜索策略深度优先搜索中，当搜索到某一状态，其所有子状态及子状态的后裔状态必须先于该状态的兄弟状态被搜索。并且为了保证找到解，应选择合适的深度限制或不断加大深度限制值，反复搜索。
深度优先搜索并不能保证第一次搜索到某个状态时的路径是到这个状态的最短路径，如果算法多次搜索到同一个状态时应当保留最短路径
盲目搜索——代价树搜索代价树搜索：用于寻找最小代价路径问题，是推广版的BFS（如果权值都一致的话就是BFS）
比较图搜索与树搜索：
最短路径的图搜索：搜索算法认为一个状态只能对应搜索图中的一个节点
最短路径的树搜索：同一个状态可以多次出现在树中，相同状态可以同时出现在搜索中代表不同节点
实际操作中可以从搜索树构造搜索图搜索算法，从边缘集合中取出那些会导致搜索出现重复状态的节点。
搜索图是动机的角度，搜索树是实现的角度。
例题：卒子穿阵问题
2.4启发式图搜索启发式策略启发：关于发现和发明操作算子及搜索方法的研究
在状态空间搜索中，启发式被定义成一系列操作算子，并能从状态空间中选择最有希望到达问题解的路径。
启发式策略：利用问题相关的启发信息进行搜索
运用启发策略的两种基本情况1、一个问题由于在问题陈述和数据获取方面的模糊性，可能使它没有确定解
2、虽有可能有确定解，但是状态空间特别大，生成扩展的状态数会随搜索深度指数级增长
启发信息和估价函数求解问题中利用的大多是非完备的启发信息
1、求解问题系统不能知道与实际问题有关的全部信息，无法知道所有状态空间，无法用一套算法求解所有问题
2、虽然理论上存在求解算法，但工程实践中不是效率太低就是无法实现
启发信息分类1、陈述性2、过程性
3、控制性（没有任何控制性知识作为搜索依据，所以每一步都是随意的；有充分的控制知识作为依据，因而搜索的每一步选择都是正确的）
估价函数：估计代搜索节点的有希望程度，并依次给它们拍定次序
估价函数f（n）从初始节点经过n节点到达目的节点的路径的最小代价估计值f=g+h（g越大先用宽度优先，h越大表示启发能力越强）
总结：利用知识来引导搜索，减少搜索范围，降低问题复杂度
启发信息的强度可以分为：强：降低搜索工作量，可能导致找不到最优解
弱：导致工作量加大，极限情况下可以盲目搜索，但可能找到最优解
引入启发知识，在保证找到最优解的情况下尽可能缩小搜索范围，提高搜索效率
例题：八数码的估价函数
A搜索算法启发式图搜索算法的基本特点：寻找并设计一个与问题相关的h（n）及构出f（n）=g+h，然后以f（n）的大小来排列待扩展状态的次序，每次选f值最小者进行
open表：保留所有已生成而未扩展的状态
closed表：记录已扩展过的状态
进入open表的状态是根据其估值的大小插入到表中合适的位置，每次从表中优先取出启发估价函数值最小的状态进行扩展。
每次重复时，A搜索算法从open表中取出第一个状态。如果该状态满足目标条件，则算法返回到该状态的搜索路径。
如果open表的第一个状态非目的状态，则算法通过一系列操作算子进行相应操作来产生其子状态。若某子状态在open&closed表中出现过，即该状态再一次被发现时 ，通过刷新祖先状态的历史记录，使算法可能找到更短路径。
A搜索算法接着open表中每个状态的估价函数值，按照值大小重新排序，将值最小的状态放在表头，使其第一个被扩展。
例题：利用A搜索算法求解八数码问题的搜索树，估价函数定义为f=d+w
d：为状态深度，每步代价为单位代价。w：以“不在位”的将牌数作为启发信息的量度。
（A&A*搜索树）
A*搜索算法及其特性分析若某一问题有解，A*一定能搜索到解且一定能得到最优解。
A算法没有对估价函数f（n）作任何限制，实际上估价函数对搜索过程也十分重要
A*就是对估价函数加上一些限制后得到的一种启发式搜索算法
可容性：启发函数不会高估从节点n到终止节点所应付出的代价
一致性：三角不等式h(n)
人工智能六种知识表示法，你必须要了解
3.谓词逻辑表示
虽然命题逻辑(propositionallogic)能够把客观世界的各种事实表示为逻辑命题,但是它具有较大的局限性,不适合于表示比较复杂的问题。谓词逻辑(predicatelogic)允许表达那些无法用命题逻辑表达的事情。
逻辑语句,更具体地说,一阶谓词演算(firstorderpredicatecalculus)是一种形式语言，其根本目的在于把数学中的逻辑论证符号化。如果能够采用数学演绎的方式证明一个新语句是从那些已知正确的语句导出的，那么也就能断定这个新语句也是正确的。
4.语义网络表示
语义网络是知识的一种结构化图解表示,它由节点和弧线或链线组成。节点用于表示实体、概念和情况等,弧线用于表示节点间的关系。
语义网络表示由下列4个相关部分组成：
(1)词法部分决定词汇表中允许有哪些符号,它涉及各个节点和弧线。
(2)结构部分叙述符号排列的约束条件,指定各弧线连接的节点对。
(3)过程部分说明访问过程,这些过程能用来建立和修正描述,以及回答相关问题
(4)语义部分确定与描述相关的(联想)意义的方法,即确定有关节点的排列及其占有物和对应弧线。
5.框架表示
心理学的研究结果表明,在人类日常的思维和理解活动中,当分析和解释遇到新情况时,要使用过去经验积累的知识。这些知识规模巨大而且以很好的组织形式保留在人们的记忆中。例如,当走进一家从未来过的饭店时,根据以往的经验,可以预见在这家饭店将会看到菜单、桌子、服务员等。当走进教室时,可以预见在教室里可以看到椅子、黑板等。
人们试图用以往的经验来分析解释当前所遇到的情况,但无法把过去的经验一一都存在脑子里,而只能以一个通用的数据结构的形式存储以往的经验。这样的数据结构称为框架(frame)。框架提供了一个结构,一种组织。在这个结构或组织中,新的资料可以用经验中得到的概念来分析和解释。因此,框架也是一种结构化表示法。
6.过程表示
语义网络和框架等知识表示方法,均是对知识和事实的一种静止的表达方法,称这类知识表达方式为陈述式知识表达,它强调的是事物所涉及的对象是什么,是对事物有关知识的静态描述,是知识的一种显示表达形式。而对于如何使用这些知识,则通过控制策略来决定。
与知识的陈述式表示相对应的是知识的过程(procedure)表示。所谓过程表示就是将有关某一问题领域的知识,连同如何使用这些知识的方法,均隐式地表达为一个求解题的过程。它所给出的是事物的一些客观规律,表达的是如何求解问题。知识的描述形式就是程序,所有信息均隐含在程序之中。从程序求解问题的效率上来说,过程式表达的效率要比陈述式表达高得多。但因其知识均隐含在程序中,因而难以添加新知识和扩充功能,适用范围较窄。返回搜狐，查看更多