私はいくつかのコードを持っています、私はクラスのためにやっています。私は、タブー検索で旅行セールスマンの検索を解決するという考えです。私がすでに自分のコードで行ってきたことは、都市のリスト（ユーザからの入力に基づいて、彼が望みたい都市の数、プログラムが最初に質問する質問）を無作為に生成することです。 Y）、私はそれらの間の距離を計算することができます（私は、セールスマンは単にある都市から別の都市にまっすぐ行くことができると仮定します）。TABUを使用したTSP検索 - リストの問題
私は問題があるのは、タブー検索です。私の考えは、すべての都市を順番に訪問するだけで、デフォルトのパスを持つことです（行47、変数名：domyslne）。それから私はそれを得る、私はそれに2つのランダムな都市を交換し、同様にそのルートの長さを計算します。ここに難しい部分があります： 私はタブーとすべての条件を取得することについて私の頭を得ることができません、私は（それはおそらく入れ子のループのセットになります）。私は2つのテーブルを取得したいと思います：tabu（私は最後にXの組み合わせをチェックします）とtabulen（tabuテーブルのそれぞれのパスの長さを格納します）。次に新しいルートをレンダリングし、長さを計算します。 tabuが既に最大サイズXに達していて、新しいルートの長さがそれよりも小さく、現在保存されている値が最も大きい場合、tabuリストからその最高値を削除し、私が今レンダリングしたものと置き換えます。最後に、このようなコマンドの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))