在图的表示中，我介绍了如何自定义类来表示图，其中就有启发式距离的表示。爬山法是在DFS上基于启发式距离的一种算法。有点类似于贪婪算法，每一次选择离目标顶点最近的顶点进行遍历，因此只需对DFS的代码增加选取离目标最近顶点即可。
def hill_climbing(graph, start, goal): pathlist=[(start,)] if start == goal: return [start] while len(pathlist) > 0: curr_path = pathlist.pop(0) curr_node = curr_path[-1] new_nodes = graph.get_connected_nodes(curr_node) if len(curr_path) > 1: new_nodes = [node for node in new_nodes if node not in curr_path] if goal in new_nodes: goal_path = curr_path + (goal, ) return list(goal_path) # 根据启发式距离对顶点进行排序 dis = [(graph.get_heuristic(node, goal), node) for node in new_nodes] dis = sorted(dis) # 取距离最近的顶点 new_nodes = [node[1] for node in dis] new_paths = [curr_path + (node,) for node in new_nodes] new_paths.extend(pathlist) pathlist = new_paths else: return []爬山法运行起来要比DFS效率要高，因为省去了一些顶点，但是缺点在于容易陷入局部最优，而不能找到全局最优的路径。
前面的爬山法是在DFS算法基础上改进的，而集束搜索是在BFS算法基础上改进的。BFS会遍历每一层级的所有顶点，而集束搜索会选择前k个离目标顶点的启发式距离最近的顶点进行遍历，k称为集束宽度（beam width）。
def beam_search(graph, start, goal, beam_width): pathlist = [(start,)] if start == goal: return [start] while len(pathlist) > 0: new_paths = [] # 取前beam_width个路径 pathlist = pathlist[:beam_width] while len(pathlist) > 0: curr_path = pathlist.pop(0) curr_node = curr_path[-1] new_nodes = graph.get_connected_nodes(curr_node) if len(curr_path) > 1: new_nodes = [node for node in new_nodes if node not in curr_path] if goal in new_nodes: goal_path = curr_path + (goal,) return list(goal_path) new_paths += [curr_path + (node,) for node in new_nodes] pathlist.extend(new_paths) # sort pathlist dis = [(graph.get_heuristic(path[-1], goal), path) for path in pathlist] dis = sorted(dis) pathlist = [path[1] for path in dis] return []前面的两种算法都是基于启发式距离，而路径最短往往说的是实际的路径长度，分支界定法就是基于实际的路径长度，每次选路径最短进行遍历。因此需要一个方法来统计到目前顶点的累积路径长度：
def path_length(graph, node_names): """ node_names:遍历过的顶点 return:返回累积路径长度 """ i = 0 length = 0 while i < len(node_names) - 1: if graph.are_connected(node_names[i], node_names[i+1]): length += graph.get_edge(node_names[i], node_names[i+1]).length i += 1 return length同时，只需将爬山法的对启发式距离排序的程序改为对所有路径按累积路径长度进行排序即可，代码如下：
def branch_and_bound(graph, start, goal): pathlist = [(start,)] if start == goal: return [start] goal_path = False while len(pathlist) > 0: curr_path = pathlist.pop(0) curr_node = curr_path[-1] new_nodes = graph.get_connected_nodes(curr_node) if len(curr_path) > 1: new_nodes = [node for node in new_nodes if node not in curr_path] if goal in new_nodes and goal_path: new_goal_path = curr_path + (goal,) if path_length(graph, new_goal_path) < path_length(graph, goal_path): goal_path = new_goal_path elif goal in new_nodes and not goal_path: goal_path = curr_path + (goal,) new_paths = [curr_path + (node,) for node in new_nodes] new_paths.extend(pathlist) pathlist = new_paths # 按路径长度对所有路径进行排序 dis = [(path_length(graph, path), path) for path in pathlist] dis = sorted(dis) # 取最短的路径 pathlist = [path[1] for path in dis] if goal_path: return list(goal_path) else: return []A*算法是同时基于累积路径长度和启发式距离的算法，对于程序的编写，我们只需在上述代码中增加启发式距离即可：
def a_star(graph, start, goal): pathlist = [(start,)] if start == goal: return [start] goal_path = False while len(pathlist) > 0 and not goal_path: curr_path = pathlist.pop(0) curr_node = curr_path[-1] new_nodes = graph.get_connected_nodes(curr_node) if len(curr_path) > 1: new_nodes = [node for node in new_nodes if node not in curr_path] if goal in new_nodes: goal_path = curr_path + (goal,) new_paths = [curr_path + (node,) for node in new_nodes] new_paths.extend(pathlist) pathlist = new_paths # 按 累计长度+启发式距离 对所有路径进行排序 dis = [(path_length(graph, path)+graph.get_heuristic(path[-1], goal), path) for path in pathlist] dis = sorted(dis) pathlist = [path[1] for path in dis] if goal_path: return list(goal_path) else: return []A* 算法是其中效率比较高的算法，但其运行的好坏，在于启发式距离设定的好坏。如果get_heuristic(node, goal)始终小于等于节点node到goal的实际距离，则A*算法保证一定能够找到最短路径。但是当get_heuristic(node, goal)的值越小，算法将遍历越多的节点，也就导致算法越慢。
如果get_heuristic(node, goal)大于节点node到goal的实际距离，则A*算法不能保证找到最短路径，不过此时会很快。
