人工智能 3.ppt

人工智能 3.ppt人工智能
( 问题求解基本原理及搜索技术)
问题求解基本原理
问题求解:在给定条件下,寻求一个能解决某类问题且能在有限步骤内完成的算法。
问题求解特征:
传统软件: ①求解的问题是能够用数学精确描述的良结构的问题(如,解方程); ②计算机执行的繁杂的统计计算任务一般不能看成是人工智能活动。
AI软件:①求解的是不可直接用数学模型描述的所谓不良结构问题(如,几何证明、求不定积分、逻辑演算等),通常需要采用弱方法进行搜索求解;② AI程序中符号的内涵不仅局限于数值计算和数据处理中的一般数据信息,应表现人类进行推理所需要的各种知识。
问题求解基本原理
一、问题求解的基本方法
二、搜索技术
问题求解基本原理
问题求解方法:
基于状态空间的问题求解方法
基于问题空间的问题求解方法
基于状态空间的问题求解方法
1、状态空间表示法
状态空间表示法是人工智能中最基本的形式化方法,也是讨论问题求解技术的基础。状态空间表示法是用“状态”和“算符”来表示问题的一种方法。
1、状态:状态是描述问题求解过程中任一时刻状况的数据结构,一般用一组变量的有序组合表示:SK=(SK0,SK1,…)当给每一个分量以确定的值时,就得到了一个具体的状态。
2、算符:算符引起状态中某些分量发生变化,从而使问题由一个状态变为另一个状态的操作称为算符。当到达目标状态时,由初始状态到目标状态所用算符的序列就是问题的一个解。
1、基于状态空间的问题求解方法
3、状态空间:由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间。状态空间是一个四元组:(S,O,S0,G),其中S为状态集合,O为算符集合,S0为初始状态集合,G为目标状态集合。
4、状态空间的图示形式称为状态空间图。其中,节点表示状态;有向边(弧)表示算符
问题实例
例1 二阶梵塔问题。
设有1、2、3三根钢针,在1号钢针上穿有A、B两个金片,A小于B,A位于B的上面。要求把这两个金片全部移到另一根钢针上,而且规定每次只能移动一片,任何时刻都不能使B位于A的上面。
解1:A、B都搬到3上:
A(1,2)
B(1,3)
A(2,3)
解2:A、B都搬到2上:
A(1,3)
B(1,2)
A(3,2)