文档介绍：人工智能
( 问题求解基本原理及搜索技术)
问题求解基本原理
问题求解:在给定条件下,寻求一个能解决某类问题且能在有限步骤内完成的算法。
问题求解特征:
传统软件: ①求解的问题是能够用数学精确描述的良结构的问题(如,解方程); ②计算机执行的繁杂的统计计算任务一般不能看成是人工智能活动。
AI软件:①求解的是不可直接用数学模型描述的所谓不良结构问题(如,几何证明、求不定积分、逻辑演算等),通常需要采用弱方法进行搜索求解;② AI程序中符号的内涵不仅局限于数值计算和数据处理中的一般数据信息,应表现人类进行推理所需要的各种知识。
问题求解基本原理
一、问题求解的基本方法
二、搜索技术
问题求解基本原理
问题求解方法:
基于状态空间的问题求解方法
基于问题空间的问题求解方法
基于博弈搜索的问题求解方法
问题实例
桌上固定了 3 根柱子,按 1,2,3 次序排例。有 n 个大小全不一样大的盘子d1,…,dn ,按从小到大,小的在上的次序依次插在第一根柱子上,要把这 n 个盘子全部搬到第三根柱子上,每次只许搬一个,任何时候都不允许把大盘子放在小盘子上面,问该如何搬法。设 n = 3,该如何搬法?
1 2 3 1 2 3
梵塔问题
基于状态空间的问题求解方法
(1,1,1)→(1,1,2)
(1,1,1)→(1,1,3)
(1,1,2)→(1,3,2)
。。。。。
状态合法变换规则(满足约束条件):
状态定义-(i大, j中, k小):
设向量下标分别表示大盘、中盘、小盘;向量值分别表示盘子所在柱子的编号。
状态描述- 大盘在第 i 根柱子上;中号盘在第 j 根柱子上,小号盘在第 k 根柱子上。
基于问题空间的问题求解方法
问题:如何将 i 柱子上的 m 个盘子搬到 k 柱子上?
将 i 柱子上的 m – 1 个盘子搬到 j 柱子上;
将 i 柱子上的第 m 个盘子搬到 k 柱子上;
将 j 柱子上的 m – 1 个盘子搬到 k 柱子上。
问题描述:
问题(a, b, c): 将 b 柱子上的 a 个盘子搬到 c 柱子上。
问题分解合法规则:
(3,1,3)--〉(2,1,2)(1,1,3)(2,2,3)
。。。。。。
基于问题空间的问题求解方法
状态空间法有关概念
状态空间法:
从问题的初始状态出发,通过一系列的状态变换找到目标状态的问题求解方法。
状态:描述问题中事物形状或状况的符号或数据结构。
状态空间:所有状态的全体构成的集合;用四元组(S, S0, O, G) 表示:
S: 非空状态子集,S0 = 初始状态(非空)。
G: 非空目标状态子集。
O: 操作算子集合,一个状态合法转换为另一个状态的描述规则
问题求解过程:隐含求一个普通有向图,节点- 状态,边–算子
搜索空间:问题求解过程中到达过的所有状态(节点)的集合。
状态空间法有关概念
状态空间、搜索空间及解径的关系:
问题的解(解径):初始状态到目标状态通路上的每一条规则(或状态)构成序列,称为解径。解不唯一。
S0 R1 S2 R2 Sk ….. Rk G
问题有解:从代表初始状态 s 节点出发, 存在一条通向目标节点的路径。