搜索算法(1)——启发式搜索1(GBFS)

小何同学冷泡茶

发布时间 2022.03.09阅读数 3165 评论数 0

启发式搜索（Heuristically Search)

又叫做有信息搜索(Informed Search)，该算法利用问题的启发信息(所求解问题相关的辅助信息)引导搜索过程，来减少搜索范围，降低问题复杂度。

这篇博文主要介绍两种启发式搜索算法：
贪婪最佳优先搜索——Greedy Best-First Search(GBFS)
A*
其中，GBFS是一种很基础简单的搜索算法，其基本思想——将节点表按照距目标的距离进行排序，再以节点的估计距离为标准选择待扩展节点。搜索问题解法的时候，“目光短浅”，每一步算法会先看所有邻近节点，选择最低开销。（比如寻路算法中，GBFS只看对当前城市来说，最近的下一个城市，但是不考虑总距离消耗），其有如下的弊端：

不一定最优(不考虑总距离)
容易陷入死循环
有可能一直沿着一条道，但是这条道到不了终点... （不完备性)

启发式搜索的辅助信息一般有两类：
Evaluation Function 评价函数 $f(n)$ : 评估总cost;---寻路任务中，从当前节点n出发，根据评价函数来选择后续节点。
当前最小cost函数 $g(n)$ ；考虑从开始到目前的cost；
后续最小cost函数 $h(n)$ ; ---寻路任务中，计算从节点n到目标节点之间所形成路径的==估算的==最小代价值，这里将两点之间的直线距离作为启发函数。

GBFS的评价函数： $f(n)=h(n)$ ，以寻路算法为例，其可以帮我们回答两个问题：① 从A出发，有前往B的路径与否？② 从A出发，哪条往B的路径最短？
以下面这个经典的寻路算法为例来实现GBFS:

图片来源：Artificial Intelligence A Modern Approach by Stuart J. Russell and Peter Norvig

我们需要找到从Arad到Bucharest的最短路线。其中路线的辅助信息已经给出。GBFS的实现，要求我们使用一个priority queue优先队列，所谓优先队列，其一般不在遵循队列的先入先出原则，元素按照其自然顺序进行排序，或者根据构造队列时提供的Comparator进行排序。一般分为以下两种情况：
1️⃣最大优先队列——无论入队顺序，当前最大的元素优先出队；
2️⃣最小优先队列——无论入队顺序，当前最小的元素优先出队；
pq队列的头值排序规则最小的那个元素，若多个元素都是最小值，则随机选择一个即可。同时，pq是一个无界队列，随着不断向优先级队列添加元素，其容量会自动扩容。
在GBFS的算法中，其主要过程如下：
1️⃣建立一个已经排序好的初始节点表A（从小到大）；
2️⃣若A为空集，退出，给出失败信号；
3️⃣a取为A的首节点（优先队列首节点原则)，并在A中删除节点a，讲其放入已访问节点列表;
4️⃣若a为目标节点，退出，给出成功信号；否则，将a的后续节点加到A中，记为A'，对A‘中的节点按距目标的估计距离排序，并返回2.

代码部分如下：

首先是heuristics.txt文件，其给出了辅助信息。

Arad 366
Bucharest 0
Craiova 160
Dobreta 242
Eforie 161
Fagaras 178
Giurgiu 77
Hirsova 151
Iasi 226
Lugoj 244
Mehadia 241
Neamt 234
Oradea 380
Pitesti 98
Rimnicu_Vilcea 193
Sibiu 253
Timisoara 329
Urziceni 80
Vaslui 199
Zerind 374

input.txt就是输入信息，其每一行的形式：

city1 city2 dist

23
Arad Sibiu 140
Arad Timisoara 118
Arad Zerind 75
Bucharest Fagaras 211
Bucharest Giurgiu 90
Bucharest Pitesti 101
Bucharest Urziceni 85
Craiova Dobreta 120
Craiova Pitesti 138
Craiova Rimnicu_Vilcea 146
Dobreta Mehadia 75
Eforie Hirsova 86
Fagaras Sibiu 99
Hirsova Urziceni 98
Iasi Neamt 87
Iasi Vaslui 92
Lugoj Mehadia 70
Lugoj Timisoara 111
Oradea Zerind 71
Oradea Sibiu 151
Pitesti Rimnicu_Vilcea 97
Rimnicu_Vilcea Sibiu 80
Urziceni Vaslui 142
Arad
Bucharest

代码部分：

import networkx as nx
import matplotlib.pyplot as plt
import Queue as Q
 
def getPriorityQueue(list):
	q = Q.PriorityQueue()
	for node in list:
		q.put(Ordered_Node(heuristics[node],node))
	return q,len(list)

def greedyBFSUtil(G, v, visited, final_path, dest, goal): 
	if goal == 1:
		return goal
	visited[v] = True
	final_path.append(v)
	if v == dest:
		goal = 1
	else:
		pq_list = []
		pq,size = getPriorityQueue(G[v])
		for i in range(size):
			pq_list.append(pq.get().description)
		for i in pq_list:
			if goal != 1:
				#print "current city:", i
				if visited[i] == False :
					goal = greedyBFSUtil(G, i, visited, final_path, dest, goal)
	return goal

def greedyBFS(G, source, dest, heuristics, pos): 
	visited = {}
	for node in G.nodes():
		visited[node] = False
 	final_path = []
	goal = greedyBFSUtil(G, source, visited, final_path, dest, 0)
	prev = -1
	for var in final_path:
		if prev != -1:
			curr = var
			nx.draw_networkx_edges(G, pos, edgelist = [(prev,curr)], width = 2.5, alpha = 0.8, edge_color = 'black')
			prev = curr
		else:
			prev = var
	return

class Ordered_Node(object):
	def __init__(self, priority, description):
		self.priority = priority
		self.description = description
		return
	def __cmp__(self, other):
		return cmp(self.priority, other.priority)

def getHeuristics(G):
	heuristics = {}
	f = open('heuristics.txt')
	for i in G.nodes():
		node_heuristic_val = f.readline().split()
		heuristics[node_heuristic_val[0]] = node_heuristic_val[1]
	return heuristics



#takes input from the file and creates a weighted graph
def CreateGraph():
	G = nx.Graph()
	f = open('input.txt')
	n = int(f.readline())
	for i in range(n):
		graph_edge_list = f.readline().split()
		G.add_edge(graph_edge_list[0], graph_edge_list[1], length = graph_edge_list[2]) 
	source, dest= f.read().splitlines()
	return G, source, dest



def DrawPath(G, source, dest):
	pos = nx.spring_layout(G)
	val_map = {}
	val_map[source] = 'green'
	val_map[dest] = 'red'
	values = [val_map.get(node, 'blue') for node in G.nodes()]
	nx.draw(G, pos, with_labels = True, node_color = values, edge_color = 'b' ,width = 1, alpha = 0.7)  #with_labels=true is to show the node number in the output graph
	edge_labels = dict([((u, v,), d['length']) for u, v, d in G.edges(data = True)])
	nx.draw_networkx_edge_labels(G, pos, edge_labels = edge_labels, label_pos = 0.5, font_size = 11) #prints weight on all the edges
	return pos



#main function
if __name__ == "__main__":
	G, source,dest = CreateGraph()
	heuristics = getHeuristics(G)
	pos = DrawPath(G, source, dest)
	greedyBFS(G, source, dest, heuristics, pos)
	plt.show()