我有一些代码，我正在为我的课程做。这个想法是我用禁忌搜索来解决旅行推销员搜索。我在我的代码中已经做的是随机生成一个城市列表（基于用户的输入——他想要多少个城市，程序在开始时提出的问题）和他们自己的一组坐标（X 和Y），我可以计算它们之间的距离（我假设，那个推销员可以直接从一个城市直接到另一个城市）。
我的问题是禁忌搜索。我的想法是有一个默认路径，只需按顺序访问所有城市，它们就会生成（第 47 行，变量名：domyslne）。然后我明白了，我在上面交换了两个随机城市，并计算了那条路线的长度。这是棘手的部分：我无法理解我想要的禁忌和所有条件（它可能是一组嵌套循环）。我想获得 2 个表：禁忌（我存储 X 最后检查的组合）和 tabulen（存储禁忌表中相应路径的长度）。接下来我渲染一条新路线并计算它的长度。如果禁忌已经达到它的最大大小 X，并且新路线的长度更小，那么当前存储的最大值，我们从禁忌列表中删除该最大值，并将其替换为新的，即 i' 我刚刚渲染。最后，在此类命令的 Y 循环之后（当前默认设置为 6，但我正在考虑像城市数量的平方或其他东西一样），我从禁忌表中获得最短路线并将其作为解决方案呈现. 我不知道如何使它正常工作，我希望我能在这里得到一些帮助。非常感谢你！
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))