什么是问题求解Agent？
问题求解Agent三个例子
无信息搜索：宽度优先搜索（性质，汉诺塔问题）、一致代价搜索（按照路径代价排序的宽度优先搜索，性质）、深度优先搜索（性质）、深度受限搜索、迭代加深搜索、双向搜索
有信息搜索：启发式搜索（f（n）代价估计函数，h（n）启发式函数，是代价估计函数的一部分），例子：贪婪搜索，A*搜索
问题求解Agent
问题求解Agent是一种基于目标的Agent，利用目标信息做动作决策，通过搜索解决问题
对于某些NP完全或者NP难问题，只能通过搜索来求解
基本概念：
解（solution）：到达目标的动作序列
搜索（search）：寻找到达目标的动作序列的过程
问题形式化（problem formulation）：给定目标，决定要考虑的动作与状态
简单问题求解Agent算法：
function SIMPLE-PROBLEM-SOLVING-AGENT(percept) returns an action
persistent: seq, an action sequence, initially empty
state, some description of the current world state
goal, a goal, initially null
problem, a problem formulation
action, the most recent action, initally none
state<-UPDATE-STATE(state, percept)
if seq is empty then
goal<-FORMULATE-GOAL(state)
problem<-FORMULATE-PROBLEM(state,goal)
seq<-SEARCH(problem)
if seq = failure then return a null action
action<-FIRST(seq)
seq<-REST(seq)
return action
问题形式化的五个要素
1）Initial state初始状态：即智能体出发时的状态
2）Actions动作：该智能体可执行的动作
3）Transition model转换模型：描述每个动作将一种状态转化为另一种状态
4）Goal test目标测试：确定一个给定的状态是否是目标状态
5）Path cost路径代价：每条路径所分配的数值代价，或每个动作的代价
状态空间
状态空间可以形式化地定义为：初始状态，动作和转换模型。
状态空间可以用图来表示，其中节点表示状态，连接表示动作。
状态空间的一条路径是由一系列动作连接的一个状态序列。
例子：
1、真空吸尘器世界
初始状态：智能体只能在两个房间中的其中一个，每个房间都有可能是干净的或者不干净的，所以总共有 种可能的状态任何一种状态都有可能作为初始状态
动作：左移L，右移R，吸尘S，其中无效动作是在左房间左移，在右房间右移，在干净房间吸尘，而有效动作是在左房间右移，右房间左移，干净房间吸尘
转换模型：
无效动作不会导致状态转换
目标测试：是否所有的房间内部干净
路径代价：等于路径的步数（若每一个动作代价都为1）
2、八数码问题（滑块问题类是NP完问题）
初始状态：8个数字滑块每一个占据一个方格，空格位于剩下的一个方格，任意一个状态都可以作为初始状态
动作：最简单的形式化将动作定义为空格的上下左右方向的移动，当然也存在有效动作和无效动作
转换模型：给定一个状态以及动作，返回空格滑块移动后的状态
目标测试：检查状态是否与目标布局相符
路径代价：路径的步数（若每一个动作的代价都为1）
3、八皇后问题
两种形式化方法：增量形式化，全形态形式化（局部搜索算法）
增量形式化I
初始状态：第1到第8个皇后在棋盘上任意摆放，为一个状态，
动作：添加一个皇后到任意一个空格
转换模型：将一个皇后添加到指定空格，再返回该棋局
目标测试：8个皇后都在棋盘上，并且不会相互攻击
路径代价：步数（若每步代价都为1）
增量形式化II（相比于I，不可将皇后摆放在可被攻击的位置）
初始状态：对于 ，保证第1到第 列的皇后互相之间不会攻击，则初始状态为
动作：移动第n列的皇后，使之不与第n列之前的皇后相互攻击
转换模型：在第n列遵守不被前n-1列皇后攻击到的原则，摆放一个皇后
增量形式I的状态空间中的状态个数为 ，远大于增量形式II的状态空间中的状态个数2057（通过程序枚举可算出）
问题求解算法的性能
完备性：当问题有解，能否保证找到解
最优性：搜索策略能否找到最优解
时间复杂度：找到解需要花费多长时间
空间复杂度：执行搜索过程中需要多少内存
即该搜索策略没有超出问题定义之外的附加信息，所能做的就是生成后继节点，并区分一个目标状态是否为目标状态
无信息搜索策略通过其选择节点拓展的顺序来定义
评价方法：1）完备性：是否能找到解；2）最优性：是否能找到最优解；3）时间复杂度；3）空间复杂度
时间复杂度和空间复杂度的描述：b——搜索树的嘴的分支因子，d——最浅的解的深度，m——搜索树的最大深度
宽度优先搜索
采用先进先出（FIFO）的队列来存储待拓展节点，新拓展的节点总是排在相对旧的节点的后面
图的宽度优先搜索算法
function BREADTH-FIRST-SEARCH(problem) returns a solution, or failure
node<-a node with STATE = problem.INITIAL-STATE
PATH-TEST = 0
frontier<- a FIFO queue with node as only element
explored<-an empty set
loop do
if EMPTY?(frontier)then return failure
node<-POP(frontier)
add node.STATE to explored
for each action in problem.ACTIONS(node,STATE) do
child<-CHILD-NODE(problem, node, action)
if child.STATE is not int explored or frontier then
if problem.GOAL-TEST(child.STATE)then return SOLUTION(child)
frontier<-INSERT(child,frontier)
复杂度分析
时间复杂度：
空间复杂度：
指数级的复杂度代价是巨大的
例子：汉诺塔问题，将 个 块移动到另一根柱子上并且要求保持金字塔装，时间复杂度为
一致代价搜索
拓展最低代价的未拓展节点，使用优先队列，按照路径代价排序，路径代价低的优先出队
算法
function UNIFORM-FIRST-SEARCH(problem) returns a solution, or failure
node<-a node with STATE = problem.INITIAL-STATE, PATH-TEST = 0
frontier<- a priority queue ordered by PATH-COST, with node ad the only element
explored<- an empty set
loop do
if EMPTY?(frontier) then return failure
node<-POP(frontier)
if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)
add node.STATE to explored
for each action in problem.ACTIONS(node.STATE) do
child<-CHiLD-NODE(problem,node,action)
if chile.STATE is not in explored of frontier then
frontier<-INSERT(child.frontier)
else if child.STATE is in frontier with higher PATH-COST then
replace that frontier node with child
复杂度分析
令 为最优解的代价， 为最小的动作代价
时间复杂度：
空间复杂度：
深度优先搜索
总是拓展搜索树当前边缘节点集中最深的节点，即使用LIFO队列，最新生成的节点最早被选择拓展
深度受限搜索
时间复杂度为 ，空间复杂度是
迭代加深的深度优先搜索
不断加深深度受限搜索的深度限制
时间复杂度
双向搜索
同时运行两个搜索，一个从初始状态向前搜索，一个从目标状态向后搜索——希望它们在中间某点相遇，此时搜索终止
只适用于目标状态明确的问题
无信息搜索策略对比
什么是有信息搜索？
有信息搜索利用问题定义之外的信息，定义评价函数或者启发式函数作为搜索策略而进行搜索。
最佳优先搜索是一类有信息搜索策略，贪婪搜索和A*搜索是其中两个具体例子。
贪婪搜索的评价？
贪婪搜索的评价函数就是启发式函数，即 。
不保证完备性和最优性。
不保证完备性是因为可能陷入两点之间的局部循环
A*搜索与贪婪搜索的区别？
A*搜索的评价函数为 ，其中 是到达该节点的最小代价， 是该节点到达目标节点的估计代价。
A*搜索具有完备性和最优性。
为什么A*搜索的最优性？
1）启发式 的可采纳性：对于评价函数 ，对于节点 与终点 ， ，即从n到终点的估计距离不大于实际距离。
启发式 的一致性（单调性）对于每个节点 以及其通过行动 生成的后继节点 ，有 ，即节点与其后继节点的到终点的估计距离的差不大于两者之间的实际距离。
因此一致性可以推出可采纳性
2）若启发式是可采纳的，则A*算法的树搜索版本是最优的；若启发式是一致的，则A*算法的图搜索版本是最优的
A*搜索的完备性？
设最优解路径代价为 ，则对于A*算法拓展你的所有节点都有
若所有评价小于等于 的节点都会被拓展，且这些节点有限，则可保证完备性
例子——八数码难题的两种启发式
对于八数码难题，给出两个启发式， 错位的数码总数， 当前状态与目标状态的曼哈顿距离（hanmming距离）。
若对于所有的n，都有 ，则称 优于 ，因而更适合搜索
内存受限的启发式
递归最佳优先搜索（RBFS）
如何设计启发式函数
1）考虑松弛问题
2）子问题模式数据库