Я хочу рассчитать разницу между двумя значениями в «distance_table = » с перестановками, как я могу правильно использовать перестановки в этом случае?

Я хочу рассчитать разницу между двумя значениями в 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]) 

так что теперь я могу, например, увидеть с расстояния_таблица расстояние между городом А и городом Б следующим образом:

distance_table [city_A] [city_B]

Как я могу перебирать все комбинации в перестановке, когда я хочу, чтобы каждый город появлялся один раз?

Я хочу например: городA-городB + городB-cityC + городC-cityA и нет: городA-городB + городA городC + городB-cityC + городC-cityA и т.п.trara. , ,

Здесь я хотел бы использовать разные алгоритмы, во-первых, глупый алгоритм содержит грубую силу, чтобы увидеть разницу во времени между этим и более интеллектуальным алгоритмом, как алгоритм кратчайшего пути.

Но я не знаю, как я могу пройти через города. Как?

Вы говорите, что хотите, чтобы все перестановки без какого-либо города появлялись дважды, но в вашем примере снова появляется стартовый город (cityA), который указан в конце:

Я хочу например: городA-cityB + городB-cityC + городC-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 

Если вы думаете об этом немного, вы увидите, что комбинация формы, cityA-cityB + cityB-cityC + cityC-cityA на самом деле просто A,B,C слегка изменена. Можете ли вы придумать алгоритм преобразования A,B,C в cityA-cityB + cityB-cityC + cityC-cityA ? Возможно, вы могли бы объединить эту модификационную функцию с инструментом python, который генерирует уникальные комбинации из вашего списка.

Как насчет этого решения:

 from itertools import permutations import csv sums = [] for p in permutations(distance_table[0], 2): sums.append(sum(p)) for s in sums: print(s) 

Один простой подход с использованием функции перестановок:

 N = len(city_names) for perm in permutations(range(N)): dist = sum(distance_table[perm[i]][perm[(i+1)%N]] for i in range(N)) print perm,dist