搜索求解策略
搜索求解策略
搜索的概念
搜索中需要解决的基本问题：
- 是否一定能找到一个解。
- 找到的解是否是最佳解。
- 时间与空间复杂性如何。
- 是否终止运行或是否会陷入一个死循环。
搜索策略
育目搜索：在不具有对特定问题的任何有关信息的条件下，按固定的步骤依次或随机调用操作算子) 进行的搜索。
启发式搜索：考虑特定问题领域可应用的知识，动态地确定调用操作算子的步骤，优先选择较适合的操作算子，尽量减少不必要的搜索，以求尽快地到达结束状态。
状态空间的搜索策略
状态空间的表示法
状态空间的图描述
eg. 旅行商问题，最短哈密尔顿回路
盲目的图搜索策略
回溯策略
PS(path states)表：保存当前搜索路径上的状态。如果找到了目的
NPS(new path states)表：
NSS(no solvable states)表：
宽度优先搜索策略
宽度优先搜索(breadth-first search，广度优先搜索)：以接近起始节点的程度(深度)为依据，进行逐层扩展的节点搜索方法。
深度优先搜索策略
启发式搜索策略
启发式图搜索策略：重排OPEN表
种类：A，A*
问题简单时，不需要用启发式信息
使用启发式的情况：
一个问题由于存在问题陈述和数据获取的模糊性，可能会使他没有一个确定的解
指数级增长的情况，如 TPS
井字棋
h(n)启发函数：
A*算法：启发函数h(x)小于等于h*(n)时，被称为A*算法
如果某问题有解，则利用A*一定可以搜索到最优解
最短路径算法
单源最短路最好的算法，稳定最短路
迪杰斯特拉
需要堆结构
类似Prim
缺点：不适用于有负权值的带权图