我想计算一个distancetable中两个值之间的差异,这个值是从一个文件中读取的,一个csv文件中有许多城市的距离在.csv文件中,我和城市排在第一行,
这样地:
巴塞罗那;贝尔格莱德;柏林
下一行是城市之间的距离,写得像这样:
0;1528.13;1497.61年
1528.13;0;999.25年
1497.61;999.25;0
例如,从巴塞罗那到巴塞罗那的距离是0(第一位),巴塞罗那和贝尔格莱德是1528.13(第二位),贝尔格莱德和柏林是999.25。等
我正在尝试创建一个算法来搜索像这样的文件中所有城市的最短路径。但我需要使用python,可能还需要itertools的置换。
我不知道怎样才能正确地使用排列,这样我就可以把与不同可能性的距离加起来。我该怎么做?
所以我要导入排列,csv,读入文件,然后从这里开始…
from itertools import permutations
import csv
# Read data file
distance_table = []
with open('european_cities.csv') as file:
reader = csv.reader(file,delimiter=';')
# First row is the city names
city_names = reader.next()
# The rest of the rows are the distance table
for row in reader:
distance_table.append([float(cell) for cell in row])
因此,现在我可以从距离表中看到城市A和城市B之间的距离,如下所示:
距离表[城市A][城市B]
当我只希望每个城市出现一次时,如何循环排列中的所有组合?是吗?
我想要例如:citya cityb+cityb cityc+cityc citya
而不是:citya cityb+citya cityc+cityb cityc+cityc citya等。……
我想在这里使用不同的算法,首先一个愚蠢的算法用蛮力来看看这和一个更聪明的算法在时间上的区别,比如最短路径算法。
但我不知道我怎样才能环游城市。怎么用?
最佳答案
你说你希望所有没有任何城市的排列都出现两次,但是你的示例在末尾再次列出了起始城市(citya):
我想要例如:citya cityb+cityb cityc+cityc citya
所以,假设最后出现的第一个城市实际上就是你的意思,我想下面的例子说明了你如何生成你想要的城市的排列——如果这个假设是错误的,只要去掉第一个城市重复的那条线。
为了得到不同的总距离(三个总是相同的),我添加了第四个城市,并更改了输出格式,使其更紧凑,以更好地适应更多的城市。
Barcelona;Belgrade;Berlin;Brussels
0;1528.13;1497.61;1346.0
1528.13;0;999.25;1723.0
1497.61;999.25;0;764.0
1346.0;1723.0;764.0;0
代码如下:
from __future__ import print_function
import csv
import functools
try:
from itertools import izip, imap
except ImportError: # Python 3
izip = zip
imap = map
from itertools import permutations, repeat
# Create a dictance dictionary from csv data file with entries like this:
# (city_a, city_b): float(distance-between-city_a-and-city_b)
# for all pairs of city names in the file.
data_filename = 'european_cities.csv'
dist_dict = {}
with open(data_filename, 'r') as file:
reader = csv.reader(file, delimiter=';')
cities = next(reader) # header row
num_cities = len(cities)
for city in cities: # should be a row of distances for each city
from_city_iter = repeat(city, num_cities)
dist_dict.update((pair for pair in izip(izip(from_city_iter, cities),
imap(float, next(reader)))
if pair[1])) # skip 0 distances (city_a == city_b)
def pairwise(iterable):
"s -> (s0,s1), (s1,s2), (s2,s3), ..."
a, b = iter(iterable), iter(iterable)
next(b) # advance second iterator one iteration
return izip(a, b)
for tour in permutations(cities, len(cities)):
tour += (tour[0],) # make round trip by appending starting city
route = '->'.join(tour)
dist = sum(dist_dict[city_a, city_b] for city_a, city_b in pairwise(tour))
print('{:^49}: {:,}'.format(route, dist))
输出:
Barcelona->Belgrade->Berlin->Brussels->Barcelona : 4,637.38
Barcelona->Belgrade->Brussels->Berlin->Barcelona : 5,512.74
Barcelona->Berlin->Belgrade->Brussels->Barcelona : 5,565.86
Barcelona->Berlin->Brussels->Belgrade->Barcelona : 5,512.74
Barcelona->Brussels->Belgrade->Berlin->Barcelona : 5,565.86
Barcelona->Brussels->Berlin->Belgrade->Barcelona : 4,637.38
Belgrade->Barcelona->Berlin->Brussels->Belgrade : 5,512.74
Belgrade->Barcelona->Brussels->Berlin->Belgrade : 4,637.38
Belgrade->Berlin->Barcelona->Brussels->Belgrade : 5,565.86
Belgrade->Berlin->Brussels->Barcelona->Belgrade : 4,637.38
Belgrade->Brussels->Barcelona->Berlin->Belgrade : 5,565.86
Belgrade->Brussels->Berlin->Barcelona->Belgrade : 5,512.74
Berlin->Barcelona->Belgrade->Brussels->Berlin : 5,512.74
Berlin->Barcelona->Brussels->Belgrade->Berlin : 5,565.86
Berlin->Belgrade->Barcelona->Brussels->Berlin : 4,637.38
Berlin->Belgrade->Brussels->Barcelona->Berlin : 5,565.86
Berlin->Brussels->Barcelona->Belgrade->Berlin : 4,637.38
Berlin->Brussels->Belgrade->Barcelona->Berlin : 5,512.74
Brussels->Barcelona->Belgrade->Berlin->Brussels : 4,637.38
Brussels->Barcelona->Berlin->Belgrade->Brussels : 5,565.86
Brussels->Belgrade->Barcelona->Berlin->Brussels : 5,512.74
Brussels->Belgrade->Berlin->Barcelona->Brussels : 5,565.86
Brussels->Berlin->Barcelona->Belgrade->Brussels : 5,512.74
Brussels->Berlin->Belgrade->Barcelona->Brussels : 4,637.38