【人工智能】一致代价搜索（Uniform Cost Search, UCS） Python实现_uniform-cost search (ucs),

带环检测的一致代价搜索（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 cos
from email import header
from importlib.resources import path
from json.tool import main
from os import pread, stat
from re import T
import re
from stat import S_IEXEC
import heapq
class Node:
    def __init__(self,state,pre,cost) -> None:
        self.state = state
        self.pre = pre
        self.cost = cost
edges = [] # 边集
closed = [] # 已经扩展过的结点
frontier = [] #待扩展的结点
path = []
def is_in_frontier(state):
    for f in frontier:
        if state == f[1]:
            return True
    return False

def print_path(result): #打印路径
    while True:
        path.append(result[1])
        if result[2] == None:
            break
        result = 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, pre
    
    while len(frontier):
        t = heapq.heappop(frontier)
        if t[1] == dest:  # 目标检测
            return t
        closed.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 == '':
                continue
            child = {'state': des, 'pre': t, 'w': t[0]+edge['w']}  # 将子结点封装成一个字典，分别是子结点的状态， 父亲结点， cost
            if child['state'] not in closed:  # 环检测（如果该结点没有被扩展过）
                heapq.heappush(frontier, (child['w'], child['state'], child['pre']))
    return None

if __name__ == '__main__':
    main()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

运行结果：

对于题目中给定的图来说，从a城市走到z城市的最短路径为7，对应的路为a->b->e->d->z。

补充：

在开始学习一致代价搜索算法的时候，我隐隐约约地觉得好像在哪见过这个算法，但是又好像没见过。其实这个算法跟Dijkstra算法很像，其核心内容都很相似，但是又不完全相同。

在Dijkstra算法中，我们用图中的所有顶点初始化顶点表。因此，Dijkstra算法只适用于已知所有顶点和边的显式图。

而一致代价搜索算法从源顶点开始，并逐渐遍历必要的图部分。因此，它适用于显式图和隐式图。