搜索探寻与问题求解¶
1 搜索基本概念¶
搜索的形式化描述： - 状态（state）是对搜索算法和搜索环境当前所处情形的描述信息，只保留一些对求解模型产生作用的信息 - 动作(action)，从一个状态转移到另一个状态所采取的行为 - 状态转移(state teansition),算法选择了一个动作之后，其所处状态也会发生相应变化，这个过程被称为状态转移 - 路径和代价(path, cost): 路径是一个状态序列，每条路径对应一个代价 - 目标测试(goal test), 目标测试函数用于判断状态s是否为目标状态
可以用一棵树来记录算法所探索的路径，搜索树记录了从根结点出发目前所有探索过的路径。搜索算法可以被看成是一个构建搜索树的过程，从根节点开始，不断展开每个节点的后记结点，知道某个节点通过了目标测试
1.1 搜索算法的评测标准¶
- 完备性： 当问题存在解时，算法能够保证找到一个解，虽然这个解可能不是最优解
- 最优性，搜索算法是否能够保证找到的第一个解是最优解
- 时间复杂度
- 空间复杂度
完备性和最优性刻画了算法找到解的能力以及所求的解的质量，时间复杂度和空间复杂度衡量了算法的资源消耗，通常用\(O\)符号（big O notation）来描述。
一般来说，搜索算法复杂度可能和以下变量有关： - 分支因子\(b\), 即搜索树中每个结点的最大分支数目 - 目标节点到根节点的最前深度\(d\), - 搜索树中路径的最大可能长度\(m\) - 状态空间的大小\(n\)
搜索框架
- 算法中集合\(F\)用于保存搜索树中可用于下一步搜索的所有候选结点，此集合被称为边缘(fridge)集合
- 函数pick_from: 决定了扩展结点的顺序
- 函数successor_nodes: 决定了哪些结点可悲放入边缘集合供后续被扩展
放弃扩展部分结点的做法被称为剪枝(prunning)，其对应的搜索算法被称为剪枝搜索
图搜索-不允许环路的存在
1.2 贪婪最佳优先搜索与A*搜索¶
贪婪最佳优先搜索: 有信息搜索和启发式搜索, 将启发函数作为评价函数
两个重要函数:评价函数与启发函数
