一。状态空间盲目搜索
1. 广度优先搜素(Breadth-First-Search) 2.深度优先搜素(Depth-First-Search)
二。状态空间启发搜索
BFS像一个胆小的孩纸,遇到困难会尝试每一种解决方法,DFS,像一个胆大的孩纸,遇到困难会选择一种解决方法进行实践,直到解决或者实践失败。这两种方法都不适合人工智能。
适用于人工智能的启发性搜索-A*搜索:
启发性信息是指那种与具体问题求解过程有关的,并可指导搜索过程朝着最有希望方向前进的控制信息。
估价函数:
用来估计节点重要性的函数。估价函数f(n)被定义为从初始节点S0出发,约束经过节点n到达目标节点Sg的所有路径中最小路径代价的估计值。它的一般形式为:
f(n)=g(n)+h(n)
其中,g(n)是从初始节点S0到节点n的实际代价;h(n)是从节点n到目标节点Sg的最优路径的估计代价。