Untitled

unknown
python
23 days ago
3.3 kB
1
Indexable
Never
```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))
```