一、最佳优先搜索

根据评价函数选择表现的最佳的节点进行扩展

最佳优先搜索 best-first-search 算法

不同的方法有不同的评价函数

 

启发函数，标记h(x)

h(n)=从节点n到目标的最低耗散估计值

 

启发函数是额外信息的一种最普通的形式

二、贪婪最佳优先搜索

最先扩展离目标节点最近的节点

需要检查重复状态

三、A*搜索

将  到达节点的耗散g(n) 与

从该节点到目标节点的消耗h(n)  结合起来

f(n)=h(n)+g(n)

 

剪枝：不需要检验就直接把它们的可能性排除

三、存储限制搜索算法

1-递归最佳优先搜索 RBFS

2-MA*

四、局部搜索算法

1-爬山法搜索

   用一系列爬山搜索来避免局部极大值

2-模拟退火

3-遗传算法