本文主要是介绍最佳优先搜索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是一种贪婪算法,每次选取最优的近邻点是一种“短视”,虽然如此,他仍是一种可行的算法。
该算法最坏的复杂度是 ,其中n是节点的总数。在最坏的情况我们需要访问所有节点,然后我们构造的堆,每次添加删除元素时复杂度为:
算法的性能显然与我们选择什么样的代价函数有直接关系。
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')
访问路径如下:
算法每次选取最近的节点,因此我们没有得到最优解,要想得到最优解,需要对算法进行改造,使之称为启发式算法,我会在后续章节介绍一二。
参考链接:
BFS维基百科:Best-first search - Wikipedia
geek for geeks: Best First Search (Informed Search) - GeeksforGeeks
这篇关于最佳优先搜索best-find search的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!