带环检测的一致代价搜索(Uniform Cost Search, UCS) Python实现
罗马尼亚旅行问题
求从城市Arad到城市Bucharest的最短路径
States:表示当前所处的城市;
Actitons:表示在图中进行移动的动作
Initial state:表示初始位置,也就是起点城市
Goal:表示目标城市
算法思想:
一致代价搜索算法,维护三个线性表,边界表(frontier表),已扩展结点表(close表),前驱结点表(pre表)。考虑当前边界中的最小代价的结点(这部分用优先队列实现)对其进行扩展,将其子结点放入边界中,已经扩展过的结点放入close表,从边界表中取出结点的时候进行目标检测,(这里与BFS不同,BFS是在将结点放入边界时就对目标进行检测);在算法执行过程中进行Cycle checking(环检测), 如果结点已经扩展过,则不能放入边界表中。
算法例题:
给定无向图,及图上两个节点,求其最短路径及长度
要求:使用Python实现带环检测的一致代价搜索(uniform-cost)算法
输入(统一格式,便于下周的验收)
第1行:节点数m 边数n(中间用空格隔开,下同);
第2行到第n+1行是边的信息,每行是:节点1名称 节点2名称 边权;
第n+2行开始可接受循环输入,每行是:起始节点名称 目标节点名称。
输出(格式不限)
最短路径及其长度。
Python实现代码:
算法实现中采用了优先队列作为frontier表,将代价最小的结点放在表头。具体的细节可以看代码中的注释。
from cmath import cosfrom email import headerfrom importlib.resources import pathfrom json.tool import mainfrom os import pread, statfrom re import Timport refrom stat import S_IEXECimport heapqclass Node:def __init__(self,state,pre,cost) -> None:self.state = stateself.pre = preself.cost = costedges = [] # 边集closed = [] # 已经扩展过的结点frontier = [] #待扩展的结点path = []def is_in_frontier(state):for f in frontier:if state == f[1]:return Truereturn Falsedef print_path(result): #打印路径while True:path.append(result[1])if result[2] == None:breakresult = result[2]path.reverse()def main():m, n = map(int,input().split(" ")) #"Please enter the number of vertex and edge:"for _ in range(n):n1, n2, w= input().split(" ")w = int(w)edges.append({'c1':n1, 'c2':n2, 'w':int(w)})while True :s_city, d_city = input().split(" ")ans = uniform_cost_search(s_city, d_city) print('Shortest distance from %s to %s is %d' %(s_city,d_city,ans[0]))print_path(ans)print('Path:',path) def uniform_cost_search(start, dest):heapq.heapify(frontier)heapq.heappush(frontier,(0,start,None)) # 元组(heapq不支持字典) 分别是 w, state, prewhile len(frontier):t = heapq.heappop(frontier)if t[1] == dest: # 目标检测return tclosed.append(t[1])for edge in edges:des = ''if edge['c1'] == t[1]: # 由于是无向图,当前的城市可以作为边的起点,也可以作为终点des = edge['c2']elif edge['c2'] == t[1]:des = edge['c1']if des == '':continuechild = {'state': des, 'pre': t, 'w': t[0]+edge['w']} # 将子结点封装成一个字典,分别是子结点的状态, 父亲结点, costif child['state'] not in closed: # 环检测(如果该结点没有被扩展过)heapq.heappush(frontier, (child['w'], child['state'], child['pre']))return Noneif __name__ == '__main__':main()
运行结果:
对于题目中给定的图来说,从a城市走到z城市的最短路径为7,对应的路为a->b->e->d->z。
补充:
在开始学习一致代价搜索算法的时候,我隐隐约约地觉得好像在哪见过这个算法,但是又好像没见过。其实这个算法跟Dijkstra算法很像,其核心内容都很相似,但是又不完全相同。
在Dijkstra算法中,我们用图中的所有顶点初始化顶点表。因此,Dijkstra算法只适用于已知所有顶点和边的显式图。
而一致代价搜索算法从源顶点开始,并逐渐遍历必要的图部分。因此,它适用于显式图和隐式图。
如果觉得《【人工智能】一致代价搜索(Uniform Cost Search UCS) Python实现》对你有帮助,请点赞、收藏,并留下你的观点哦!