Untitled

 avatar
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