Untitled
unknown
plain_text
10 months ago
59 kB
8
Indexable
import asyncio
import math
import os
import random
import subprocess
import tempfile
import time
from io import StringIO
from typing import List, Union
import numpy as np
from matplotlib import pyplot as plt
from graphite.data.dataset_utils import load_default_dataset
from graphite.data.distance import geom_edges, euc_2d_edges, man_2d_edges
from graphite.protocol import GraphV1Problem, GraphV2Problem, GraphV2ProblemMulti
from graphite.solvers.base_solver import BaseSolver
def aggressive_single_iteration(route, edges, initial_window=20, top_nodes_percent=0.5):
print("Starting Aggressive Single Iteration...")
current_route = route.copy()
best_distance = calculate_edge_distance(current_route, edges)[0]
# Get nodes connected to longest edges
print("Calculating edge distances...")
_, edge_distances = calculate_edge_distance(current_route, edges)
print("Getting longest edges...")
longest_edges = get_longest_edges(edge_distances, top_nodes_percent)
nodes_to_try = set()
print("Building nodes set...")
# Get more nodes to try
for start, end, dist in longest_edges:
nodes_to_try.add(start)
nodes_to_try.add(end)
idx_start = current_route.index(start)
idx_end = current_route.index(end)
for offset in [-2, -1, 1, 2]:
if 0 <= idx_start + offset < len(current_route):
nodes_to_try.add(current_route[idx_start + offset])
if 0 <= idx_end + offset < len(current_route):
nodes_to_try.add(current_route[idx_end + offset])
print(f"Number of nodes to try: {len(nodes_to_try)}")
# Simplified version - let's first make sure it runs
for node in nodes_to_try:
current_pos = current_route.index(node)
temp_route = current_route.copy()
temp_route.pop(current_pos)
# Try a fixed window size first
window_size = initial_window
start_window = max(0, current_pos - window_size)
end_window = min(len(current_route), current_pos + window_size)
best_local_pos = None
best_local_distance = best_distance
for pos in range(start_window, end_window):
candidate_route = temp_route.copy()
candidate_route.insert(pos, node)
new_distance, _ = calculate_edge_distance(candidate_route, edges)
if new_distance < best_local_distance:
best_local_distance = new_distance
best_local_pos = pos
if best_local_pos is not None and best_local_distance < best_distance:
print(f"Improved distance: {best_local_distance}")
current_route.pop(current_pos)
current_route.insert(best_local_pos, node)
best_distance = best_local_distance
return current_route
def do_edges_intersect(p1, p2, p3, p4):
# Simple 2D line segment intersection check
def ccw(A, B, C):
return (C[1] - A[1]) * (B[0] - A[0]) > (B[1] - A[1]) * (C[0] - A[0])
return ccw(p1, p3, p4) != ccw(p2, p3, p4) and ccw(p1, p2, p3) != ccw(p1, p2, p4)
def double_bridge_move(route):
size = len(route)
if size < 8:
return route
# Select 4 random cutting points
pos1 = random.randint(1, size // 4)
pos2 = random.randint(pos1 + 2, size // 2)
pos3 = random.randint(pos2 + 2, 3 * size // 4)
pos4 = random.randint(pos3 + 2, size - 1)
# Create new route using double-bridge move
new_route = route[:pos1] + \
route[pos3:pos4] + \
route[pos2:pos3] + \
route[pos1:pos2] + \
route[pos4:]
return new_route
def path_relinking(route1, route2, edges):
best_route = route1
best_distance = calculate_edge_distance(route1, edges)[0]
current_route = route1.copy()
# Get edges that exist in route2 but not in route1
edges_in_2 = set((route2[i], route2[i + 1]) for i in range(len(route2) - 1))
edges_in_1 = set((route1[i], route1[i + 1]) for i in range(len(route1) - 1))
target_edges = edges_in_2 - edges_in_1
for edge in target_edges:
# Try to incorporate this edge from route2 into current route
start, end = edge
if start in current_route and end in current_route:
idx1 = current_route.index(start)
idx2 = current_route.index(end)
new_route = two_opt_swap(current_route, idx1, idx2)
new_distance, _ = calculate_edge_distance(new_route, edges)
if new_distance < best_distance:
best_distance = new_distance
best_route = new_route.copy()
current_route = new_route
return best_route
def temperature_based_optimization(initial_route, edges, n_attempts=5):
best_route = initial_route
best_distance = calculate_edge_distance(initial_route, edges)[0]
for _ in range(n_attempts):
# Create perturbed starting solution using double-bridge
current_route = double_bridge_move(initial_route.copy())
temperature = 1.0
while temperature > 0.1:
# Get candidate move
i = random.randint(0, len(current_route) - 2)
j = random.randint(i + 1, len(current_route) - 1)
candidate_route = two_opt_swap(current_route, i, j)
current_distance = calculate_edge_distance(current_route, edges)[0]
candidate_distance = calculate_edge_distance(candidate_route, edges)[0]
# Accept based on temperature
if candidate_distance < current_distance or \
random.random() < math.exp(
(current_distance - candidate_distance) / (temperature * current_distance)):
current_route = candidate_route
if candidate_distance < best_distance:
best_distance = candidate_distance
best_route = candidate_route.copy()
temperature *= 0.95
return best_route
def enhanced_optimization(initial_route, edges):
print("Starting Enhanced Optimization...")
current_route = initial_route.copy()
best_distance = calculate_edge_distance(current_route, edges)[0]
# 1. First apply quick local search chain
current_route = quick_local_search_chain(current_route, edges)
# 2. Generate multiple solutions using double-bridge
solutions = [current_route]
for _ in range(3): # Generate 3 additional solutions
perturbed = double_bridge_move(current_route.copy())
optimized = quick_local_search_chain(perturbed, edges)
solutions.append(optimized)
# 3. Apply path relinking between best solutions
for i in range(len(solutions)):
for j in range(i + 1, len(solutions)):
relinked = path_relinking(solutions[i], solutions[j], edges)
current_distance = calculate_edge_distance(relinked, edges)[0]
if current_distance < best_distance:
best_distance = current_distance
current_route = relinked
# 4. Final temperature-based refinement
final_route = temperature_based_optimization(current_route, edges)
final_distance = calculate_edge_distance(final_route, edges)[0]
print(f"Final enhanced distance: {final_distance}")
return final_route
def visualize_routes(node_coords, routes):
fig, ax = plt.subplots(figsize=(10, 10))
for i, route in enumerate(routes, start=1):
# Extract the coordinates for the current route
route_coords = node_coords[route]
# Plot the route
ax.plot(route_coords[:, 0], route_coords[:, 1], marker='o', label=f'Route {i}')
# Add arrow markers to indicate the direction of travel
for j in range(len(route) - 1):
start = route_coords[j]
end = route_coords[j + 1]
dx = end[0] - start[0]
dy = end[1] - start[1]
ax.annotate('', xy=end, xytext=start, arrowprops=dict(arrowstyle='->', color='gray', shrinkA=5, shrinkB=5))
# Add depot marker
depot_coords = node_coords[0]
ax.plot(depot_coords[0], depot_coords[1], marker='s', markersize=10, color='red', label='Depot')
ax.set_xlabel('X')
ax.set_ylabel('Y')
ax.set_title('Multiple Traveling Salesman Problem Routes')
ax.legend()
plt.tight_layout()
plt.show()
def calculate_edge_distance(route, edges):
total_distance = 0
edge_distances = []
for i in range(len(route) - 1):
dist = edges[route[i]][route[i + 1]]
edge_distances.append((route[i], route[i + 1], dist))
total_distance += dist
return total_distance, edge_distances
def get_longest_edges(edge_distances, top_percent=0.5):
# Sort edges by distance and get top 10%
sorted_edges = sorted(edge_distances, key=lambda x: x[2], reverse=True)
num_edges = int(len(sorted_edges) * top_percent)
return sorted_edges[:num_edges]
def two_opt_swap(route, i, j):
new_route = route[:i]
new_route.extend(reversed(route[i:j + 1]))
new_route.extend(route[j + 1:])
return new_route
def try_node_insertion(route, edges, node_idx, window=5):
best_distance = float('inf')
best_position = None
current_pos = route.index(node_idx)
# Try inserting the node in nearby positions
start = max(0, current_pos - window)
end = min(len(route), current_pos + window)
temp_route = route.copy()
temp_route.pop(current_pos)
for pos in range(start, end):
candidate_route = temp_route.copy()
candidate_route.insert(pos, node_idx)
dist, _ = calculate_edge_distance(candidate_route, edges)
if dist < best_distance:
best_distance = dist
best_position = pos
if best_position is not None:
new_route = route.copy()
new_route.pop(current_pos)
new_route.insert(best_position, node_idx)
return new_route
return route
def quick_local_search_chain(initial_route, edges):
print("Starting Quick Local Search Chain optimization...")
current_route = initial_route.copy()
initial_distance, edge_distances = calculate_edge_distance(current_route, edges)
print(f"Initial distance: {initial_distance}")
# Get longest edges
longest_edges = get_longest_edges(edge_distances)
print(f"Found {len(longest_edges)} longest edges to optimize")
improved = True
iteration = 0
max_iterations = 3 # Limit iterations to maintain speed
while improved and iteration < max_iterations:
improved = False
iteration += 1
# Try 2-opt moves around longest edges
for edge_start, edge_end, _ in longest_edges:
idx1 = current_route.index(edge_start)
idx2 = current_route.index(edge_end)
# Try 2-opt swap
new_route = two_opt_swap(current_route, idx1, idx2)
new_distance, _ = calculate_edge_distance(new_route, edges)
if new_distance < initial_distance:
print(f"Improved distance with 2-opt: {new_distance} (iteration {iteration})")
current_route = new_route
initial_distance = new_distance
improved = True
# Try node insertion for nodes connected to longest edges
nodes_to_try = set()
for edge_start, edge_end, _ in longest_edges:
nodes_to_try.add(edge_start)
nodes_to_try.add(edge_end)
for node in nodes_to_try:
new_route = try_node_insertion(current_route, edges, node)
new_distance, _ = calculate_edge_distance(new_route, edges)
if new_distance < initial_distance:
print(f"Improved distance with node insertion: {new_distance} (iteration {iteration})")
current_route = new_route
initial_distance = new_distance
improved = True
final_distance, _ = calculate_edge_distance(current_route, edges)
print(f"Final distance after optimization: {final_distance}")
return current_route
class LKHSolver(BaseSolver):
def __init__(self, problem_types: List[Union[GraphV1Problem, GraphV2Problem]] = [GraphV1Problem(n_nodes=2),
GraphV1Problem(n_nodes=2,
directed=True,
problem_type='General TSP')]):
super().__init__(problem_types=problem_types)
self.lkh_path = "/home/lampham/CLionProjects/LKH-3.0.12/LKH"
def create_problem_file(self, distance_matrix):
dimension = len(distance_matrix)
problem_file_content = f"""NAME: TSP
TYPE: TSP
DIMENSION: {dimension}
EDGE_WEIGHT_TYPE: EXPLICIT
EDGE_WEIGHT_FORMAT: FULL_MATRIX
EDGE_WEIGHT_SECTION
"""
# Sử dụng StringIO và np.savetxt để tạo chuỗi
buffer = StringIO()
np.savetxt(buffer, distance_matrix, fmt='%d', delimiter=' ')
matrix_string = buffer.getvalue().strip()
problem_file_content += matrix_string + "\nEOF\n"
return problem_file_content
def create_parameter_file(self, problem_file_path, tour_file_path, nodes=5000):
trial = int(500 * 5000 / nodes)
parameter_file_content = f"""PROBLEM_FILE = {problem_file_path}
TOUR_FILE = {tour_file_path}
INITIAL_PERIOD = 100
PRECISION = 1e-05
RUNS = 1
INITIAL_TOUR_ALGORITHM = GREEDY
MAX_TRIALS = {trial}
KICK_TYPE = 5
KICKS = 10
POPMUSIC_INITIAL_TOUR = YES
POPULATION_SIZE = 5
TIME_LIMIT = 18
TOTAL_TIME_LIMIT = 18
POPMUSIC_MAX_NEIGHBORS = 5
POPMUSIC_SAMPLE_SIZE = 20
POPMUSIC_SOLUTIONS = 70
POPMUSIC_TRIALS = 2
POPULATION_SIZE = 10
PRECISION = 1
"""
return parameter_file_content
async def solve(self, formatted_problem, future_id: int) -> List[int]:
with tempfile.NamedTemporaryFile('w+', prefix='problem_', suffix='.txt', delete=False) as problem_file, \
tempfile.NamedTemporaryFile('w+', prefix='param_', suffix='.txt', delete=False) as parameter_file, \
tempfile.NamedTemporaryFile('r+', prefix='tour_', suffix='.txt', delete=False) as tour_file:
problem_file_content = self.create_problem_file(formatted_problem)
problem_file.write(problem_file_content)
problem_file.flush()
parameter_file_content = self.create_parameter_file(problem_file.name, tour_file.name,
len(formatted_problem))
parameter_file.write(parameter_file_content)
parameter_file.flush()
# Run LKH
subprocess.run([self.lkh_path, parameter_file.name], check=True)
# Read the tour file
tour_file.seek(0)
tour = self.parse_tour_file(tour_file.name)
# Clean up temporary files
os.remove(problem_file.name)
os.remove(parameter_file.name)
os.remove(tour_file.name)
# total_distance = self.calculate_total_distance(tour, formatted_problem)
# return tour
return tour
def calculate_total_distance(self, tour, distance_matrix):
total_distance = 0
for i in range(len(tour)):
total_distance += distance_matrix[tour[i]][tour[(i + 1) % len(tour)]]
return total_distance
def parse_tour_file(self, tour_file_path):
tour = []
with open(tour_file_path, 'r') as file:
in_tour_section = False
for line in file:
if line.strip() == 'TOUR_SECTION':
in_tour_section = True
elif line.strip() == '-1':
break
elif in_tour_section:
tour.append(int(line.strip()) - 1) # LKH uses 1-based indexing
tour.append(tour[0])
return tour
def problem_transformations(self, problem: Union[GraphV1Problem, GraphV2Problem]):
return problem.edges
if __name__ == "__main__":
## Test case for GraphV2Problem
class Mock:
def __init__(self) -> None:
pass
def recreate_edges(self, problem: Union[GraphV2Problem, GraphV2ProblemMulti]):
edge_start_time = time.time()
node_coords_np = self.loaded_datasets[problem.dataset_ref]["data"]
node_coords = np.array([node_coords_np[i][1:] for i in problem.selected_ids])
if problem.cost_function == "Geom":
edges = geom_edges(node_coords)
elif problem.cost_function == "Euclidean2D":
edges = euc_2d_edges(node_coords)
elif problem.cost_function == "Manhatten2D":
edges = man_2d_edges(node_coords)
else:
return "Only Geom, Euclidean2D, and Manhatten2D supported for now."
# logger.info(f"Edge recreation took: {time.time() - edge_start_time:.2f} seconds")
return edges, node_coords
mock = Mock()
load_default_dataset(mock)
n_nodes = 3877
# randomly select n_nodes indexes from the selected graph
selected_ids = [717846, 26690333, 4168552, 169543, 21202402, 20398931, 20286603, 17518068, 21643873, 23673485, 16422586,
26428050, 982127, 11295052, 8080498, 2156297, 18597836, 7671501, 21667079, 5836273, 16870251, 17952777,
14427084, 2475157, 3573191, 22635674, 24200242, 3291513, 23671608, 2827082, 15109917, 9504143, 15966105,
2144437, 17740844, 6669876, 26508438, 12235485, 24692642, 21599104, 6695242, 11164007, 6281116, 25202774,
10855194, 21476996, 23139822, 5858059, 9739615, 25373275, 3964509, 4889136, 3733736, 3422489, 20957260, 275775,
5786784, 10843343, 25410731, 8344035, 21522982, 16367205, 3212495, 25953059, 4489386, 24369648, 6348178,
18652718, 14247052, 4714211, 25040833, 5904920, 6289578, 15406063, 20224786, 19650564, 15587698, 3776099,
2836214, 23524448, 24177838, 24919393, 12775185, 5389261, 25438091, 12404179, 26181043, 22503057, 13730371,
16865901, 797814, 24781103, 4170956, 11341882, 2096100, 11709163, 26098823, 6351499, 510217, 17201504,
21743425, 15955812, 7323545, 13040846, 15592290, 21305682, 24082601, 7052607, 9274327, 23471770, 14435091,
5562139, 11531624, 23084998, 19470523, 2672203, 19850407, 18206125, 24169245, 19364555, 15790956, 6682001,
22501274, 14255262, 5617799, 15077540, 24786807, 5694950, 11718845, 25793843, 4079275, 9418911, 6843698,
5174407, 5864099, 3096551, 9690254, 22056407, 11294570, 5350205, 4523269, 11946560, 24703168, 18280647,
10715824, 11437000, 17385165, 7521557, 2421016, 14634142, 23093092, 8227175, 21082464, 21840579, 13220599,
2698690, 3956777, 12984509, 23725940, 19856193, 11301053, 9886991, 10505342, 25252568, 3310031, 21722278,
17576774, 23256694, 4143948, 4913664, 13456310, 20579235, 19322643, 25699397, 15358047, 23048492, 5063474,
12116652, 3765145, 21927217, 26450453, 10415843, 8780272, 15583345, 7394441, 20397181, 22860046, 15408681,
9618833, 634955, 13655668, 7462391, 14955562, 10041572, 4265621, 24219302, 4319894, 1322385, 10848441, 1317292,
16408481, 2100516, 12980570, 6001982, 11405877, 24035218, 5547910, 25835529, 23347165, 2875400, 15331839,
18495118, 19363322, 14185801, 26465728, 21165270, 4496474, 8765194, 22922900, 5537531, 143799, 2368830,
1883544, 506405, 20111883, 25370769, 7527728, 18030395, 25162374, 20179591, 7563866, 13284180, 21910925,
12656320, 13450367, 24245967, 5209836, 7713305, 105939, 2810719, 18336329, 17376374, 14997350, 14647584,
20575872, 13706275, 22373560, 13386304, 15642131, 9455913, 8998471, 5814581, 25336597, 15547, 13049790,
10515685, 3140464, 16317142, 7177246, 7415560, 6005353, 26607953, 16899932, 15515223, 24653593, 2337277,
18608773, 1477546, 8780365, 22135819, 9953030, 23839132, 7026490, 5877102, 16366760, 12172804, 15712103,
11480710, 17762569, 8724394, 21927982, 13612250, 6400437, 10095291, 16312407, 25508561, 12251440, 14397161,
2771398, 9448667, 2278696, 14136230, 11733496, 2779516, 8768263, 16367150, 7363393, 2921857, 11061446, 7560220,
84049, 26314669, 2145388, 15538060, 19114430, 5380656, 5134308, 7936177, 15690014, 4179372, 24480389, 12637485,
25381141, 6762214, 2882267, 24902989, 11443479, 25191045, 291702, 9145926, 12042162, 1742486, 9790282, 2441934,
14287380, 13775707, 16488558, 17967760, 8240735, 15801874, 5503649, 20175797, 1746013, 11320331, 24486347,
4905969, 1168377, 18062898, 9779065, 5411899, 18323673, 6028926, 2408656, 23141864, 11048340, 19330003,
16709459, 5593857, 15056088, 10754662, 138093, 11776624, 24346937, 17551419, 25071844, 14719266, 26719109,
24521455, 10388744, 6005302, 13018821, 614259, 25692595, 8086010, 24131573, 21379446, 8656984, 6824701,
20690529, 19983461, 14162672, 5293380, 17512825, 15647383, 22486693, 16895984, 21685618, 6394971, 21578972,
10515889, 21148156, 17083250, 6359416, 14772933, 5909623, 2907988, 6368262, 13741482, 966311, 23823108,
13277253, 11632181, 22296100, 12601230, 23612205, 10117423, 3529117, 23263228, 25847033, 19738581, 15514166,
5104605, 2574822, 19436821, 7975688, 26005480, 20173605, 2784636, 22065902, 11237014, 25983150, 26663117,
7015625, 2629543, 3573793, 13312619, 17460753, 7657746, 8933635, 23005423, 10096499, 12504543, 18420188,
6907443, 15081342, 8365521, 11301754, 9582992, 533885, 8586603, 14964429, 8428869, 10193089, 5740587, 19750210,
8963160, 21615982, 4173737, 12067212, 10678296, 10162678, 17378789, 23287575, 25977998, 11384816, 22528936,
10236255, 11278555, 22406766, 17443430, 25273721, 4431791, 11380948, 9812587, 11401164, 25546106, 18153569,
8409934, 10361348, 19779241, 17962868, 25658764, 7720556, 16838508, 5980842, 25988275, 24717475, 3714624,
21552518, 1215152, 22596854, 8575516, 18485742, 23097777, 21683800, 653169, 25112029, 14250660, 14906841,
1276395, 13223123, 5511399, 25375128, 25833023, 7769470, 2436967, 14327186, 12104451, 286838, 20275029,
25176144, 16584114, 13771435, 15798959, 2447096, 14072163, 13549161, 21999569, 10261017, 9150084, 4740022,
20771256, 15934247, 7605118, 19408900, 334015, 8828783, 1486077, 21926330, 10918859, 20445533, 12838600,
172615, 20427935, 12219663, 26201783, 21651915, 2715726, 20980752, 1963148, 26411469, 579758, 980687, 24755273,
15293097, 3162866, 2015683, 19110279, 16303218, 24142896, 12960712, 3343140, 14463760, 5061313, 13216053,
3244332, 8469962, 230737, 26681815, 3800207, 24614253, 16687624, 16105036, 16987990, 5900750, 8067842,
13250195, 6153908, 7368716, 13215939, 14123819, 3712482, 24782140, 13803368, 26412066, 21776794, 3672345,
25537149, 22191450, 23446468, 18001928, 2717208, 22729904, 13335949, 21689948, 14244457, 13870107, 7607001,
10130161, 9122151, 1772012, 1328646, 24524094, 21343446, 20077967, 4388134, 20815153, 2040111, 12106449,
7881543, 8690216, 19065607, 15258006, 20932826, 86733, 11162064, 20733023, 1768948, 20843985, 10236141,
20056514, 25456870, 2188810, 17510141, 14583333, 12264994, 19589716, 1655560, 22057722, 3966044, 21176526,
24907649, 6249171, 5731254, 1866628, 4759719, 13286931, 20808009, 1712567, 22074335, 15154448, 23984006,
14222878, 3676995, 16027847, 4681030, 15205019, 20216099, 17040897, 13752279, 16318531, 3950948, 26668616,
10849224, 4187113, 11799405, 25375736, 15629419, 16228561, 12956498, 10810956, 6104987, 12512197, 19128191,
24254304, 5596368, 21925829, 6822863, 1672534, 1694906, 22105014, 16478292, 21222478, 14922809, 14447002,
8808457, 10315585, 17922278, 23070364, 8611753, 7750039, 8057124, 23043567, 15792175, 6819364, 24236883,
2618840, 14704048, 19709133, 5750276, 21485460, 26608836, 10519739, 17704802, 24963528, 7722272, 14793810,
5176187, 10343445, 17893803, 5025072, 19198064, 7820160, 19558080, 19804459, 17747123, 1348331, 19492437,
24615142, 10247942, 16832880, 13500990, 22488304, 20585087, 23609340, 3949708, 26768695, 2160078, 16827765,
2378188, 24318358, 6441132, 20866905, 2575457, 1007212, 17707045, 21804382, 23178464, 20372227, 20022203,
2813431, 18994351, 4270366, 14474508, 1177069, 12457280, 9154604, 21715991, 4525004, 10646688, 4375617,
12391230, 13019143, 11070482, 25495193, 10977557, 14658149, 11471597, 3576266, 20245923, 306314, 2298643,
11262522, 14483938, 16757797, 15844105, 2322884, 15510349, 6140034, 8016278, 16484745, 22720198, 13167004,
26151429, 11712448, 25048975, 4991949, 7219906, 5626472, 13619300, 5233861, 13621321, 18011248, 13794087,
3011892, 23767884, 14652708, 25051400, 12699724, 23366765, 25345705, 3627393, 19125493, 18746151, 983833,
8642822, 14295525, 24777154, 18301176, 21220753, 14973092, 20555674, 489262, 3520550, 14224405, 6649388,
208594, 11862570, 201665, 13028791, 15587210, 23380049, 16380875, 5581959, 19624443, 18630552, 1223493,
13478470, 17842397, 3658626, 9107090, 23632744, 22833082, 8184749, 12846929, 16568840, 25964548, 7209876,
1213230, 19413426, 20037104, 8556211, 3077861, 7854400, 12181311, 7294056, 1554209, 23061296, 21579367,
6420776, 17645807, 17427526, 1670309, 1278896, 21702987, 2213165, 12255973, 18357268, 14535086, 3188702,
12202935, 12728296, 19651378, 19864950, 3586315, 16608270, 23041886, 16523918, 15015854, 1933803, 12320147,
19020573, 5122768, 19153162, 2641158, 20831601, 189, 25605782, 2144546, 19604098, 17786888, 4792255, 25463365,
19462015, 17059259, 7039752, 21850143, 13728807, 314954, 3238667, 19631960, 11333562, 196780, 20425343,
13721347, 24645442, 19745931, 16758393, 18896678, 9093039, 24873270, 18918340, 8475658, 15536784, 6832825,
22293612, 12995257, 17996396, 13784196, 24960045, 17856618, 11451243, 12943184, 12290045, 19878630, 12088814,
17330369, 2565819, 18196687, 16503350, 12356767, 6135113, 9383556, 1764217, 4868782, 16262123, 24619438,
22378191, 19180042, 23048251, 695198, 21497122, 12443104, 23058912, 9859772, 5378384, 14517857, 3720140,
11461184, 20230387, 24548827, 10370766, 20776845, 21939803, 914233, 14574375, 3880141, 7691138, 21722595,
10267451, 24052993, 11268731, 3210923, 25238819, 12470651, 23148607, 19142742, 22842064, 18889165, 10653952,
13538756, 2891743, 5177819, 9581214, 23651422, 24360659, 18468293, 20990648, 6088930, 5253114, 12816500,
20538995, 3000906, 15734733, 9243512, 23294090, 22939545, 9192518, 25405997, 23990338, 5319946, 8775986,
13075748, 11330234, 15531110, 4872023, 9909176, 14767209, 22365687, 10593884, 12371017, 25604030, 15495148,
8091749, 946243, 21320631, 11594217, 6120077, 12051876, 25380729, 19311271, 12039278, 26103021, 6182697,
13422334, 6552780, 1631208, 11885131, 25967364, 4920722, 9791693, 21640980, 9621663, 3658263, 15368606,
1886218, 1257795, 20091625, 11598738, 12908629, 6744846, 1597673, 17177922, 8682125, 17494587, 18247584,
18727752, 25243411, 1460490, 14623137, 15939932, 11966613, 19773121, 25260469, 5082986, 1383002, 925964,
12991234, 18195048, 21637139, 8823592, 12934901, 26739916, 9167323, 19831410, 7112977, 20148282, 19745871,
23786561, 13356166, 26230735, 20312909, 1230818, 709231, 16599033, 3826122, 7492509, 14141335, 4695088, 926196,
19069445, 9689791, 24993408, 14072076, 2081670, 6839492, 15486187, 14271495, 23536973, 4169833, 17586902,
24672532, 5690593, 2906020, 20931371, 13760874, 17275757, 3053210, 19851874, 6070611, 12808801, 8706778,
7591889, 13461977, 3299589, 14693239, 3713221, 10638728, 2244037, 23968015, 994472, 8110806, 15449642, 5168068,
24966645, 14637496, 3308552, 8190693, 23376113, 23799121, 18390698, 20351312, 6744984, 21877330, 14773798,
3485795, 10237454, 24460540, 17939521, 22066622, 2011012, 6378422, 16046188, 4298214, 9071795, 10716505,
17838719, 24081281, 1121984, 11887526, 20071174, 13128812, 4006561, 21282003, 22863872, 21242248, 10822805,
6716596, 3167056, 22173227, 11285594, 17191391, 14866178, 2290198, 19846857, 7798747, 17718781, 64057,
10750257, 15160829, 15509999, 3481566, 18858762, 9856069, 877647, 23991547, 8235370, 9094271, 8595955,
13112813, 12424872, 24517563, 17093565, 3150924, 4623817, 8284726, 2390132, 4254686, 1152084, 7624695,
26275454, 17692506, 23975809, 4270862, 4443212, 10406569, 19204707, 24393282, 21565456, 15649057, 8517526,
25811267, 4671154, 6892266, 11262219, 3704412, 4494881, 21998467, 18816159, 774977, 15825136, 10446217,
18071940, 2896640, 307180, 19958940, 11778457, 26025375, 16557200, 24709746, 26017122, 10018962, 16578649,
701562, 10271052, 11081895, 25744863, 11232992, 22662401, 22925039, 6243658, 8480486, 23549236, 19888478,
15734812, 15951385, 15825265, 7987893, 21098608, 24101068, 16887235, 21401412, 13641771, 2032893, 9853747,
8583198, 22303254, 4479753, 4914643, 14884450, 14401013, 2934698, 21390400, 14742187, 22405355, 2978353,
15399624, 10853984, 22538486, 20639963, 8928520, 2862050, 20489596, 8335133, 720602, 24930818, 25705212,
11821401, 4314450, 7283681, 4849474, 6458344, 18829117, 21897513, 9368129, 1187549, 22138788, 5982760, 3022447,
25209107, 13222627, 7551933, 16107316, 3974102, 20298112, 16341348, 26410483, 11906158, 6042903, 11798590,
12716784, 2298569, 5079315, 12316491, 24331251, 25576853, 305838, 8347474, 13604685, 3494679, 25776556,
18706874, 10964695, 10528943, 7293931, 26023423, 11607400, 7125167, 24384514, 15433553, 11823169, 8434945,
1613093, 16087317, 4575147, 11690845, 24696387, 12484992, 24182437, 2658668, 1487828, 3076003, 338449, 8532258,
9376943, 11762408, 23061854, 25213671, 9524829, 17765855, 5341028, 24857335, 14019775, 21852905, 23244104,
65692, 17553767, 18794480, 10844916, 18766093, 671509, 1716003, 21950405, 21453976, 15867618, 11246953,
12889157, 26531598, 5039086, 19929915, 4554433, 4938205, 17021895, 16360141, 15076883, 19144525, 6818149,
1232409, 18274417, 22256247, 26722562, 4939754, 14692952, 4144511, 7237453, 14402341, 18462404, 1851065,
4197780, 3020214, 19185208, 25897848, 619004, 23228548, 22071583, 7463241, 5132615, 10757087, 2748075,
26021790, 16567851, 19656660, 23785095, 866413, 21365511, 5608674, 13032315, 12410220, 3906725, 11076720,
5591396, 17472518, 21720142, 26499726, 10522773, 1865714, 2720878, 5950766, 10266888, 10899319, 12274842,
14009148, 26271602, 3076623, 23440867, 2732665, 3454044, 12552297, 13007672, 15269822, 14285354, 1526733,
14048349, 25176229, 3871898, 15789143, 22880652, 22181244, 23388046, 9498669, 21397611, 11682742, 22315215,
1288604, 7842892, 1446470, 2142610, 10292918, 24486275, 10756686, 18654535, 24274403, 6112471, 12465776,
9698040, 20823418, 6866212, 7933206, 23329509, 20092683, 11977715, 19565244, 5024433, 6248639, 19287236,
11028414, 23877458, 2666951, 6527323, 21628188, 23365927, 20011983, 21635588, 25617488, 26717414, 14447105,
4186054, 1556340, 2941126, 19889541, 17762742, 19217793, 20809074, 16681635, 1820867, 5039979, 21485767,
12127253, 18500991, 16042448, 14751913, 21901738, 1643929, 178695, 23432636, 26422637, 2571552, 14980925,
18198535, 23422301, 18841705, 12901448, 4800268, 11662167, 23083861, 24923466, 18942696, 20223550, 17957236,
8890393, 5151487, 3859804, 12095767, 11959829, 625427, 14462752, 5508178, 1927300, 19494739, 7811290, 6527287,
13798190, 20400387, 8712845, 19559287, 4983810, 16042675, 16266661, 7526309, 24755707, 17730201, 6843167,
26397998, 11901059, 17877238, 9252155, 10166175, 24199272, 24728591, 26283645, 18298873, 3406776, 21222956,
17689469, 11120503, 22016915, 13428607, 19505738, 4559997, 8757284, 11859001, 8631503, 17611020, 16124925,
25892258, 13013068, 1582288, 15390518, 15189365, 22398614, 19853935, 4852246, 21028253, 21788135, 14601835,
10675514, 5265736, 22560041, 5814468, 12734159, 5244241, 3768011, 15064087, 18247602, 13300863, 9041709,
12061745, 10542538, 19628667, 14938831, 26465806, 6006614, 20589915, 14423646, 1232727, 13317370, 17804238,
12436432, 12505876, 8422828, 125912, 11670347, 17723378, 3887546, 4567741, 20604623, 15000635, 19003178,
16588480, 21974309, 23062405, 21922614, 17672888, 22772529, 16973221, 1168307, 17630408, 25435312, 1304719,
14516543, 22484760, 15640481, 11819696, 8633226, 20592084, 2989254, 8962165, 23010211, 25930528, 8589175,
7818257, 23385615, 5963402, 18045138, 22627838, 14249330, 3807142, 7663547, 13986782, 19984239, 25188391,
26750092, 3639543, 3376937, 25083340, 13649926, 26382833, 23669509, 16440809, 10047809, 21699778, 22880535,
14148381, 14656455, 13125836, 9622625, 15536894, 7891052, 25398131, 7965869, 5667583, 22931312, 26736562,
23548628, 323706, 3146470, 24501563, 13850454, 11829823, 24485487, 14043974, 23458624, 5389324, 22176690,
25791222, 9841946, 5409778, 9002370, 14851585, 3364279, 26339404, 12530090, 6139141, 16600492, 5005716,
6623249, 19190446, 1679860, 21439381, 1040487, 20426651, 1096984, 17650945, 10969896, 25315064, 9866446,
21940221, 1556610, 13310763, 17848457, 8478144, 6031249, 17341820, 24866193, 18556055, 18298752, 5341946,
4254181, 15307633, 6184593, 3545118, 16935735, 8149239, 22744202, 1717671, 7855084, 12087393, 11643262,
16683748, 10480114, 9338996, 9008252, 9362025, 19946398, 21795628, 8362748, 20858362, 19041646, 17180450,
20393079, 7217444, 3760099, 22653594, 15661733, 2556805, 20736623, 17171429, 21633318, 16429503, 19834281,
1078018, 9071628, 20052347, 65924, 5920202, 14148027, 13834032, 15821348, 13817068, 23401440, 24050349,
2853198, 4645919, 10252652, 21905573, 17360770, 19834626, 17041845, 5335582, 1189536, 1443083, 378056, 2943193,
24207462, 10191521, 7148044, 3352294, 4122779, 12981276, 17928478, 2840176, 23555396, 25377007, 22583235,
8187037, 1364572, 17135114, 684338, 10465873, 42789, 15680087, 21620411, 25204245, 7453908, 7569420, 10645022,
9188036, 5022957, 19420858, 4217621, 13801650, 16808144, 171199, 1374787, 15879134, 25926503, 25666718,
14659715, 5766019, 9421452, 11594546, 18760954, 11618152, 5797884, 13761766, 13648840, 19552353, 23029619,
6281856, 15811628, 24924300, 22597024, 22912288, 25154635, 7093108, 573279, 7959348, 12814997, 9993777,
13820667, 19556087, 23857712, 25519959, 15627001, 11067530, 17755144, 1857310, 4130699, 20752619, 4403791,
20302966, 16814127, 25929360, 12065774, 9126000, 8551980, 1652829, 3485554, 15849467, 8424044, 1400998,
19024628, 9178995, 14198378, 312694, 4180177, 25341894, 16553436, 659513, 18269517, 3579377, 7939202, 13796891,
7303796, 14247706, 4834944, 45963, 25189823, 18801064, 25176896, 3269744, 26239677, 12940746, 15360609,
26716276, 13157906, 16377721, 12984042, 1896225, 19612183, 4837391, 24073906, 3036392, 10789487, 10511538,
18436913, 14160651, 16010724, 17221171, 1211652, 23684768, 4393456, 18425029, 1684833, 11506561, 23521758,
1089835, 18364576, 22188768, 4644812, 18742299, 3035510, 1272426, 5899330, 10827916, 11699278, 21511079,
11656332, 11636728, 25230230, 8804738, 14364348, 16695773, 6274198, 15006813, 5642664, 15352142, 26105051,
22843647, 7928117, 23311334, 6333537, 7044351, 10438195, 15772354, 10481977, 26493726, 111460, 14176423,
13810920, 2536716, 15224593, 10817728, 11804924, 14509109, 764836, 11744353, 19236807, 20278586, 9021307,
23902638, 23319983, 13777782, 15890385, 19915278, 20378667, 7813197, 6631828, 7624903, 4790310, 23500585,
26464574, 5458698, 11407486, 4275793, 6700626, 10493277, 1422453, 21668996, 2485317, 10041496, 16532458,
2477968, 12482636, 3981434, 5896983, 18432889, 1232456, 12591252, 12770475, 22559661, 249954, 25782029,
9211225, 9625590, 12663603, 8504169, 19639755, 6210885, 21427486, 5865236, 19081024, 1784158, 2042744, 4864253,
6939704, 5512609, 10068799, 26102935, 25079063, 10176164, 23688371, 16858514, 23739245, 9433052, 12307952,
24058957, 24479511, 10983464, 20638054, 3628813, 15698807, 22428303, 4346506, 282057, 2124849, 4931107,
22279371, 19744951, 5041734, 647810, 58196, 17021760, 967655, 23262800, 25028113, 13621853, 16057585, 17291653,
2195083, 18900269, 3615451, 14890259, 9507053, 26718190, 20087825, 17699268, 10732432, 22864849, 2408556,
11300542, 6668340, 9325868, 3807862, 10816379, 15122893, 16015844, 20993241, 3130685, 21161826, 24595250,
22845740, 7516056, 19183357, 21355033, 18795153, 12113317, 23770096, 3271335, 1228627, 19838347, 14386657,
5245685, 2848824, 2070400, 4426941, 7238959, 14552917, 4254283, 9382919, 6674287, 3862303, 14404326, 22020062,
7353447, 6200783, 18646153, 3506894, 19318952, 15949718, 16427001, 4315162, 11546118, 22642431, 6877196,
14562259, 22242360, 20477488, 22856338, 9257240, 15887947, 7324175, 8932885, 17717044, 15958957, 5202222,
17700276, 14504140, 2502699, 9639762, 7469059, 2061746, 9767086, 12971817, 15758345, 25492346, 11716580,
24462682, 5375934, 10455048, 17125363, 6700530, 6506921, 16208396, 1735427, 6479034, 17291287, 19093073,
18431439, 3699624, 12267204, 19803125, 20621611, 14753793, 19509141, 7940267, 20482573, 13431893, 19991570,
2664637, 18370578, 24950148, 6529219, 1490673, 11844509, 838428, 7182811, 10961324, 14503471, 16526859,
6315076, 4318536, 7534840, 15673758, 8414650, 625944, 15597392, 21487050, 20113582, 9792393, 19453660, 8726757,
19698194, 48901, 4337844, 5171025, 18203183, 17672619, 7236639, 9352515, 5160856, 13691126, 14836738, 19972487,
26709367, 23655952, 4384739, 1981310, 20335915, 2062420, 7446606, 26212464, 19550611, 5673445, 8341733,
8180865, 6815003, 2154530, 15293134, 12074417, 16377490, 4002149, 25354009, 26520724, 20062378, 17624540,
11039703, 16903260, 18627496, 24155288, 11544881, 14104214, 13758011, 5029253, 12694166, 14540401, 408780,
2329176, 5916563, 2347495, 13569330, 25655091, 8945147, 16582061, 17172194, 26620849, 16241449, 26749364,
2775932, 14105626, 21523055, 8099953, 13863481, 21333585, 1445394, 3482868, 19083027, 16771233, 16815687,
1486083, 12120599, 12253859, 16785856, 2816567, 2942479, 25996256, 21924755, 15304055, 623596, 6249972,
19855539, 13010109, 6075459, 12058860, 19687575, 12774723, 3841292, 24618859, 16883228, 11844674, 5587101,
8475851, 23302173, 652678, 18812633, 196596, 21758546, 14663445, 4940848, 7631534, 16336834, 26739928,
20786638, 6897647, 26364712, 4390581, 107787, 258962, 618723, 10243687, 1776338, 18204028, 22517306, 9886158,
4766727, 21730446, 8886190, 15539859, 17983211, 22831979, 6587874, 20735383, 11525687, 22073387, 25234074,
20751491, 3991292, 23031529, 6298470, 11864853, 16438796, 12574204, 23788125, 25613032, 8513777, 5325595,
12387159, 17002204, 21374791, 10393901, 21056609, 5764041, 8061189, 6020440, 11553852, 15451946, 18533551,
7093962, 12849009, 7905387, 2093671, 13324419, 17849150, 10583962, 7829576, 17418591, 5630893, 6791379,
16757825, 15393933, 1696624, 1363626, 26353863, 4526706, 12823229, 20482982, 19171462, 17774940, 20850218,
55278, 2153385, 26765460, 14403930, 10958363, 5957112, 2628824, 10256466, 7951087, 3840901, 24493311, 19458552,
125614, 10387892, 16966821, 18966215, 4560017, 6130078, 15021456, 16935841, 24833418, 22746242, 23476436,
13586623, 19433409, 6458126, 9709358, 18025650, 18897266, 26302246, 24400886, 5852456, 26130513, 21644614,
1841914, 24224335, 10573263, 13053580, 16656686, 24520891, 24979941, 19072831, 1905499, 14495922, 24827201,
11979836, 23553943, 12467543, 5448856, 25242946, 14918489, 5966226, 3523088, 15970110, 23229053, 5143743,
14755503, 19261281, 13985178, 9879395, 11991110, 7955235, 11637640, 7365540, 18669630, 17134451, 16278912,
270431, 25342425, 10848840, 20941807, 14084823, 1098775, 20932837, 16122887, 2412477, 9798638, 7665052,
11683064, 20905936, 17681809, 14009805, 18389720, 26658308, 20457589, 11774240, 3611372, 6638173, 25605591,
12246820, 14566209, 8324884, 1239835, 14143413, 10516350, 5185435, 1847159, 22597167, 20772845, 10887653,
3869467, 2946288, 512743, 8397059, 21880384, 26217707, 9196972, 26527150, 15355574, 5019847, 6358502, 19292411,
19965120, 12400357, 25332414, 14203876, 19083383, 9904572, 1493546, 12744214, 17850499, 485210, 5341632,
18315891, 20809399, 20255249, 12652523, 24063442, 10068897, 6633546, 16912751, 96087, 8224391, 6451735,
9634045, 2502743, 21564780, 5491813, 17888598, 17172912, 17436317, 22476282, 11496628, 4597602, 15217036,
20634891, 5397007, 10783744, 25278259, 19026527, 14533860, 18124019, 18213828, 9717785, 2987909, 14125443,
1140896, 1496936, 12336689, 19291761, 25452067, 1876379, 17011644, 18578061, 13464892, 4208344, 17757422,
17091860, 26803621, 12946276, 18664432, 17748177, 22080121, 14740707, 5317187, 14780718, 5477716, 25038448,
18787686, 15757986, 10580569, 6653714, 10649065, 2520227, 9196755, 4070469, 2972291, 19914580, 14280587,
24709887, 15147784, 16031619, 539717, 19765539, 19000002, 21977864, 12408762, 81639, 6752518, 5737420,
14765148, 11734783, 20424975, 8625747, 6283071, 19202242, 12276912, 24090481, 19765448, 1273458, 6047669,
12930703, 15372473, 951038, 11098337, 10740416, 2434580, 18807508, 4079383, 11964324, 2316754, 11155181,
16086832, 10137710, 2816329, 24186128, 7003487, 19260498, 9103495, 18024517, 16634250, 9282081, 13356771,
23348994, 5751775, 11002816, 23526838, 7551715, 3487492, 22519261, 18625732, 9217392, 13901550, 8208005,
571505, 23892040, 10585299, 21890790, 198141, 2864777, 14751261, 21580674, 10156788, 13783441, 3716952,
15369240, 9426862, 1558978, 9381295, 8484013, 17271860, 4201506, 26624413, 2568241, 20545543, 23618402,
26464591, 640286, 22337941, 9516958, 14779208, 18088364, 24252092, 22651594, 20091486, 17394644, 13664659,
19807295, 8423625, 10079032, 9147666, 2994114, 1644511, 11630665, 3678498, 13966316, 2496125, 7046971, 126787,
9006252, 9711195, 5094141, 12492525, 17122610, 16370857, 14271459, 10064777, 12259385, 4341222, 23185730,
24227894, 19101058, 4020243, 25700902, 17918930, 10960916, 7356644, 14458289, 21978255, 1214665, 23669260,
1544998, 24085736, 11172309, 6544923, 14985889, 6616975, 24563420, 21081142, 15565454, 13324475, 948273,
4968401, 25183467, 10327889, 24917726, 8503679, 958822, 14451939, 7604215, 16427227, 20360297, 23708345,
24905059, 9059490, 6931986, 401054, 1761831, 16049820, 19265316, 4341478, 25275311, 3266882, 20853502,
19864980, 5817307, 23100157, 23329620, 14204607, 24831590, 22660309, 21745745, 23413738, 8541658, 12208611,
14696557, 5134606, 15034552, 11111605, 14207721, 17406404, 6016118, 16671650, 291342, 25282476, 17630002,
19428571, 5025021, 12125395, 6946914, 8746638, 18510175, 22014942, 21197178, 13980950, 19957387, 2847011,
12792169, 4864449, 10099398, 12964287, 18978217, 8332842, 789764, 21134481, 22067922, 15540175, 3700721,
3313824, 20263732, 9812323, 23295423, 26330250, 16999125, 3249193, 17258113, 23204171, 9550152, 25004670,
3105653, 16240153, 10949723, 3817034, 24521423, 13878487, 2829016, 11917852, 15569805, 12184257, 10638909,
3197562, 18318824, 26608706, 1877831, 6986941, 30288, 7498918, 17154883, 15271567, 14627409, 3054670, 16864900,
26558000, 16332652, 9194877, 6331510, 11996030, 5902935, 23454563, 2222013, 10589881, 11656117, 17265174,
14426803, 11289830, 22881930, 10747717, 8408035, 23746217, 9830922, 4830557, 21539794, 4129690, 12464726,
14897956, 14231690, 16214480, 9448094, 26696716, 20361601, 7971923, 16156788, 16746067, 15061594, 1994165,
8938911, 23170125, 3519143, 18993925, 6386126, 3153440, 5506578, 8723025, 20684188, 10928223, 22680545,
15741782, 5982393, 13103355, 17244093, 15558406, 22297795, 16876231, 1435662, 8868312, 12466411, 11279217,
15638360, 15395486, 8362676, 18036365, 4299791, 984309, 23592288, 3476611, 14973637, 6201789, 6126781, 7748344,
2463353, 2808594, 14281542, 23199579, 10616676, 2657092, 2536539, 9969604, 12728332, 22392224, 4764829,
13873333, 26798444, 7100904, 13188505, 12567248, 2611504, 13646624, 10141682, 6094790, 20088127, 25148936,
20846535, 9549041, 16472081, 657690, 21056355, 9701620, 12502573, 15768065, 26505660, 19741462, 19387014,
1671647, 5078467, 7094473, 12280249, 17010232, 26363583, 23644749, 23890001, 745176, 10506421, 17910689,
15162020, 15104771, 16271340, 21729945, 6074144, 25127377, 11896103, 25399020, 22531380, 2389104, 15852753,
26106565, 12967816, 12383596, 17366982, 4382931, 8946164, 20931633, 19681944, 2877503, 18463214, 25696687,
15848416, 9341216, 24503897, 10728812, 19682667, 26686890, 11259925, 12701695, 4539485, 15696410, 21528543,
22770050, 17102558, 19584556, 24804751, 16616549, 18887499, 1168559, 17136729, 21723836, 6186147, 4910900,
22487276, 2972467, 24993462, 4849992, 6136561, 8285745, 9167786, 5132975, 4379381, 17115949, 2539892, 7986879,
2842556, 2723835, 16364359, 15318847, 2503229, 14162773, 20353366, 16478534, 10365786, 21458663, 8839053,
2046483, 8737659, 10902391, 3096132, 4151865, 14118659, 12896051, 1346992, 10341800, 16822474, 8766369,
11097159, 17296660, 5267486, 8931168, 13124199, 12785124, 7823468, 26301248, 1444656, 21522404, 13325518,
4495424, 6556388, 25677372, 25913699, 16289570, 6167607, 6375398, 3570927, 12222426, 25164512, 20193348,
8335446, 1903685, 14754073, 19856909, 26127741, 25812939, 26058102, 13949826, 18887956, 2611769, 23227333,
1542962, 3584092, 5108091, 20587004, 8497100, 20639938, 26313000, 7289705, 24588129, 675543, 7028048, 21520869,
9095290, 11244997, 9467284, 22704380, 4632638, 12973058, 3944754, 24895193, 13228226, 22227835, 5586802,
25017112, 20281959, 13886411, 16404128, 13221023, 3889809, 26502539, 9352843, 25111016, 26193309, 1715368,
11963821, 23085796, 19200932, 21625491, 14394737, 2287823, 22088928, 17110468, 23844239, 23462763, 6177125,
26411194, 20904893, 11147997, 24943932, 8710666, 10387395, 1675277, 974476, 20647518, 416546, 26586235,
8722355, 964543, 1556957, 9669028, 8184921, 9096764, 405701, 22510870, 18638733, 3000483, 16540625, 4934119,
19322078, 19402198, 22971167, 15182560, 12737907, 10189824, 1562579, 2626249, 22879474, 25017595, 26150020,
12023360, 10927005, 4163511, 10834790, 9480560, 533905, 80235, 11459832, 16438014, 19091769, 23377298, 6623889,
3207707, 14746064, 17538469, 24141228, 25673844, 5450870, 26254943, 12974, 10560924, 10385815, 10017352,
22585854, 10538732, 12020313, 20762953, 19731910, 6920038, 15059723, 23661595, 19992547, 24566859, 13594606,
10829985, 13142685, 18474808, 14156122, 25244174, 21049804, 2125431, 5998513, 6680016, 2314397, 14011757,
8276995, 8054317, 18958179, 20984807, 1319757, 23593140, 14912735, 17665309, 14739323, 12504133, 20300636,
26234236, 15133072, 15764847, 2620238, 8528448, 19478791, 3438528, 1323804, 1959054, 14489709, 11263373,
25853708, 629778, 26380000, 19318736, 14219703, 19589899, 13833754, 3799034, 23996054, 10066071, 8380120,
15485511, 6405066, 1282834, 14534233, 3853545, 19659876, 10339896, 23382760, 18554023, 2730751, 15525172,
2301500, 11654074, 2147390, 23603140, 6701728, 14869001, 3065924, 15799960, 17465454, 21632245, 7750652,
18397407, 5114655, 10883445, 4671998, 23755207, 17864753, 26744004, 7374137, 14124915, 5763548, 14205372,
765197, 4757512, 24957870, 24073419, 13438556, 3311992, 7233094, 18721488, 8088942, 26211361, 565244, 14294296,
16456636, 24041428, 12002334, 20159525, 2585540, 6746636, 3958040, 2892700, 1971952, 10765830, 22382524,
4199934, 16104081, 11921823, 23468984, 1454374, 2568651, 15937253, 23737000, 9625158, 8710939, 13963243,
13614319, 18768300, 465437, 18989466, 3922163, 26109951, 25305994, 24759583, 2512859, 26027024, 537087,
26408847, 2135912, 26541104, 11094467, 19795739, 6755852, 14465410, 3098596, 7751234, 2831237, 22288264,
10643704, 8815555, 20825539, 22444191, 25879446, 9326355, 25299850, 2979386, 23521527, 4555643, 6592551,
5675088, 26043505, 4498501, 23057528, 12142932, 13139703, 19256693, 21331065, 18287029, 24165100, 14451589,
1762562, 11616484, 13787028, 10031046, 8484890, 17628511, 2931074, 9349384, 24310976, 26096693, 9398612,
23923620, 20854025, 14698941, 25824422, 16004429, 12613451, 9104671, 4854586, 24639575, 16573146, 26550428,
20222795, 18754402, 2774787, 21028415, 2326749, 23798806, 17565042, 1420786, 5518051, 7235424, 1559612,
18741285, 25044526, 20702919, 9560235, 18671758, 11859847, 746915, 1497975, 26524771, 7047472, 735641, 333626,
11613021, 18048161, 23513939, 26446008, 3833511, 15975230, 2746802, 4803608, 23030206, 12384585, 23795606,
20044242, 6915882, 20775292, 19288999, 4514224, 20662887, 17249762, 7698471, 19859155, 811317, 6290813,
14411091, 14347612, 1777693, 14786099, 15108700, 10860331, 12679041, 6271002, 12307703, 9826087, 21346833,
18678058, 19804235, 3295694, 15144115, 17039365, 25639455, 6577125, 19522763, 26671475, 24114898, 6469852,
6891778, 18051714, 25794139, 4959836, 14566785, 10327367, 1878198, 15203739, 25828506, 22088196, 7363474,
15986971, 23970277, 1429144, 2220149, 23247440, 4117031, 2180320, 20792086, 24144421, 20150133, 26396646,
18908692, 5994850, 14789561, 19514245, 18413104, 776740, 3612614, 3256513, 25294472, 22117513, 5866958,
5434418, 3594138, 20585605, 18994926, 5845938, 15427546, 4219121, 7902095, 6388830, 18031179, 13971848,
4879878, 23288316, 23526584, 1342873, 22469024, 18582246, 14382186, 2749665, 25220178, 2849662, 26199089,
3780450, 3407807, 25576331, 19236263, 6853640, 6538731, 5248534, 14844205, 25067740, 14060535, 617112, 9282925,
23309045, 15810118, 13182622, 19742231, 8809873, 3872796, 840920, 17844740, 1033055, 3070804, 24147470,
3329073, 23801970, 18773189, 7387463, 4039614, 21490366, 9155475, 23312331, 2134521, 18409454, 21717956,
23152357, 2389564, 12450195, 9391734, 26006421, 15524230, 8029226, 25209704, 17689274, 4006494, 18524869,
26703724, 22131013, 20939683, 16803919, 6562356, 9994845, 21242874, 21240766, 1215751, 13016069, 2658533,
22445173, 19952433, 8317843, 13798968, 11057256, 5629530, 19776315, 11397228, 4417317, 7800003, 11369397,
8470888, 21880333, 14323645, 5014128, 11621918, 17188910, 9518346, 12244619, 2081195, 11428636, 4586075,
20475040, 24681958, 2598301, 17300570, 12230580, 2501859, 158772, 14021806, 10610419, 21547581, 21213797,
20943371, 1105792, 23917096, 20704546, 15639171, 22204487, 12839735, 13150103, 16051152, 9265665, 22149903,
20437481, 11394356, 7717667, 17000630, 10791108, 25465880, 10392090, 13006897, 13988860, 22665761, 1431088,
16531882, 12060757, 4376241, 26493034, 15990142, 3264665, 16788079, 1528811, 24039607, 20499956, 4524341,
12078612, 25211749, 12462867, 21013513, 9249225, 18799688, 4818137, 12426938, 25608062, 24248757, 1549345,
6972235, 10905645, 14801707, 7799808, 3290631, 61719, 21692788, 24006872, 12940274, 1816315, 24633808, 4551787,
5850583, 23075626, 15035959, 15832122, 20361469, 22442399, 12973110, 23022429, 12307169, 8276787, 19470296,
19339008, 9080899, 25057124, 14663057, 9224018, 11674563, 12825508, 11258560, 2037277, 16159442, 18062860,
10264714, 12778747, 22705077, 18780806, 24079398, 21339603, 3518572, 19386498, 1410534, 18355975, 20458113,
25252182, 23654883, 22995422, 1279717, 7030374, 1926700, 26095800, 25010230, 391858, 21283173, 7468327,
10287466, 18300952, 22137610, 17521135, 12826630, 9520569, 24016811, 18862978, 22519076, 4363839, 5017528,
16998135, 9309452, 20719446, 19480197, 20618974, 879108, 13383395, 26022536, 20904120, 20725323, 26406474,
14508829, 20752473, 17243236, 10386425, 5944827, 20606699, 8153192, 6173728, 12374412, 11365748, 11931057,
9387047, 26102019, 6874162, 685604, 15428323, 16546516, 7834516, 11810557, 15495365, 1338159, 22799354,
18843900, 8148061, 23609675, 5215923, 4452871, 5066025, 18430136, 26769272, 12757188, 9449534, 10783555,
1606976, 24813279, 14677328, 24069231, 14704995, 15813794, 8469220, 7784193, 14632657, 20964728, 23227270,
26133404, 9323973, 2452788, 25843982, 20507926, 21045350, 10413630, 8811502, 23831255, 26689696, 14876923,
9982554, 19650258, 977369, 21990564, 1848802, 12456924, 19420663, 23714263, 15305283, 17821294, 16078902,
15383176, 25982298, 593444, 17146991, 16224914, 4993530, 16108387, 8070631, 825931, 15140052, 8510692,
19490616, 4089409, 656911, 708357, 21690751, 4997910, 17409906, 10850931, 16911630, 20183780, 21251016,
16503683, 20489333, 4209416, 4640487, 284963, 7838091, 11339566, 25392036, 14829924, 13525717, 12216121,
12423043, 15197254, 24746848, 20133439, 19590234, 5202787, 2900042, 12374849, 1386631, 6566474, 5045090,
19836502, 9812662, 5571237, 6050115, 21090598, 1121349, 26271126, 23013784, 17544181, 14456862, 19137774,
17414569, 7457703, 13380118, 4910515, 1972283, 16752710, 23153736, 21665643, 21836276, 402372, 6745501,
2773329, 7891186, 16821806, 25348146, 7758662, 14505456, 13270306, 18674697, 11491283, 7984234, 10313125,
2564158, 6710115, 26234840, 19145802, 24501612, 15280318, 17692796, 4334550, 20488415, 18460032, 2020927,
4640651, 24797734, 11535768, 25710837, 12282417, 16083448, 9243433, 9225857, 24803936, 18073905, 19091403,
14616507, 15240920, 4014476, 15369997, 10473145, 23935368, 5130477, 10617747, 4514708, 859198, 13475784,
17500050, 17350657, 4689471, 12007585, 26587058, 13586392, 25190597, 15489568, 10597781, 24001358, 2028959,
13310664, 20465660, 24530986, 23693896, 8248279, 17185806, 2542142, 3847863, 7977369, 22109016, 15062308,
21084086, 16902488, 20860905, 8478229, 14152690, 20052207, 23343626, 5256493, 17750912, 7628309, 10325935,
21785591, 25324485, 12831216, 13251089, 9102836, 5960870, 5967530, 24214762, 2225815, 13418644, 26599958,
19102075, 7356866, 9742517, 21032675, 15145317, 15455542, 56507, 10870459, 5184667, 17951992, 62686, 13875158,
25265687, 8337301, 24643728, 603563, 24324083, 16625007, 3303319, 20766401, 11098684, 346686, 19600490,
12561792, 12157467, 749003, 10826309, 16674626, 21059831, 1970472, 25177183, 16911598, 18792883, 20805759,
10014545, 2944853, 8222994, 9748673, 9207241, 7154187, 18207914, 14549097, 20302075, 4670496, 4601303, 1040335,
22658260, 18654, 9641374, 23897737, 21616562, 6851559, 4202329, 4486581, 2670684, 13942712, 2611998, 18659251,
21729484, 16770799, 25208925, 7532217, 6398365, 3846075, 11837089, 15289582, 7660858, 11932519, 25841297,
19399054, 167923, 15575142, 18944986, 13600246, 6255922, 21334274, 12911313, 3190033, 6947300, 9863324,
22575609, 12745436, 18622875, 548719, 4063960, 8702404, 4316027, 865357, 14926237, 17177279, 7752705, 14168022,
26761083, 7056686, 7350542, 13999279, 5845848, 12491922, 24524093, 23995624, 14272788, 8247141, 26411861,
20526297, 21573665, 3496402, 18214069, 23315981, 24878376, 9193780, 12597491, 19702891, 6400036, 2509142,
5484542, 20331439, 17472765, 8574838, 6652974, 22125015, 5024090, 21158088, 11319087, 844726, 13720291,
24327631, 1337306, 22684063, 1043877, 13638172, 15657319, 18718242, 19778990, 20704182, 20879959, 1793380,
2173627, 26284522, 22587686, 6882229, 9900577, 8790969, 16000937, 12993553, 24264819, 9902338, 4049387,
22523757, 12013622, 18459110, 21254276, 15923042, 14015481, 24257326, 21960421, 3286637, 25510400, 13537624,
22225405, 3820946, 7777024, 317190, 19566398, 20387820, 8181184, 21909687, 11829481, 14704720, 2910570,
13525756, 12422191, 8191020, 4058887, 22914720, 25486281, 19720362, 3146727, 15639446, 16770882, 23559076,
12720650, 15542155, 20452384, 24926442, 3344020, 17006967, 6790275, 3305696, 2553995, 445127, 6924436,
23084357, 18981553, 13632840, 11996748, 26269331, 3881440, 7741579, 13535782, 1807659, 9014611]
test_problem = GraphV2Problem(problem_type="Metric TSP", n_nodes=n_nodes, selected_ids=selected_ids,
cost_function="Geom", dataset_ref="Asia_MSB")
test_problem.edges, node_coords = mock.recreate_edges(test_problem)
print("edges", test_problem.edges)
print("Problem", test_problem)
lkh_solver = LKHSolver(problem_types=[test_problem])
start_time = time.time()
# Run the solver to get the tour
route = asyncio.run(lkh_solver.solve_problem(test_problem))
routes = [route]
visualize_routes(node_coords, routes)
# Calculate total distance of the tour
total_distance = lkh_solver.calculate_total_distance(route, test_problem.edges)
print(f"{lkh_solver.__class__.__name__} Tour: {route}")
print(f"Total distance of the tour: {total_distance}")
print(f"{lkh_solver.__class__.__name__} Time Taken for {n_nodes} Nodes: {time.time() - start_time}")
#optimize phase
start_improve_time = time.time()
optimized_route = aggressive_single_iteration(route, test_problem.edges)
print(f"Time taken for improvement: {time.time() - start_improve_time}")
# Visualize both routes for comparison
routes_optimize = [optimized_route]
visualize_routes(node_coords, routes_optimize)
initial_distance = lkh_solver.calculate_total_distance(route, test_problem.edges)
final_distance = lkh_solver.calculate_total_distance(optimized_route, test_problem.edges)
print(f"Initial distance: {initial_distance}")
print(f"Final distance: {final_distance}")
improvement = ((initial_distance - final_distance) / initial_distance) * 100
print(f"Improvement: {improvement:.2f}%")
Editor is loading...
Leave a Comment