Я новичок, когда дело доходит до кодирования. Сейчас я пытаюсь написать код для решения проблемы коммивояжера. Я уже нашел работающий код для набора случайных значений (как показано ниже или в https://nbviewer.jupyter.org/url/norvig.com/ipython/TSP.ipynb#Random -Sets-of-Cities ). Теперь я хочу использовать данные в созданном мною файле .csv, содержащем данные о городах в системе координат (значения x и y). Однако я не могу понять, что именно мне нужно изменить в коде.
Я попытался изменить определение функции Cities () на return frozenset(City() for row in csv.reader(staedtekoordinaten.csv, delimiter=";"), но это тоже не сработало.
Это вероятно, довольно глупый вопрос, но я был бы очень признателен, если бы кто-нибудь мог мне помочь ... Заранее спасибо!
import matplotlib.pyplot as plt
import random
import time
import itertools
import urllib
import csv
import functools
from statistics import mean, stdev
def alle_touren_tsp(cities):
# Erstelle eine Auflistung aller möglichen auszuführenden Touren. Aus dieser Liste
# kann später eine Auswahl per "min" Funktion getroffen werden, die die kürzeste Route darstellt.
return minimale_tour(alle_touren(cities))
def minimale_tour(tours):
# Definiere Funktion zur Auswahl der kürzesten Tour.
return min(tours, key=laenge_tour) # aus der Sammlung "touren" minimiere ELement "distanz_tour"
#Verbesserung - Redundante Touren werden vermieden (reduziert Rechenaufwand)
def alle_touren(cities):
# Gibt List mit Touren aus mit Permutation von Städten, alle permutationen starten jedoch mit
# derselben Stadt (verhindert Redundanzen)
start = first(cities)
return [[start] + Tour(rest)
for rest in itertools.permutations(cities - {start})]
def first(collection):
#Iteration über die collection, Ausgabe des jeweils ersten Elements
return next(iter(collection))
Tour = list # Tours are implemented as lists of cities
def laenge_tour(tour):
# Gesamtsumme einer Tour.
# Addiert die gelaufenen Teildistanzen zwischen zwei Datenpunkten (= locations)
return sum(distance(tour[i], tour[i - 1]) # für i=0 wird i-1 der letzte Datenpunkt
for i in range(len(tour)))
# Für alle Elemente in tour (Anzahl = len(tour)) wird die Distanz von der vorherigen Location (i-1)
# zur aktuellen (i) summiert)
# Lösung mit Subclass von Complex - Jeder Datenpunkt (also jeder Ort) wird mit zwei Koordinaten gespeichert,
# der Einfachheit halber im komplexen Zahlenraum (dort hat jeder Punkt generell zwei Koordinaten)
class Datenpunkt(complex):
x = property(lambda p: p.real)
y = property(lambda p: p.imag)
City = Datenpunkt
def distance(A, B):
# Definiert die Distanz "zu laufende Länge" zwischen den Punkten A und B => Euklidische Distanz
return abs(A - B)
# Testdatenpunkt: Randomized Cities mit Seed 42
def Cities(n, width=900, height=600, seed=42):
# Set aus n Datenpunkten mit randomized Koordinaten, dargestellt in width x height (900x600 weil Python-Standard)
random.seed(seed * n)
return frozenset(City(random.randrange(width), random.randrange(height))
# frozenset, damit kein Algorithmus einfach Datenpunkte löscht
# (i. S. v. der kürzeste Weg wäre, erst gar keinen Weg zu laufen)
for c in range(n))
alle_touren_tsp(Cities(8))
def plot_tour(tour):
# "Plot the cities as circles and the tour as lines between them."
plot_lines(list(tour) + [tour[0]])
def plot_lines(points, style='bo-'):
# "Plot lines to connect a series of points."
plt.plot([p.x for p in points], [p.y for p in points], style)
plt.axis('scaled');
plt.axis('off')
plot_tour(alle_touren_tsp(Cities(8)))
def plot_tsp(algorithm, cities):
# "Apply a TSP algorithm to cities, plot the resulting tour, and print information."
# Find the solution and time how long it takes
t0 = time.process_time()
tour = algorithm(cities)
t1 = time.process_time()
assert valid_tour(tour, cities)
plot_tour(tour);
plt.show()
print("{} city tour with length {:.1f} in {:.3f} secs for {}"
.format(len(tour), laenge_tour(tour), t1 - t0, algorithm.__name__))
def valid_tour(tour, cities):
# "Is tour a valid tour for these cities?"
return set(tour) == set(cities) and len(tour) == len(cities)
plot_tsp(alle_touren_tsp, Cities(8))
Что касается нового кода (если я правильно понял замечания:
import csv
# Lösung mit Subclass von Complex - Jeder Datenpunkt (also jeder Ort) wird mit zwei Koordinaten gespeichert,
# der Einfachheit halber im komplexen Zahlenraum (dort hat jeder Punkt generell zwei Koordinaten)
class Datenpunkt(complex):
x = property(lambda p: p.real)
y = property(lambda p: p.imag)
class City(Datenpunkt):
# this is a subclass of `complex` which sets itself up in `__new__`
def __new__(cls, x, y, name):
self = super().__new__(cls, float(x), float(y))
self.name = name
return self
def __str__(self):
return "{} {}".format(super().__str__(), self.name)
def __repr__(self):
return str(self)
@classmethod
def from_csv(cls, row):
"""Create class from CSV row. Row is assumed to be a collection with
index 0 and 1 being the coordinates of interest."""
return cls(*row[0:3])
def Cities(filename):
with open(filename, newline='') as fp:
return frozenset(City.from_csv(row) for row in csv.reader(fp, delimiter=";"))
print(Cities("testfile.csv"))
Это дает ошибки: Traceback (последний вызов последний):
File "filepath/Test.py", line 35, in <module>
print(Cities("testfile.csv"))
File "filepath/Test.py", line 34, in Cities
return frozenset(City.from_csv(row) for row in csv.reader(fp,
delimiter=";"))
File "filepath/Test.py", line 34, in <genexpr>
return frozenset(City.from_csv(row) for row in csv.reader(fp,
delimiter=";"))
File "filepath/Test.py", line 29, in from_csv
return cls(*row[0:3])
File "filepath/Test.py", line 15, in __new__
self = super().__new__(cls, float(x), float(y))
ValueError: could not convert string to float: 'x'
Process finished with exit code 1
Напечатанные строки в соответствии с вашей идеей:
b'\xef\xbb\xbfx;y;name\r\n'b'0;0;Duisburg\r\n'
b'455,56;120,87;Berlin\r\n'
b'218,86;235,59;Hamburg\r\n'
b'345,6;-366,75;Muenchen\r\n'
b'13,97;-55,24;Koeln\r\n'
b'135,12;-147,2;Frankfurt\r\n'
b'190,25;-13,17;Kassel\r\n'
b'297,02;-51,3;Erfurt\r\n