一、问题的状态和状态空间
(二). 问题的特征分析 问题求解步骤是否可撤回 (1).忽略。 (2).可撤回。如走迷宫。 (3).不可撤回 ，如下棋，决策等问题，要提前 分析每步走一步后会导致的结果，不可回头重 来，这需要使用规划技术。
一、问题的状态和状态空间
(二). 问题的特征分析 问题全域是否可预测 有些问题的全域可预测，即该问题空间 有哪些状态是可以预计的。如水壶问题 有些问题的全域不可预测，如变化环境 下机器人的控制。
第2讲 问题求解与搜索方法
知识回顾
(一).从拟人思维角度的定义：
什么是人工智能
(二).从理性思维角度的定义
人工智能的产生及 主要学派 人工智能的技术特 征 人工智能应用系统
(三).从拟人行为角度的定义 (四).从理性行为角度的定义
知识回顾
(一).符号主义学派
什么是人工智能
(二).联结主义学派
人工智能的产生及 主要学派 人工智能的技术特 征 人工智能应用系统
2 1 7 8 6 3 4 5 1 8 7 6 2 3 4 5 八数码问题估计函数
初始状态
目标状态
三、启发式搜索方法
(一). 启发式信息的表示 搜索方向的选择 正向搜索：从初始状态向目标状态搜索。 逆向搜索：从目始状态向初标状态搜索。 双向搜索：正向搜索与逆向搜索结合的搜索。
如图示
三、启发式搜索方法
三、启发式搜索方法
(一). 启发式信息的表示 启发式函数的表示方法 估价函数用来估计节点重要性的函数。
三、启发式搜索方法
(一). 启发式信息的表示 启发式函数的表示方法 八数码问题， 例：八数码问题，评价函数 f(n) = d(n) + W(n) d(n): 节点 的深度 节点n的深度 的深度; W(n):与目标相比 错位的数字数目 与目标相比, 与目标相比 错位的数字数目;
一、问题的状态和状态空间
(二). 问题的特征分析 问题要求的是最优解还是较满意解， 解得要求不同，采用的策略也不同。一 般说来，最佳路径问题的计算比次优路 径问题的计算要困难。
主要内容
问题的状态和状态空间 盲目的搜索方法 启发式搜索方法 图搜索策略 博弈
二、盲目的搜索方法
盲目搜索是按预定的控制策略进行，在 搜索过程中获得的中间信息不用来改进 控制策略
二、盲目的搜索方法
(二). 深度优先搜索(Depth-first-Search)
如用深度优先搜索解决八数码难题
优点：节省大量的时间和空间。 缺点：不一定能找到解。因为在深度无限搜索树的情况 下，最坏的情况可能是不能停机。
深度优先搜索算法描述
1 把初始状态节点So放入OPEN表中； 2 若OPEN表为空，则搜索失败，退出。 3 取OPEN表中前面第一个节点放入CLOSD表中，令该节 点为x并以顺序编号n; 4 若目标状态节点Sg=x，则搜索成功，结束。 5 若x不可扩展，则转至步骤2； 6 扩展x，将其所有子节点配上指向x的返回指针依次放入 首部，转至步骤2。 OPEN表的首部 首部
小结
问题的状态和状 态空间 盲目的搜索方法 启发式搜索方法 图搜索策略 博弈
(一). 如何定义状态空间及其 搜索 (二). 问题的特征分析
小结
问题的状态和状 态空间 盲目的搜索方法 启发式搜索方法 图搜索策略 博弈
(一).宽度优先搜索 (二).深度优先搜索 (三).分支有界搜索 (四).迭代加深搜索
(三).专家系统 (四).智能软件Agent (五).数据挖掘和知识发现
主要内容
问题的状态和状态空间 盲目的搜索方法 启发式搜索方法 图搜索策略 博弈
一、问题的状态和状态空间
(一). 如何定义状态空间及其搜索 人工智能中的搜索技术的应用 （如机器人足球赛 对弈） 解空间：所求问题的解构成的状态集。 状态(State)：在人工智能中，状态是为了描述某些不同事物间的 差别而引入的一组最小变量q0,q1,…,qn的有序集合。 其形式表示为：Q=(q0,q1,…,qn)。其中，每个qi称为状态变量。 给定每个分量的一组值，就得到一个具体的状态。(如对弈中的状 态)
一、问题的状态和状态空间
(一). 如何定义状态空间及其搜索 问题状态空间法的基本算法： (1)、根据问题定义相应的状态空间，确定出状态的一 般表示，它含有相关对象各种可能的排列。 (2)、规定一组操作(算子)，能够作用于一个状态后过 渡到另一种状态。 (3)、决定一组搜索策略，使得能够从初始状态出发， 沿某个路径到达目标状态。
(三).行为主义学派
知识回顾
(一).利用搜索
什么是人工智能
(二).利用知识
人工智能的产生及 主要学派 人工智能的技术特 征 人工智能应用系统
(三).利用推理 (四).遵循有限合理原则 (五).利用抽象
知识回顾
(一).问题求解系统
什么是人工智能
(二).自然语言理解和处理系统
人工智能的产生及 主要学派 人工智能的技术特 征 人工智能应用系统
OPNE表用于存放刚 表用于存放刚 生成的节点。 生成的节点。
宽度优先搜索算法描述
1 把初始状态节点So放入OPEN表中； 2 若OPEN表为空，则搜索失败，退出。 3 取OPEN表中前面第一个节点放在CLOSED表中，令该 节点为x并以顺序编号n; 4 若目标状态节点Sg=x，则搜索成功，结束。 CLOSED表用于存放将要扩展或以被 5 若x不可扩展，则转至步骤2； 扩展的节点。 6 扩展x将其所有字节点配上指向x的指针依次放入 OPEN表的尾部转至步骤2。
一、问题的状态和状态空间
(一). 如何定义状态空间及其搜索 操作符或算子：
使问题从一种状态变化为 另一种状态的手段如五子 棋游戏
operator Q1
状态1
Q2
状态2
一、问题的状态和状态空间
(一). 如何定义状态空间及其搜索 问题的状态空间(State Space)。是一个表示 该问题全部可能状态及其关系的集合。 它包括问题初始状态集合S、操作符集合F和目 标状态集合G。 状态空间可表示为三元组(S,F,G),其中S属于 Q,G属于Q。
三、启发式搜索方法
(二). 几种最基本的搜索策略 最佳优先搜索(Best-first-Search) 基本步骤：(由爬山法改造而来) (1) 生成第一个可能的解。若是目标，则停止；否则转下 一步。 (2) 从该可能的解出发，生成新的可能的解集。 (2.1) 用测试函数测试新的可能解集中的元素，若是 解，则停止；若不是解，转下一步。 (2.2) 将新生成的解集加入到原可能解集中。 (3) 从解集中挑选最好的元素作为起点，再转(2.2)。
二、盲目的搜索方法
(三). 分支有界搜索(Branch-and-Bound Search) 也是一种深度优先搜索，但是每个分支都规定 了一个统一的搜索深度，搜索到这个深度后， 如果没有找到目标便自动退回到上一层，继续 按深度优先搜索。
分支有界搜索算法描述
1 把So放入OPEN表中，置So的深度d(So)=0; 2 若OPEN表为空，则搜索失败，退出。 3 取OPEN表中前面第一个节点放入CLOSD表中，令该节点 为x并以顺序编号n; 4 若目标状态节点Sg=x，则搜索成功，结束。 5 若x的深度d(x)=dm,或x无子节点，则转至步骤2； 6 扩展x，将所有子节点xi配上指向x的返回指针后依次 放入OPEN表中前部，置d(xi)=d(x)+1,转至步骤2。
二、盲目的搜索方法
(一). 宽度优先搜索(Breadth-first Search)
宽度优先搜索，又称为广度优先搜索，是一种逐层次 搜索的方法。在第n层的节点没有全部扩展并考察之前， 不对第n+1层的节点进行扩展。 用宽度优先搜索解决八数码难题 优点：若问题有解，则可找到最优解 缺点：效率低，组合爆炸问题难以解决
主要内容
问题的状态和状态空间 盲目的搜索方法 启发式搜索方法 图搜索策略 博弈
三、启发式搜索方法
前面讨论的方法都是盲目的搜索方法,即都没有 利用问题本身的特性信息。 启发式搜索要用到问题自身的某些特性信息,以 指导搜索朝着最有希望的方向前进
三、启发式搜索方法
(一). 启发式信息的表示 为什么要使用启发式搜索 (1).人们善于利用一些线索来帮助自己选择搜索方向，这些 线索被称为启发式(Heuristic)信息。(如案件侦探)。 (2).现实问题往往只需一个解，而不是求最优解或全部解。 (3).启发式信息可以避免某些领域里的组合爆炸问题。 如：计算机下棋问题
作业
3.1阐述广度优先搜索、深度优先搜索、 有界深度优先搜索和迭代加深搜索各自 的特点及复杂度。（P94）
第2讲 问题求解与搜索方法
郭建方
4课时
主要内容
问题的状态和状态空间 盲目的搜索方法 启发式搜索方法 图搜索策略 博弈
四、图搜索策略
(一). 一个通用的图搜索算法 1、问题的分解与等价变换 基本思想： 当一问题较复杂时，可通过分解或变换， 将其转化为一系列较简单的子问题，然后通过 对这些子问题的求解来实现对原问题的求解。
一、问题的状态和状态空间
(一). 如何定义状态空间及其搜索 问题状态空间法：是基于解空间的问题表示和求解方法。 问题状态空间法的基本思想:（1）将问题的已知条件看成 状态空间的初始状态(S)；将问题中要求达到的目标看成 状态空间中的目标状态(G)；将问题中其他可能发生的情 况看成状态空间的任一状态。（2）设法在状态空间寻找 一条路径，由初始状态出发，能够沿着这条路径达到目标 状态。
小结
问题的状态和状 态空间 盲目的搜索方法 启发式搜索方法 图搜索策略 博弈
(一).启发式信息的表示 (二).几种最基本的搜索策略
思考题
修道士(Missionaries)和野人 和野人(Cannibals)问题 简称 问题(简称 修道士 和野人 问题 简称M-C问 问 题)。 。 设在河的一岸有三个野人、三个修道士和一条船， 设在河的一岸有三个野人、三个修道士和一条船，修道士想 用这条船把所有的人运到河对岸，但受以下条件的约束： 用这条船把所有的人运到河对岸，但受以下条件的约束： 一是修道士和野人都会划船，但每次船上至多可载两个人； 一是修道士和野人都会划船，但每次船上至多可载两个人； 二是在河的任一岸，如果野人数目超过修道士数， 二是在河的任一岸，如果野人数目超过修道士数，修道士会 被野人吃掉。 被野人吃掉。 如果野人会服从任何一次过河安排， 如果野人会服从任何一次过河安排，请规划一个确保修道士 和野人都能过河，且没有修道士被野人吃掉的安全过河计划。 和野人都能过河，且没有修道士被野人吃掉的安全过河计划。 修道士与野人