最小里程电动汽车需要通过每个城市

Question

我有点被这个任务卡住了。

我们有一个矩阵，其中包含每个城市(60个城市)之间的距离。我们必须开着电动车经过每个城市至少一次。每个城市都有一个汽车充电点。我们可以在一个城市停留的次数没有限制。

我必须找到一次充电的最小里程，这样我们才能通过每个城市。

我应该如何面对这个任务？

Answer 1

您需要的关键概念是优先级队列，它通常是用堆实现的。这是一种数据结构，它允许你将具有某种权重的东西放入其中，然后取出权重最小的东西。

让我们也使用一组东西。

现在的想法是这样的。我们从某个地方开始。我们有一个去另一个城市的优先队列。我们总是关注到达那个城市的最短距离的车程。如果它到达了一个对我们来说是新的城市，我们会将它添加到我们可以到达的城市中，如果这比我们看到的任何其他城市都要开更长的路，我们就会更新我们的里程。

一旦我们访问了所有的城市，我们就完成了。

下面是伪代码。

choose a start_city
initialize set visited_cities
initialize priority queue named queue to (0, start_city)
initialize min_range = 0

while len(visited_cities) < number of cities:
    (distance, city) = queue.pop()
    if city not in visited_cities:
        min_range = max(min_range, distance)
        visited_cities.add(city)
        for other_city in all cities:
            if other_city not in visited_cities:
                queue.add(distance from city to other_city, other_city)

min_range is the answer