Прогулка по мостам Кёнигсберга с ORtools / Хабр

На выходных впервые удалось выбраться в Калининград. Я уделил немало внимания исследованию уровня жизни и благополучия области, в основном, ориентируясь на стоимость покупки/аренды жилья, цены в ресторанах и заработок таксистов. Данные достаточно доступные и позволяют сформировать общее представление о положении дел в городе/области.

Помимо экономической составляющей, конечно, старался погрузиться в культурный/исторический аспект жизни города. За короткий промежуток времени достаточно сложно проникнуться всеми особенностями, однако в Калининграде я бы выделил верное следование ограничениям скорости! Благодаря этому, возникает ощущение безопасности, замедления времени и спокойствия.

История города богатая, и в этом мешке событий я нашел кое-что интересное для себя. Речь пойдет о задаче семи пешеходных мостов Кёнигсберга. В свое время Эйлер в процессе размышлений над решением этой задачи положил начало теории графов. В статье рассмотрим задачу с позиции задачи линейного программирования и подтвердим результаты трехсотлетней давности с помощью Python и OR-Tools.

Семь мостов Кёнигсберга

По легенде еще с прусских времен жители Кёнигсберга задавались вопросом: как пройти все пешеходные мосты города так, чтобы маршрут проходил по каждому из мостов ровно один раз. Эйлер в рамках своей деятельности по решению этой задачи комментировал следующее: «Как я слышал, некоторые отрицают, что это можно сделать, другие сомневаются, но никто не подтверждает такой возможности».

В конце 1542 года было семь мостов и четыре различных берега (Альтштадт, Кнайпхоф, Ломзе и Форштадт). В настоящее время кол-во мостов немного поубавилось, но берега осталиcь прежними. Далее, будем рассматривать исторический период, когда все семь мостов были на месте с теми же условиями задачи какие использовал Эйлер.

В теории графов есть термин Эйлерова цепь - это путь, проходящий по всем рёбрам графа и только по одному разу. Очевидно, прослеживается связь термина и задачи о кёнигсбергских мостах. Собственно, задача состоит в том, чтобы найти Эйлеров путь.

Попробуем развеять таинственность вокруг задачи с помощью современных инструментов для мат. моделирования и решения задач.

Задача удовлетворения ограничений

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

Сформулируем потоковую модель с использованием целочисленного линейного программирования (ILP). Для этого введем набор решающих переменных и сформулируем ограничения. Задача состоит в нахождении допустимого решения, поэтому целевая функция отсутствует. Перейдем к обозначениям:

Индексы

$i, j \in V$ - множество узлов сети (соответствуют берегам);

$m \in M$ - множество мостов;

$(i, j, m) \in E$ - множество направленных переходов по мостам (для каждого моста два направленных ребра);

Переменные

- бинарная переменная, узел начала пути (ограничений на точку старта нет);

- бинарная переменная, узел окончания пути (ограничений на окончание маршрута нет);

$b_{ijm}$ - бинарная переменная, проход по мосту в направлении

Ограничения

В задаче указано, что нужно пройти по всем мостам и ровно один раз. В случае потоковой модели добавляются еще несколько ограничений: на связность пути - ребра должны быть последовательными; одна точка начала и одна точка окончания маршрута. Ограничения имеют следующий вид:

Одна точка начала пути (один исток):

$\sum_{i \in I} s_i = 1;$

Одна точка окончания пути (один сток):

$\sum_{i \in I} t_i = 1;$

Баланс входов и выходов в узел сети:

$s_i + \sum_{j \in I}\sum_{m \in M} b_{jim} = t_i + \sum_{j \in I}\sum_{m \in M} b_{ijm}, \quad \forall i \in I;$

Необходимо пройти по каждому мосту ровно один раз (только в одном направлении):

$b_{ijm} + b_{jim} = 1, \quad \forall m \in M.$

Вариант постановки задачи не является ее решением. Поэтому перейдем к способу решения сформулированной задачи в виде ILP.

Нахождение Эйлерова пути с OR-Tools

Библиотека OR-Tools позволяет описать задачу ILP и найти ее решение. Для реализации решения будем использовать cp-sat solver, встроенный в OR-Tools. Начнем с уста��овки библиотеки:

pip install ortools

Инициализируем объект модели и входные данные. Каждый мост свяжем с берегом начала и берегом окончания. Для учета направления перехода по мосту введем дополнительный постфикс к названию моста _r - reverse. Таким образом, мы сможем закодировать мосты с использованием только их названия.

from ortools.sat.python import cp_model

model = cp_model.CpModel()

# Участки города, разделенные рекой Преголя
areas = ["Altstadt", "Kneiphof", "Vorstadt", "Lomse"]

# Список мостов
bridges = {
    "lavochniy": ("Altstadt", "Kneiphof"),  # Лавочный мост
    "zeleniy": ("Kneiphof", "Vorstadt"),  # Зелёный мост
    "rabochiy": ("Kneiphof", "Vorstadt"),  # Рабочий мост
    "kuznechniy": ("Altstadt", "Kneiphof"),  # Кузнечный мост
    "derevyanniy": ("Altstadt",  "Lomse"),    # Деревянный мост
    "visokiy": ("Vorstadt", "Lomse"),     # Высокий мост
    "medoviy": ("Kneiphof", "Lomse")      # Медовый мост
}

# Направленные ребра
arcs = {}
for bridge, (_from, _to) in bridges.items():
  arcs[bridge] = (_from, _to)
  arcs[bridge + "_r"] = (_to, _from)

Инициализируем переменные модели. Выше описаны три типа переменных, заведем для них отдельные словари.

# Переменные начала движения
S = {}  # Словарь с переменными start
T = {}  # Славрь переменных terminate

for area in areas:
  var_name = f"s_{area}"  # Название переменной
  S[area] = model.NewBoolVar(name=var_name)

  var_name = f"t_{area}"  # Название переменной
  T[area] = model.NewBoolVar(name=var_name)

# Переменные прохода по мосту
E = {}  # Словарь переменных проходов по мосту (ребра)

for arc in arcs:
  var_name = f"b_{arc}"  # Название переменной
  E[arc] = model.NewBoolVar(name=var_name)

Передадим в модель сформулированные ограничения:

# Ограничение: ровно одна точка начала движения
model.AddExactlyOne(S.values())

# Ограничение: ровно одна точка завершения движения
model.AddExactlyOne(T.values())

# Ограничения: баланс входов и выходов в area
for area in areas:
  # Переменная начала маршрута в area
  start_var = S[area]
  # Переменная окончания маршрута в area
  t_var = T[area]
  # Список входящих потоков в area
  lst_in_vars = [var for key, var in E.items() if arcs[key][1] == area]
  # Список исходящих потоков из area
  lst_out_vars = [var for key, var in E.items() if arcs[key][0] == area]

  # Добавление ограничения в модель
  model.Add(start_var + sum(lst_in_vars) == sum(lst_out_vars) + t_var)

# Ограничение: необходимо пройти по каждому мосту ровно 1 раз
for bridge in bridges:
  model.AddExactlyOne([E[bridge], E[bridge + "_r"]])

Будем использовать встроенный в OR-Tools набор алгоритмов - решатель/solver. Размерность задачи: 13 ограничений и 22 переменных. Задача небольшая, но мало кто захочет решать ее на бумаге. Перейдем к решению:

# Инициализация solver
solver = cp_model.CpSolver()

# # Статистика по модели
# print(model.ModelStats())

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

# Проверяем статус
if status == cp_model.OPTIMAL:
  print('Найден Эйлеров путь!')
elif status == cp_model.INFEASIBLE:
  print('Эйлеров путь не существует!')

Приведу немного теории от Эйлера.

Первая теорема Эйлера, 1736. Граф с двумя или более вершинами имеет эйлеров цикл тогда и только тогда, когда в каждую вершину входит чётное число рёбер.

Вторая теорема Эйлера, 1736. Граф с двумя или более вершинами имеет единственный эйлеров путь тогда и только тогда, когда ровно в две вершины входит нечётное число рёбер.

Следствие. Граф с двумя или более вершинами имеет эйлеров путь тогда и только тогда, когда либо в каждую вершину входит чётное число рёбер, либо ровно в две вершины входит нечётное число рёбер.

В случае мостов Кёнигсберга имеем четыре вершины с нечетным числом ребер, результат модели - Эйлеров путь не существует! Отсутствие решения это тоже решение.

Корректировка постановки задачи

После получения результата напрашивается вопрос, а когда Эйлеров путь будет существовать? Ответ можно получить из следствия теорем Эйлера, или, в нашем случае, скорректировать постановку задачи на: найти максимальное кол-во мостов, когда существует Эйлеров путь.

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

$b_{ijm} + b_{jim} \le 1, \quad \forall m \in M.$

Хотим найти максимальное кол-во мостов, которые позволят сформировать Эйлеров путь. Критерий оптимизации зададим в виде следующей целевой функции:

$\max \sum_{i,j,m \in E} b_{ijm}.$

Программная реализация изменений/дополнений модели:

# Ограничение: можно пройти по мосту не более одного раза
# ВНИМАНИЕ! заменяем ограничение: необходимо пройти по каждому мосту ровно 1 раз на следующее
for bridge in bridges:
  model.AddAtMostOne([E[bridge], E[bridge + "_r"]])

# Целевая функция максимаизации кол-ва мостов в пути
model.Maximize(sum(E.values()))

Новая модель допускает путь, в котором не будет ни одного ребра. Если прогулку на месте считать Эйлеровым путем, то решение новой задачи всегда будет существовать - `Найден Эйлеров путь!`.

Посмотрим, какой мост/мосты являются камнем преткновения ... Уже исходя из теоремы Эйлера, видно, что любой мост (один), добавленный или убавленный, сделает задачу решаемой. В рамках моего запуска получилось следующее решение:

Мосты: medoviy_r -> kuznechniy_r -> derevyanniy -> visokiy_r -> rabochiy_r -> zeleniy
Берега: Lomse -> Kneiphof -> Altstadt -> Lomse -> Vorstadt -> Kneiphof -> Vorstadt

Эйлеров пути из максимального кол-ва мостов

Решение задачи с помощью целочисленного программирования будет неустойчивым, т.е. в зависимости от запуска может быть выдан новый путь. Устранить эту проблему можно за счет добавления разных весов в целевую функцию за прохождение того или иного моста. Вес можно обосновать, например, близостью ресторанов, пунктов по продаже еды или живописностью мостов.

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

Ссылки

Историческая справка и теоремы взяты из википедии;
Версия статьи в Jupyter notebook.

Схожий материал:

Модель назначения машин такси на заявки;
Модель планирования расписаний сотрудников;
Вводная статья по генерации столбцов.