import random import matplotlib.pyplot as plt # type: ignore from tsp import TSP from tsp_plotter import TSPPlotter random.seed(1) # tries_per_nbhd = 10 tries_per_nbhd_per_k = {2: 1000, 3: 1000, 4: 100, 5: 100, 6: 10} tsp = TSP.from_file("tsp100.txt") plotter = TSPPlotter() sol = tsp.random_tour() score = tsp.score(sol) failures = 0 while failures < 1000: improvement = False for k in range(2, 7): for _ in range(tries_per_nbhd_per_k[k]): new_sol = tsp.k_opt(sol, k) new_score = tsp.score(new_sol) if new_score < score: sol = new_sol score = new_score improvement = True break if improvement: break if improvement: print(f"improvement with k = {k}") plotter.show_tour(sol) plotter.add_to_score_line(score) plotter.update_best(score) plt.pause(0.00001) else: failures += 1 print(f"Failure # {failures}.") plt.show(block=True)