AI agent 搜索算法

agent 分类

reflec(reactive) agent: 只会对特定的条件作出反应 类似 if else有internal state的agent：记住周围环境的变化 有内部状态goal_based agent：以目标为导向执行动作utility_based agent：满足以上条件时 找到最优解

环境类型

fully/partially observable 可以获得所有的环境还是部分环境deterministic/stochastic 下一个状态由当前状态和行为决定还是随机episodic分布/sequential连续：是否需要考虑历史信息static/dynamic: 在机器人判断时 环境静止还是动态discrete离散/continuous: 有限数量的

定义一个搜索问题

1.initial state 初始点2 transition:operators 可以进行的操作successor function：s(x)从x进行一步之后可以达到的状态3.goal state 目标点4 path cost  用于评估一系列transitions的成本1和2共同定义一个状态空间

问题的解

a solution to a problem is an action sequence thatleads from the initial state to a goal state即：一个问题的解就是 从初始状态到目标状态的行动序列最优解就是所有解里 路径成本最小的解

为什么要搜索算法

状态空间太大 所以需要搜索算法 相当于一种求解模式

搜索问题的数据结构

搜索树的每个节点 有以下成分:state 状态parent 父节点action 父节点生成该即诶单时采取的行动path-cost 从初始节点到该节点的路径消耗depth 树深度

求解算法的性能

completeness完备性 当问题有解时 能否找到解time complexity 时间复杂度 找到解要花多长时间space complexity 空间复杂度 执行过程中需要多少内存optimality 最优性 是否能找到最优解

无信息搜索策略

无信息指的是  无法知道当前位置到目标节点的情况 不知道是变远了 还是 变近了BFS 广度优先搜索每次总是扩展深度最浅的节点 这可以通过将未扩展的节点组织成fifo 先进先出 队列来实现找到的是最浅的目标节点每个状态都有b个后继状态 解的深度为d时间复杂度 b^d 空间复杂度b^d 完备性 trueuniform cost search 一致代价搜索一致代价搜索也是一种图搜索算法 扩展的是路径消耗g(n)从初始状态到当前状态的路径消耗最小的节点n

用uniform search的结果是1. s2. s-a 1s-b 5s-c 183. 发现a最小s - a - g 13 但并不是当前遍历最小的 所以继续搜索 扩展b4. s - b - g 10为当前最小cost 完成搜索dfs深度优先搜索深度优先总是扩展搜索树的当前边缘节点集中最深的节点搜索直接推到最深层如果最深层节点扩展完了 就回溯到下一个还有未扩展节点的深度稍浅的节点。

遍历顺序  1->2->4->8->5->3->6->7深度限制搜索设置最大深度迭代加深的深度优先 iterative deepening searchids = dfs + bfs

走这张图

深度0A，没了深度1ABCE，没了深度2A, B, D, F,这时该往回走C, G, E,完了， F（F撞了）深度3A, B, D, F, E,这时该往回走C, G,完了， E, F, B（这三个撞了）在这个搜索策略中，一个具有深度限制的深度优先搜索算法会不断重复地运行，并且同时放宽对于搜索深度的限制，直到找到目标状态。我们可以估计一个深度，例如2，让DFS搜索前2步所能到达的节点，如果搜不到，也不继续搜索，直接返回，然后搜索其它的节点。如果找不到，就放款限制，让深度变为4，即搜索前4步内所能到达的节点，若没找到，就让深度变为8、16、32。依次类推，直到找到终点。这样我们就可以给出IDDFS的大致框架了

有信息的搜索策略

有信息搜索 informed search = 启发式搜索启发式搜索比无信息搜索更加高效启发函数:h(n) 估算当前state和目标state之间的距离存储结构:全部用优先队列最佳优先搜索 best - first - search节点是基于评估函数f(n)被选择扩展的f(n) 可自己定义贪婪搜索 greedy searchf(n) = h(n) 使用h(n) 对node进行排列 选择小的进行扩展A* search评估函数 f(n) = g(n) + h(n)g(n)是从出发位置到当前位置的cost