启发式搜索算法1 - 最佳优先搜索算法

启发式搜索算法有什么优势？

对于复杂问题的盲目搜索，常用广度优先搜索和深度优先搜索这两种盲目搜索算法，极大极小值和Alpha-beta剪枝算法是在盲目搜索过程中，通过剪枝避开一些不可能的结果，从而提高效率。

如果搜索能够智能化一点，通过一些特殊的信息能够避免机械式盲目搜索，就可以提高搜索算法的效率，这就是启发式搜索。

启发式搜索(Heuristically Search)又称为有信息搜索(Informed Search)，它是利用问题拥有的启发信息来引导搜索，达到减少搜索范围、降低问题复杂度的目的，这种利用启发信息的搜索过程称为启发式搜索。从定义知道启发式搜索策略是通过某些信息指导搜索向最有希望获取最佳解的方向前进，听起来像突然拿到了一张藏宝地图，根据藏宝图的信息开启了寻找宝藏之旅。根据经验，大部分人也没有找到什么宝藏，所以说启发式搜索策略是极易出错的，通过有限的信息来预测下一步的搜索过程实在太难，不然程序员都可以写个程序预测股票，趟着赚钱，不用上班了。那么能找到非常有价值的启发信息是最为重要，它应该能够降低搜索工作量，而又不牺牲找到最优解的保证。

最佳优先搜索算法（Best First Search）

图的算法中使用的广度优先搜索和深度优先搜索，它们都不考虑任何成本的盲目搜索路径，现在认识了启发式搜索算法，就要对此进行优化，首先来认识这个最佳优先搜索（Best First Search），它是在广度优先搜索的基础上的启发式搜索算法，用估价函数对将要被遍历到的点进行估价，然后选择代价小的进行遍历，直到找到目标节点或者遍历完所有点，算法结束。这样说起来有些抽象，通过下面例子如下图，通过最佳优先搜索来寻找结果。
在这里插入图片描述
想找到从【A】结点到【F】结点的最短路径，如果用广度优先搜索来求解，整个过程会以A为中心点，发散式地寻找，首先会遍历结点【B,D,G】，然后是【H】结点，再到结点【E,C】，最后才发现【F】结点，一共搜索了7次。现在改为最佳优先搜索，设置的估价函数是选取路径代价最小值，分析过程如下表所示。
在这里插入图片描述
估价函数计算的当前路径代价最小值作为信号，引导搜索选取下一个结点，如第一次选择【D】结点，因为它的值为2是当前最小值，同理第二次选择了【B】结点，最后一次选择了【C】结点，仅通过4次搜索就找到了从【A】到【F】的路径，比广度优先搜索少了3次，确实提高了效率，现在用代码来表示以上算法分析过程。

def bfs_path(graph, start, target):def find_min_path(queue):# 估计函数：寻找代价最小的路径temp_queue = [] # 记录每条路径的总代价for path in queue:total = 0for node in path:total += node[1]temp_queue.append(total)# 寻找最小代价的路径path_index = 0for i in range(len(temp_queue)):if temp_queue[i] < temp_queue[path_index]:path_index = i# 返回此路径，并且在优先队列移除return queue.pop(path_index)visited = [] # 保存已经访问的结点# 优先队列来保存访问结点的成本，初始值为开始位置priority_queue = [[(start,0)]]# 特殊情况，开始位置与目标位置相同if start == target:return "开始位置就是目标位置"  while priority_queue: # 尝试所有可能，直到队列为空print('优先队列:', priority_queue)# 选择优先队列里的一条路径path = find_min_path(priority_queue)node = path[-1]if node[0] not in visited: # 没有访问过neighbours = graph[node[0]] # 获取这个结点的邻接结点for neighbour in neighbours:# 遍历所有邻接结点，创建新的路径添加到优先队列里面if neighbour[0] not in visited:new_path = list(path)new_path.append(neighbour)if neighbour[0] == target:return new_pathpriority_queue.append(new_path)visited.append(node[0]) # 结点已经访问# 没有找到路径return "两个结点没有路径相连"

可以和2.7.3小节图的遍历中广度优先搜索的程序作对比，程序基本思路是一致的，只是在选择下一条路径的时候，不是盲目地选取第一条路径，而是通过估价函数find_min_path()来选择下一条路径。现在通过上面的例子来测试程序，这里使用邻接列表来表示有权无向图。

graph = {"A": [("B",3), ("D",2), ("G",12)],"B": [("A",3), ("H",9)],"C": [("D",4),("F",3)],"D": [("A",2), ("C",4), ("E",7)],"E": [("D",7),("F",1)],"F": [("C",3),("E",1)],"G": [("A",12)],"H": [("B",9)],
}
print("求解得到路径:", bfs_path(graph, "A", "F"))
# -----------结果-----------------
优先队列: [[('A', 0)]]
优先队列: [[('A', 0), ('B', 3)], [('A', 0), ('D', 2)], [('A', 0), ('G', 12)]]
优先队列: [[('A', 0), ('B', 3)], [('A', 0), ('G', 12)], [('A', 0), ('D', 2), ('C', 4)], [('A', 0), ('D', 2), ('E', 7)]]
优先队列: [[('A', 0), ('G', 12)], [('A', 0), ('D', 2), ('C', 4)], [('A', 0), ('D', 2), ('E', 7)], [('A', 0), ('B', 3), ('H', 9)]]
求解得到路径: [('A', 0), ('D', 2), ('C', 4), ('F', 3)]