在没有额外信息的情况下，探讨了各种盲目搜索算法，因为问题中只给出了约束条件。这些算法在达到目标状态之前会遍历许多不同的状态。这些搜索策略的缺点是时间复杂度非常差，因此使用这些策略解决现实世界问题是不合理的。
这个问题可以通过提供一些启发式信息来解决，即“通过暴露获得的经验”，从而引入了启发式搜索策略。这些算法承诺可以快速解决任何复杂问题，并且时间复杂度更低。
启发式搜索策略使用一些启发式函数来选择节点，以确保最有希望的路径到达目标。给搜索问题提供更多关于问题的信息的最流行方式是使用启发式函数。这是从特定节点n到目标状态的成本估计。任何问题特定的函数都是可以接受的（任意的和非负的）。如果n是目标节点，则H(n) = 0。
本文将介绍两种启发式搜索策略：最佳优先搜索算法和A*搜索算法。
启发式广度优先搜索遵循贪婪的方法进行状态转换以达到目标。在这里，为每个节点维护一个评估函数(f(n))，它提供了成本估计。想法是每次都扩展具有最低f(n)的节点。这里的评估函数有一个启发式函数h(n)组件，即f(n) = h(n)。因此，看起来最接近目标的节点将被扩展。这个算法的实现是使用一个优先队列，按照每个节点的评估函数进行排序。伪代码如下：
function Best_First_Search(problem) {
node = problem.initial_state;
frontier = priority queue with node as the only element;
explored = empty set;
loop(until goal state is found) {
if(frontier == empty)
return failure;
node = frontier.pop();
add node to explored_set;
if(node == problem.goal_state)
return path from Initial state up to the node;
else
generate successors of the node;
if(successors not in frontier and not in explored_set)
add successor to the priority queue;
}
}
最佳优先搜索算法的特性：
（b是分支因子，m是搜索空间的最大深度。）
A*搜索策略是最广泛使用的一种策略，因为它保证了最优解。这个想法是避免扩展已经昂贵的路径。与最佳优先搜索类似，它使用评估函数(f(n))来评估路径中的每个节点（状态）。
f(n) = g(n) + h(n)，其中g(n)是从初始状态到当前节点的实际成本，h(n)是从当前节点到目标状态的估计成本。A*算法成功地找到了问题最短路径的解决方案，因此它是状态空间搜索中最广泛接受的解决方案。A*搜索的解的最优性取决于选择的启发式函数的可接受性。下面将详细介绍。
A*搜索策略的算法步骤：
这个算法的时间复杂度是b^d。空间复杂度是b^d。（其中b是树的分支因子，d是解决方案节点的深度。）
解决方案的最优性取决于可接受的启发式。那么，什么是可接受的启发式呢？
如果对于每个节点，h(n)小于或等于g(n)（这里，g(n)是到达目标状态的实际成本），则启发式函数h(n)是可接受的。因此，一个可接受的启发式永远不会高估到达目标的成本。它总是对找到到达目标节点的最佳路径持乐观态度。如果h(n)对于A*算法是可接受的，得到问题的最优解。