Untitled

from ortools.linear_solver import pywraplp

def calculate_distance(point1, point2):
    return ((point1[0] - point2[0]) ** 2 + (point1[1] - point2[1]) ** 2) ** 0.5

def tsp_integer_programming(points):
    num_points = len(points)
    distances = [[calculate_distance(points[i], points[j]) for j in range(num_points)] for i in range(num_points)]

    # Создание солвера
    solver = pywraplp.Solver.CreateSolver('SCIP')

    # Создание переменных: x[i, j] равно 1, если путь из города i в город j присутствует в маршруте
    x = {}
    for i in range(num_points):
        for j in range(num_points):
            if i != j:
                x[i, j] = solver.BoolVar(f'x_{i}_{j}')

    # Ограничения: каждый город должен быть посещен только один раз
    for i in range(num_points):
        solver.Add(solver.Sum([x[i, j] for j in range(num_points) if i != j]) == 1)

    # Ограничения: каждый город должен быть покинут только один раз
    for j in range(num_points):
        solver.Add(solver.Sum([x[i, j] for i in range(num_points) if i != j]) == 1)

    # Ограничения: устранение подциклов
    u = [solver.IntVar(1, num_points - 1, f'u_{i}') for i in range(num_points)]
    for i in range(1, num_points):
        for j in range(1, num_points):
            if i != j:
                solver.Add(u[i] - u[j] + (num_points - 1) * x[i, j] <= num_points - 2)

    # Целевая функция: минимизация суммарного расстояния
    solver.Minimize(solver.Sum([distances[i][j] * x[i, j] for i in range(num_points) for j in range(num_points) if i != j]))

    # Решение задачи
    status = solver.Solve()

    # Получение оптимального пути и минимального расстояния
    optimal_order = []
    if status == pywraplp.Solver.OPTIMAL:
        current_city = 0
        while True:
            optimal_order.append(current_city)
            next_city_found = False
            for j in range(num_points):
                if j != current_city and x[current_city, j].solution_value() == 1:
                    current_city = j
                    next_city_found = True
                    break
            if not next_city_found or current_city == 0:
                break

    min_distance = sum(distances[optimal_order[i]][optimal_order[i + 1]] for i in range(num_points - 1))
    min_distance += distances[optimal_order[-1]][optimal_order[0]]

    return optimal_order, min_distance

def input_points(num_points):
    points = []
    for i in range(num_points):
        x, y = map(float, input(f"Введите координаты точки {i+1} (x y): ").split())
        points.append((x, y))
    return points


num_points = int(input("Введите количество точек: "))
points = input_points(num_points)

optimal_order, min_distance = tsp_integer_programming(points)
modified_order = [x + 1 for x in optimal_order]
print("Оптимальный путь:", modified_order)
print("Расстояние:", round(min_distance, 2))