搜索的概念

搜索中需要解决的基本问题：

（1）是否一定能找到一个解。
（2）找到的解是否是最佳解。
（3）时间与空间复杂性如何。
（4）是否终止运行或是否会陷入一个死循环。

搜索策略

（1）育目搜索：在不具有对特定问题的任何有关信息的条件下，按固定的步骤（依次或随机调用操作算子）进行的搜索。

（2）启发式搜索：考虑特定问题领域可应用的知识，动态地确定调用操作算子的步骤，优先选择较适合的操作算子，尽量减少不必要的搜索，以求尽快地到达结束状态。

状态空间的搜索策略

状态空间的表示法

状态空间的图描述

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

缺点：不适用于有负权值的带权图