人工智能 一种现代的方法 第3章 通过搜索进行问题求解

我的代码，基于VS2017（https://download.csdn.net/download/lvxiangyu11/10949775）

本章基于目标Agent的一种，问题求解Agent（Problem-solving Agent）。使用原子表示，要素化结构化。

无信息搜索：算法出了问题定义本身没有任何其他信息。

有信息搜索，利用给定的知识引导能够更有效地找到解。

• 问题求解Agent

形式化，搜索，执行

1. 1. 良定义的问题及解

一个问题5个组成部分

• • • 初转状态
    • 描述可能的行动 （ { Go(Sibiu) , Go(Timisoara) , Go(Zerind)} ）
    • 对每个行动的描述­­­­­——转移模型
    • 目标测试
    • 路径耗散  （行动a从状态s走到s‘的单步耗散用c(s, a, s’)表示）

所有路径耗散值最小的解为最优解

• 1. 问题形式化
• 问题实例
  1. 玩具问题：滑块问题，八皇后问题，Knuth
  2. 现实世界问题：TSP，VLSI布线，机器人导航，自动装配
• 通过搜索求解

frontier：已生成未拓展

closed：已拓展

1. 1. 搜索算法基础

STATE：空间中的状态。

PARENT：产生该节点的父节点

ACTION：父节点产生该节点的行动

PATH-COST：代价（路径耗散）

1. 1. 问题求解算法的性能

完备性：问题有解时，这个算法是否能保证找到这个解。

最优性：搜索策略能否找到最优解

时间&空间复杂度

• 无信息搜索策略

问题引入

罗马尼亚度假问题作为例子，讲解下面6种算法

1. 宽度优先搜索（BFS）

先根再叶，再根再叶。

基于节点深度的非递减函数，宽搜最优。

时间复杂度：O(bd+1) b = 一个非叶节点的子节点数 d = 层数

复杂度太高不实用。

1. 一致代价搜索（Uniform-cost Search）

每一步的行动代价都相等时，BFS是最优的。

              一致代价搜索扩展的是路径消耗g(n)最小的结点。

特点：

1. 按路径代价对对接进行排序
2. 目标检测应用于被选择拓展时
3. 如果边缘中的节点有更好的路径到达该节点，则会引入一个测试。

不关心步数，只关心路径总代价。

1. 深度优先搜索（DFS）

先叶再根，再叶再根。

1. 深度受限搜索（Depth-limited Search）

深度受限

1. 迭代加深的深度优先搜索（Iterative Deepening Search）

在一致代价搜索确保最优化的同时，避免大内存需求。

不断加深路径代价界限，代替不断增加的深度限制。——迭代加长搜索

1. 双向搜索（Bidirectional Search）

分别从源头和目标搜索。

对比

       

• 启发式搜索策略

补充罗马尼亚度假问题信息

代价函数值

有信息搜索

最佳优先搜索的评价函数f(n) 由启发函数（heuristic function）构成

h(n) = 结点n到目标结点的最小代价路径的代价估计值

1. 贪婪最佳优先搜索（Greedy Best-first Search）

使用启发式，f(n) = h(n)

1. A*算法 缩小总体评估代价

f(n) = g(n) + h(n)

保证最优性

1. 存储受限的启发式搜索

迭代加深A*（截断值改成f(n)）

递归最佳优先搜索RBFS(节点回退时将回退路径上的点写上最短的代价)

以上两种回来带冗余路径

MA*，SMA*（可以重新生成以往的子树）

 

1. 学习（以促）搜索

元状态空间中的每一个状态都要捕捉一个程序的内部状态，程序是在目标层状态空间搜索。元状态空间的每一个行动都是改变内部状态的计算步骤。

学习的目标时减小问题求解的总代价，计算开销和路径代价之间取得最佳性价比。

1. 启发式函数

同问题有多种启发函数

1. 1. 启发式精确度对性能的影响。

有效分支因子b*，设总结点为N，解的深度为d，b*为深度为d的标准搜索树为了能包括N+1个点所必须的分支因子。即，N+1 = 1 + b^1 + b^2 + … +b^d

 

1. 1. 从松弛问题出发设计可采纳的启发式

减小了行动限制的问题称为松弛问题。松弛问题的状态空间图是原有状态空间的超图，因为减少限制导致图中边的增加。

1. 1. 从子问题出发设计可采纳的启发式——模式数据库

子问题的最优解代价是完整问题的解代价的下界。存储每一个子问题代价的实例，作为启发式用。两个不想叫的子问题的代价之和是整个问题的下界（不相交的模式数据库）

1. 1. 从经验中学习启发式

线性回归方程等，略