Untitled
unknown
plain_text
2 months ago
59 kB
4
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