一、启发式搜索

1.人工智能中的搜索

在海量信息源中利用问题求解器，加上一定的约束条件和额外信息即可找到问题所对应的答案。

1.寻找最短路径为例

寻找出路径最短，时间最少，价钱最经济的路径

搜索算法的形式化描述：状态，动作，状态转移，路径，测试目标。

状态：从原问题转化出的问题描述。

动作：从当前时刻所处的状态转移到下一时刻所处状态所进行的操作。一般而言这些操作都是离散的。

状态转移：对面某一时刻对应状态进行某一种操作后，所能够到达的状态。

路径：一个状态序列。该状态序列被一系列操作所连接。

测试目标：评估当前状态是否为所求解的目标状态。

2.搜索算法：启发式搜索（有信息搜索）

在搜索的过程中利用与所求解问题相关的辅助信息，其代表算法为贪婪最佳优先搜索和A*搜索。

有信息搜索要定义如下辅助信息：

贪婪最佳优先搜索：评价函数f（n）=启发函数h（n）

根据上图所知，从当前Arad出发，选择相邻的后续节点并找出其最短路径。上图找出的最短直线距离是：Arad→Sibiu→Fagaras→Bucharest。此为贪婪最佳优先算法。

不足之处：

为了解决上述问题，提出了A*算法。

3.搜索算法：A*搜索