TSP с использованием TABU Search - проблема со списками

Question

У меня есть код, я делаю для своих классов. Идея в том, что я решаю поиск коммивояжера с помощью поиска табу. то, что я уже сделал в своем коде, - это случайным образом сгенерировать список городов (на основе входных данных пользователя - сколько городов он хочет иметь, вопрос, который программа задает в начале) с их собственным набором координат (X и Y), и я могу рассчитать расстояние между каждым из них (я предполагаю, что продавец может просто идти прямо из одного города в другой).

что у меня проблема, так это поиск по табу. Моя идея состоит в том, чтобы иметь путь по умолчанию, который идет путем посещения всех городов по порядку, в котором они были созданы (строка 47, имя переменной: domyslne). затем я получаю его, меняю местами два случайных города и рассчитываю длину этого маршрута. и вот сложная часть: я не могу разобраться, получая табу и все условия, я хочу (это, вероятно, будет набор вложенных циклов). Я хотел бы получить 2 таблицы: tabu (где я храню последние проверенные комбинации X) и tabulen (где хранится длина соответствующего пути в таблице tabu). Затем я отображаю новый маршрут и вычисляю его длину. если табу уже достигло максимального размера X, а длина нового маршрута меньше, чем наибольшее значение, сохраненное в настоящий момент, мы удаляем это самое высокое значение из списка табу и заменяем его новым, тем, которое я только что отрендерил. в конце, после того, как 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))

Answer 1

Хорошо, я понял это. Вот правильный код для замены в том месте, где объявлена ​​таблица табу

tabu = []
tabuval = []        #wartosci tabi
print(len(tabuval))
tabu.append(domyslne)           #([domyslne,(path_length(miasta, domyslne))])
tabuval.append(path_length(miasta,domyslne))
iteracje = 10000  # 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("twoja nowa tablica:",nowatablica)
    x = path_length(miasta, nowatablica)
    if (len(tabu)<5):
        tabu.append(nowatablica[:])
        #print(tabu)
        #print(x)
        tabuval.append(x)
    elif (len(tabu) == 5 and x < max(tabuval)):
        if nowatablica in tabu:
            pass
        else:
            poz = tabuval.index(max(tabuval))
            tabu[poz] = nowatablica
            tabuval[poz] = x
print(tabu)
print(tabuval)
optpoz = tabuval.index(min(tabuval))
print("Najoptymalniejsza znaleziona sciezka to:", tabu[optpoz])
print("Jej dlugosc to:", tabuval[optpoz])