2-opt: развернуть кусок маршрута и убрать пересечения

Если ты объяснишь, почему ход 2-opt - это разворот куска, посчитаешь его выигрыш без пересчёта маршрута и знаешь, что у локального оптимума 2-opt нет пересечений, листай до «Теперь сам».

Как думаешь, что значит «поменять два ребра»

Маршрут двойного дерева из прошлой главы содержал переезд через всю карту: из правого нижнего угла в левый верхний и обратно. На рисунке такие маршруты выдают себя сразу - пересечения рёбер, похожие на восьмёрку. Человек с карандашом распутывает восьмёрку за секунду.

Ответь себе до чтения: что именно сделать с маршрутом в коде, чтобы восьмёрка стала петлёй? Поменять местами два несоседних города? Не поможет: это четыре новых ребра вместо четырёх старых, и пересечение может остаться. Правильный ход трогает ровно два ребра, но требует развернуть всё, что между ними.

На что это похоже

Шнурок, завязанный восьмёркой вокруг двух гвоздей. Чтобы получить простую петлю, перекрещенные отрезки разнимают и соединяют концы иначе: левый с левым, правый с правым. Но тогда одну из половинок шнурка приходится перевернуть - иначе концы не сойдутся в одну петлю, а распадутся на две.

В маршруте половинка - это кусок списка городов, и «перевернуть» значит записать его в обратном порядке. Сами города и все рёбра внутри куска остаются те же: меняются только два ребра на стыках.

Механизм: два ребра и разворот

Маршрут … a, b, …, c, e, …. Убираем рёбра a-b и c-e. Соединить концы можно ещё двумя способами, но a-e и b-c распадаются на два цикла. Остаётся a-c и b-e: маршрут … a, c, …, b, e, … - кусок от b до c развёрнут.

было:   a → b → x → y → c → e
стало:  a → c → y → x → b → e

выигрыш = d(a,b) + d(c,e) − d(a,c) − d(b,e)

Внутренние рёбра куска (b-x, x-y, y-c) никуда не делись - их просто проходят в обратную сторону, а при симметричных расстояниях это ничего не стоит. Поэтому выигрыш - четыре расстояния, и проверка одного соседа стоит O(1). Соседей у маршрута из n городов около n² / 2.

Почему исчезают пересечения. Если рёбра a-b и c-e пересекаются в точке p, то по неравенству треугольника d(a,c) ≤ d(a,p) + d(p,c) и d(b,e) ≤ d(b,p) + d(p,e). Сложив, получаем d(a,c) + d(b,e) ≤ d(a,b) + d(c,e), причём строго, если точки не лежат на одной прямой. Значит, любое пересечение - улучшающий ход, и в локальном оптимуме 2-opt пересечений нет.

Правило

Ход 2-opt убирает рёбра a-b и c-e, ставит a-c и b-e и разворачивает кусок от b до c; выигрыш равен d(a,b) + d(c,e) − d(a,c) − d(b,e). Поиск делает ходы с положительным выигрышем, пока они есть. На плоскости в локальном оптимуме 2-opt нет пересекающихся рёбер, но постоянной гарантии приближения у него нет.

Разбор: маршрут двойного дерева на восьми точках

Те же восемь точек и тот же стартовый маршрут 0, 7, 4, 2, 5, 1, 6, 3 длиной 40,87, что в уроке о коммивояжёре. Оптимум, найденный там перебором, - 32,23. dva_opt проходит все пары рёбер и делает каждый ход с выигрышем больше 0.000001 - поэтому итог - локальный оптимум с точностью до этого порога. Порог защищает от бесконечных «улучшений» на ошибках округления.

import math

def matrica(tochki):
    d = []
    for a in tochki:
        stroka = []
        for b in tochki:
            dx = a[0] - b[0]
            dy = a[1] - b[1]
            stroka.append(math.sqrt(dx * dx + dy * dy))
        d.append(stroka)
    return d

def dlina(d, m):
    s = 0
    for i in range(len(m)):
        s = s + d[m[i - 1]][m[i]]
    return s

def dva_opt(d, m):
    n = len(m)
    hodov = 0
    uluchshilos = True
    while uluchshilos:
        uluchshilos = False
        for i in range(n - 1):
            for j in range(i + 2, n):
                a = m[i]
                b = m[i + 1]
                c = m[j]
                e = m[(j + 1) % n]
                vygoda = d[a][b] + d[c][e] - d[a][c] - d[b][e]
                if vygoda > 0.000001:
                    m = m[:i + 1] + m[i + 1:j + 1][::-1] + m[j + 1:]
                    hodov = hodov + 1
                    uluchshilos = True
    return [m, hodov]

tochki = [[0, 0], [2, 7], [6, 1], [8, 6], [3, 3], [9, 0], [5, 9], [1, 4]]
d = matrica(tochki)
start = [0, 7, 4, 2, 5, 1, 6, 3]
itog = dva_opt(d, start)
print(round(dlina(d, start), 2), itog[0], itog[1],
      round(dlina(d, itog[0]), 2))

40.87 [0, 7, 1, 6, 3, 5, 2, 4] 6 32.23

Шесть ходов - и 32,23, ровно оптимум. Переезд через всю карту 5 → 1 исчез: теперь маршрут идёт от 0 вверх через 7, 1, 6, по правому краю вниз через 3, 5 и возвращается через 2 и 4. Ни одного пересечения - и, в этот раз, лучший маршрут вообще.

Каждая проверка стоила четыре расстояния из таблицы, три сложения и одно сравнение, а пар рёбер на восьми точках двадцать с небольшим. Весь поиск - около тысячи ста шагов по счётчику движка курса. Перебор из урока о коммивояжёре потратил на тот же ответ больше ста сорока тысяч.

Разбор: хороший старт, плохой финиш

25 случайных точек на квадрате 100 × 100. Два старта: города по номерам - заведомо ужасный маршрут зигзагом по всей карте - и маршрут «в ближайший непосещённый город». Каждый доводится 2-opt до локального оптимума.

import math
import random

def matrica(tochki):
    d = []
    for a in tochki:
        stroka = []
        for b in tochki:
            dx = a[0] - b[0]
            dy = a[1] - b[1]
            stroka.append(math.sqrt(dx * dx + dy * dy))
        d.append(stroka)
    return d

def dlina(d, m):
    s = 0
    for i in range(len(m)):
        s = s + d[m[i - 1]][m[i]]
    return s

def dva_opt(d, m):
    n = len(m)
    hodov = 0
    uluchshilos = True
    while uluchshilos:
        uluchshilos = False
        for i in range(n - 1):
            for j in range(i + 2, n):
                a = m[i]
                b = m[i + 1]
                c = m[j]
                e = m[(j + 1) % n]
                vygoda = d[a][b] + d[c][e] - d[a][c] - d[b][e]
                if vygoda > 0.000001:
                    m = m[:i + 1] + m[i + 1:j + 1][::-1] + m[j + 1:]
                    hodov = hodov + 1
                    uluchshilos = True
    return [m, hodov]

def blizhajshij(d):
    n = len(d)
    m = [0]
    byl = [False] * n
    byl[0] = True
    for shag in range(n - 1):
        luchshij = -1
        for v in range(n):
            if not byl[v]:
                if luchshij == -1 or d[m[-1]][v] < d[m[-1]][luchshij]:
                    luchshij = v
        byl[luchshij] = True
        m.append(luchshij)
    return m

random.seed(7)
tochki = []
for i in range(25):
    tochki.append([random.randint(0, 100), random.randint(0, 100)])
d = matrica(tochki)
for start in [list(range(25)), blizhajshij(d)]:
    itog = dva_opt(d, start)
    print(round(dlina(d, start), 1), itog[1],
          round(dlina(d, itog[0]), 1))

1375.6 45 358.5
409.4 5 389.8

Старт по номерам: 1375,6, сорок пять ходов, финиш 358,5. Старт по ближайшему: 409,4 - втрое лучше, - пять ходов, финиш 389,8. Хороший старт привёл к худшему локальному оптимуму.

Это не парадокс, а свойство локального поиска. Маршрут «в ближайший» уже почти без пересечений: 2-opt быстро нашёл ближайший холм и остановился. Ужасный старт заставил поиск перекроить маршрут целиком, и по дороге он забрёл на холм повыше. Вывод для практики: качество старта и качество финиша - разные вещи, и сравнивать их можно только замером на многих стартах.

Что ломается без этого

Разворачивают не тот кусок. Если поставить рёбра a-c и b-e, не развернув кусок, список городов описывает не тот маршрут, а длина, посчитанная по формуле выигрыша, расходится с настоящей. Проверка: после каждого хода пересчитать длину целиком хотя бы в отладке.

Нет порога на выигрыш. Вещественные расстояния дают «выигрыш» 10⁻¹⁵ на ошибках округления, и поиск качает маршрут туда-сюда вечно.

Ждут гарантии. Постоянного множителя у 2-opt нет: построены входы, где его локальный оптимум хуже лучшего маршрута во столько раз, сколько растёт вместе с числом городов, и входы, где ходов до остановки экспоненциально много. На случайных точках на плоскости он даёт маршрут примерно на 5% длиннее оптимума (замеры Джонсона и Макгиоха) и останавливается быстро.

Асимметричные расстояния. Разворот куска меняет направление внутренних рёбер. Если туда и обратно стоят по-разному (односторонние улицы), выигрыш - уже не четыре слагаемых, и формула врёт.

Зачем это в работе

Развоз, сборка заказов на складе, обход точек дроном - везде, где маршрут строится жадно, 2-opt дочищает его за миллисекунды. Это стандартный последний шаг после любого построения маршрута. Его расширения - 3-opt (три ребра) и метод Лина-Кернигана (1973), где число меняемых рёбер подбирается на ходу, - лежат в основе программ, которые находят маршруты через миллионы городов с отрывом от нижней границы в доли процента.

Теперь сам

1. Маршрут 0, 1, 2, 3 по вершинам квадрата (0, 0), (1, 1), (1, 0), (0, 1). Какие рёбра пересекаются, какой ход 2-opt их распутает и какой маршрут получится?
2. В маршруте … a, b, x, y, c, e, … сделан ход по рёбрам a-b и c-e. Запиши новый маршрут.
3. Почему 2-opt не меняет местами два города, а разворачивает кусок?