最佳优先搜索best-find search

1. 问题

2. 算法

3.代码

1. 问题

考虑下面这个问题：

我们要找到从Arad到Bucharest的路，最好是最短的路：

2. 算法

这是一个无向有环图，

可以采用最佳优先搜索：

最佳优先搜索的算法可以参考维基百科：

伪代码如下:

// Pseudocode for Best First Search
Best-First-Search(Graph g, Node start)1) Create an empty PriorityQueuePriorityQueue pq;2) Insert "start" in pq.pq.insert(start)3) Until PriorityQueue is emptyu = PriorityQueue.DeleteMinIf u is the goalExitElseForeach neighbor v of uIf v "Unvisited"Mark v "Visited"                    pq.insert(v)Mark u "Examined"                    
End procedure

如果你熟悉广度优先搜索，那么上面的代码也没什么难度。

该算法最关键的点是如何构造优先队列中的“优先”策略，一种简单的办法就是选取当前所有访问点中最近的相邻点：

procedure GBS(start, target) is:mark start as visitedadd start to queuewhile queue is not empty do:current_node ← vertex of queue with min distance to targetremove current_node from queueforeach neighbor n of current_node do:if n not in visited then:if n is target:return nelse:mark n as visitedadd n to queuereturn failure

显然上面的BFS是一种贪婪算法，每次选取最优的近邻点是一种“短视”，虽然如此，他仍是一种可行的算法。

该算法最坏的复杂度是 $O(n*logn)$ ，其中n是节点的总数。在最坏的情况我们需要访问所有节点，然后我们构造的堆，每次添加删除元素时复杂度为： $O(logn)$

算法的性能显然与我们选择什么样的代价函数有直接关系。

3.代码

首先是节点类

# -*- coding: utf-8 -*-
"""
Created on Wed Sep  4 15:56:35 2024@author: Paul
"""class Node:def __init__(self,name):self._name=nameself._children=[]def __repr__(self):return 'Node({!r})'.format(self._name)def add_child(self,node):self._children.append(node)def __iter__(self):return iter(self._children)def __eq__(self, other):return self._name==other._namedef Childrens(self):return self._children()

优先队列：

# -*- coding: utf-8 -*-
"""
Created on Wed Sep  4 16:03:33 2024@author: Paul
"""import heapqclass PriorityQueue:def __init__(self):self._queue=[]self._index=0def push(self,item,priority):heapq.heappush(self._queue, (priority,self._index,item))self._index+=1def pop(self):return heapq.heappop(self._queue)[-1]   #弹出itemdef empty(self):              #判断是否为空return True if not self._queue else False

数据节点：

这里只选取到BuCharest城市的数据，该城市是访问Urziceni和Giurgiu后续的点必经之路。

这些城市：

cities=['Arad','Zerind','Oradea','Sibiu','Fagaras','Bucharest',
'Pitesti','Rimnicu','Craiova','Drobeta','Mehadia','Lugoj',
'Timisoara']

cities=['Arad','Zerind','Oradea','Sibiu','Fagaras','Bucharest','Pitesti','Rimnicu','Craiova','Drobeta','Mehadia','Lugoj','Timisoara']Nodes=[Node(name) for name in cities]     #12个节点
dist_mat=[[] for i in range(len(cities))]def addedge(start,end,dist):x=cities.index(start)y=cities.index(end)dist_mat[x].append((y,dist))dist_mat[y].append((x,dist))addedge('Arad', 'Zerind', 75)
addedge('Arad', 'Sibiu', 140)
addedge('Arad', 'Timisoara', 118)
addedge('Zerind','Oradea',71)
addedge('Oradea', 'Sibiu', 151)
addedge('Sibiu', 'Fagaras', 99)
addedge('Sibiu', 'Rimnicu',80)
addedge('Fagaras', 'Bucharest', 211)
addedge('Bucharest', 'Pitesti', 101)
addedge('Pitesti', 'Rimnicu', 97)
addedge('Pitesti', 'Craiova', 138)
addedge('Craiova', 'Rimnicu', 146)
addedge('Craiova', 'Drobeta', 120)
addedge('Drobeta', 'Mehadia', 75)
addedge('Mehadia', 'Lugoj', 70)
addedge('Lugoj', 'Timisoara', 111)for index,city in enumerate(Nodes):for t in dist_mat[index]:city.add_child(Nodes[t[0]])

每个节点与其相邻节点关系如下：

Node('Arad') =>[Node('Zerind'), Node('Sibiu'), Node('Timisoara')]
Node('Zerind') =>[Node('Arad'), Node('Oradea')]
Node('Oradea') =>[Node('Zerind'), Node('Sibiu')]
Node('Sibiu') =>[Node('Arad'), Node('Oradea'), Node('Fagaras'), Node('Rimnicu')]
Node('Fagaras') =>[Node('Sibiu'), Node('Bucharest')]
Node('Bucharest') =>[Node('Fagaras'), Node('Pitesti')]
Node('Pitesti') =>[Node('Bucharest'), Node('Rimnicu'), Node('Craiova')]
Node('Rimnicu') =>[Node('Sibiu'), Node('Pitesti'), Node('Craiova')]
Node('Craiova') =>[Node('Pitesti'), Node('Rimnicu'), Node('Drobeta')]
Node('Drobeta') =>[Node('Craiova'), Node('Mehadia')]
Node('Mehadia') =>[Node('Drobeta'), Node('Lugoj')]
Node('Lugoj') =>[Node('Mehadia'), Node('Timisoara')]
Node('Timisoara') =>[Node('Arad'), Node('Lugoj')]

最后BFS如下：

# -*- coding: utf-8 -*-
"""
Created on Wed Sep  4 16:37:37 2024@author: Paul
"""from node import Node
from priorityqueue import PriorityQueuedef BFS(mat,start,dest):q=PriorityQueue()q.push(start, 0)visited=[start]while not q.empty():u=q.pop()print(u)if u==dest:return Trueelse:for city,dist in mat[Nodes.index(u)]:child=Nodes[city]if child not in visited:visited.append(child)q.push(child, dist)return False

运行BFS结果如下:

Node('Arad')
Node('Zerind')
Node('Oradea')
Node('Timisoara')
Node('Lugoj')
Node('Mehadia')
Node('Drobeta')
Node('Craiova')
Node('Pitesti')
Node('Bucharest')

访问路径如下：