코드가 있습니다. 수업을 진행하고 있습니다. 그 아이디어는 내가 금기 검색으로 여행 세일즈맨 검색을 해결한다는 것입니다. 내가 이미 코드에서 수행 한 작업은 무작위로 도시 목록을 생성하는 것입니다 (사용자의 입력을 기준으로 원하는 도시의 수, 프로그램이 처음에 묻는 질문). 좌표는 X 및 Y), 나는 그들 사이의 거리를 계산할 수있다. (나는 세일즈맨이 한 도시에서 다른 도시로 곧바로 갈 수 있다고 가정한다.)TABU를 사용하는 TSP 검색 - 목록과 관련된 문제
제가 가지고있는 문제는 금기 검색입니다. 내 생각은 모든 도시를 순차적으로 방문하여 생성 된 기본 경로를 갖는 것입니다 (라인 47, 변수 이름 : domyslne). 그 다음 나는 그것을 얻는다, 나는 그것 위에서 2 개의 랜덤 한 도시를 교환하고, 그 길의 길이를 또한 계산한다. 여기에 까다로운 부분이 있습니다 : 나는 tabu와 모든 조건을 얻는 것을 잊을 수 없습니다. (아마도 중첩 된 루프 집합이 될 것입니다). 나는 2 개의 테이블을 얻고 싶다 : tabu (여기서 마지막으로 체크 된 X 조합을 저장한다)와 tabulen (tabu 테이블에 각각의 경로 길이를 저장한다). 다음으로 새 경로를 렌더링하고 길이를 계산합니다. tabu가 이미 최대 크기 X에 도달하고 새 경로의 길이가 더 작고 현재 저장된 최고 값인 경우 Tabu 목록에서 가장 높은 값을 제거하고 방금 렌더링 한 새 값으로 바꿉니다. 결국, 그런 명령의 Y 루프 이후 (현재 기본적으로 6으로 설정되어 있지만, 제곱 된 도시의 수처럼 생각하고 있습니다), 나는 tabu 테이블에서 최단 경로를 얻고이를 솔루션으로 제시합니다 . 나는 그것이 제대로 작동하도록하는 방법을 모르겠다. 나는 여기서 도움을 얻을 수 있기를 바란다. 대단히 감사드립니다!
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))