罗马尼亚地图问题中的一致费用搜索

Question

我已经写了这段代码。这是统一成本搜索的代码。我必须找到阿拉德和布加勒斯特之间的道路。我的问题是，我的代码给出了正确的总成本，即418。但我不知道如何找到导致这一代价的途径。感谢您的帮助。 从队列导入优先级队列

class Graph:
    def __init__(self):
        self.edges={"Arad":["Zerind","Timisoara","Sibiu"],"Zerind":["Oradea"],"Oradea":["Sibiu"],"Timisoara":["Lugoj"],"Lugoj":["Mehadia"],"Mehadia":["Dobreta"],"Dobreta":["Craiova"],"Sibiu":["Fagaras","RimnicuVilcea"],"Craiova":["RimnicuVilcea","Pitesti"],"RimnicuVilcea":["Craiova","Pitesti"],"Fagaras":["Bucharest"],"Pitesti":["Bucharest"],"Bucharest":["Giurgiu","Urziceni"],"Urziceni":["Hirsova","Vaslui"],"Hirsova":["Eforie"],"Vaslui":["Lasi"],"Lasi":["Neamt"]}
        self.weights={"AradZerind":75,"ZerindOradea":71,"AradTimisoara":118,"TimisoaraLugoj":111,"LugojMehadia":70,"MehadiaDobreta":75,"AradSibiu":140,"OradeaSibiu":151,"DobretaCraiova":120,"CraiovaRimnicuVilcea":146,"CraiovaPitesti":138,"SibiuFagaras":99,"SibiuRimnicuVilcea":80,"RimnicuVilceaPitesti":97,"RimnicuVilceaCraiova":146,"FagarasBucharest":211,"PitestiBucharest":101,"BucharestGiurgiu":90,"BucharestUrziceni":85,"UrziceniHirsova":98,"HirsovaEforie":86,"UrziceniVaslui":142,"VasluiLasi":92,"LasiNeamt":87}
    def neighbors(self,node):
        return self.edges[node]
    def get_cost(self,from_node,to_node):
        return self.weights[(from_node + to_node)]



def ucs(graph, start, goal):
    global total_cost
    visited = set()
    path=[]
    queue = PriorityQueue()
    queue.put((0, start))
    while queue:
        cost, node = queue.get()
        if node not in visited:
            visited.add(node)
            if node == goal:
                return visited
            for i in graph.neighbors(node):
                if i not in visited:
                    total_cost = cost + graph.get_cost(node, i)
                    queue.put((total_cost, I)


graph=Graph()
s=ucs(graph,"Arad","Bucharest")
print(s)

Answer 1

您可以使用如下方式初始化（优先级）队列：

queue = PriorityQueue()
queue.put([0,[start]])

这里，start是一个元组，表示开始状态或任何您想以自己的方式表示的内容

然后将其解压缩到while循环中：

cost,path = queue.get()
x,y=path[-1]

您不需要预先定义路径变量

当达到目标状态时，不返回成本，只需打印（成本）或任何您想要打印并返回路径的变量：

x,y=path[-1]

要在遍历每个节点的邻接列表时更新它，可以执行以下操作：

queue.put([costx,path + [(x2, y2)]]) 

如果您想跟踪很多事情，可以将其保存在“priorityQueue（）（您的队列）”中

我可以添加代码，如果你想，但也许这将是不必要的