Ich habe etwas Code, ich mache für meine Klassen. Die Idee ist, dass ich eine Reiseverkäufer Suche mit Tabu Suche löse. Was ich in meinem Code bereits getan habe, ist eine zufällige Generierung einer Liste von Städten (basierend auf der Eingabe des Benutzers - wie viele Städte will er haben, die Frage, die das Programm am Anfang stellt) mit eigenen Koordinaten (X und Y), und ich kann Entfernung zwischen jedem von ihnen berechnen (ich nehme an, dass Verkäufer einfach von einer Stadt zur anderen gerade gehen kann).TSP mit TABU Suche - Problem mit Listen
was ich habe Problem ist, ist die Tabu Suche. Meine Idee ist, einen Standardpfad zu haben, der nur alle Städte der Reihe nach besucht, sie wurden generiert (Zeile 47, Variablenname: domyslne). dann tue ich es, tausche zwei zufällige Städte darauf und berechne auch die Länge dieser Route. Und hier ist der knifflige Teil: Ich kann meinen Kopf nicht bekommen, um die Tabu und alle Bedingungen zu bekommen, ich will (es wird wahrscheinlich eine Reihe von verschachtelten Schleifen sein). Ich möchte 2 Tabellen bekommen: Tabu (wo ich X letzte Kombinationen checked) und tabulen (die Länge eines entsprechenden Pfades in tabu Tabelle speichert). Als nächstes rendere ich eine neue Route und berechne die Länge. Wenn Tabu bereits die maximale Größe X erreicht hat und die Länge der neuen Route kleiner ist als der höchste Wert, der aktuell gespeichert ist, entfernen wir diesen höchsten Wert aus der Tabu-Liste und ersetzen ihn durch den neuen, den ich gerade gerendert habe. am ende, nach Y loops eines solchen befehls (momentan standardmäßig auf 6 gesetzt, aber ich denke daran, es wie die quadrierten städte oder so zu machen), bekomme ich den kürzesten weg von tabu table und präsentiere es als lösung . Ich bin nicht sicher, wie man es richtig arbeiten lässt, und ich hoffe, dass ich hier etwas Hilfe bekommen kann. Vielen Dank im Voraus!
import math
from pprint import pprint
from random import *
def odleglosci(a1, a2, b1, b2):
w1 = a1 - b1 # wspolrzedne X (roznica)
w2 = a2 - b2 # wspolrzedne Y (roznica)
w1k = w1 * w1 # kwadrat wwspolrzednych X
w2k = w2 * w2 # kwadrat wspolrzednych Y
suma = w1k + w2k # suma kwadratow
return round(math.sqrt(suma), 2) # pierwiastek z sumy kwadratow, zaokraglony do 2 miejsca po przecinku
def path_length(cities, path):
cities_pairs = zip(path, path[1:])
consecutive_distances = [odleglosci(cities[a][0], cities[a][1], cities[b][0], cities[b][1]) for (a, b) in
cities_pairs]
return round(sum(consecutive_distances), 2)
def generate_city_coordinates(cities_count):
axis_range = range(cities_count * 5)
return tuple(zip(sample(axis_range, cities_count), sample(axis_range, cities_count)))
def calculate_distances(city_coordinates):
result = []
for city in city_coordinates:
city_distances = []
for other_city in city_coordinates:
distance = odleglosci(city[0], city[1], other_city[0], other_city[1])
city_distances.append(distance)
result.append(city_distances)
return result
if __name__ == '__main__':
ilosc = int(input("Podaj ilosc miast:"))
wielkosc = 10 * ilosc
miasta = generate_city_coordinates(ilosc)
domyslne = [] # domyslna sciezka
domyslneniep = domyslne # domyslne niepelne, bez powtorzonego pierwszego elementu na ostatnim miejscu
for i in range(0, ilosc):
domyslne.append(i)
domyslne.append(domyslne[0])
print("Domyslna sciezka:")
print(domyslne)
print("wspolrzedne miast:")
print(miasta)
print("odleglosci miedzy miastami:")
wszodl = calculate_distances(miasta) # wszystkie odleglosci
pprint(wszodl)
print("dlugosc domyslnej sciezki:")
print(path_length(miasta, domyslne))
tabu = []
tabulen = []
tabu.append(domyslne)
iteracje = 6 # ilosc iteracji algorytmu TABU
for i in range(1, iteracje):
g = randint(0, ilosc - 1)
j = randint(0, ilosc - 1)
while (j == g):
j = randint(0, ilosc - 1) # dwie rozne wartosci, do zamieniania na liscie
print("G:", g, "J:", j)
nowatablica = domyslneniep
nowatablica[g], nowatablica[j] = nowatablica[j], nowatablica[g]
ost = int(len(nowatablica)) - 1
nowatablica[ost] = nowatablica[0]
print(nowatablica)
print(path_length(miasta, nowatablica))