Прогулка по мостам Кёнигсберга с 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.

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

— Модель назначения машин такси на заявки;

— Модель планирования расписаний сотрудников;

— Вводная статья по генерации столбцов.

ссылка на оригинал статьи https://habr.com/ru/articles/745300/