Это база: Зачем нужна математика в повседневной жизни

(4) максимизирует число обратных дуг, при выполнении условий (1)–(3);

(5) максимизирует суммарный вес всех циклов, при выполнении условий (1)–(4).

Эффективный цикл длины 2

Интуитивно понятно, что это определение отдает приоритет определенным моментам, а когда выполнено главное условие, в дело последовательно вступают остальные, с более низким приоритетом. Например, условие (1) гарантирует, что включение в схему трехсторонних обменов не уменьшит число двухсторонних обменов, которые могли бы быть сделаны. Такой подход обеспечивает, во-первых, простоту, а во-вторых – возможность продолжать с циклом длины 2, если кто-то вдруг выпадет из схемы. Условие (5) означает, что множество обменов должно быть как можно более эффективным и иметь максимальную вероятность успеха, но начинать думать об этом можно только после того, как приняты главные решения по пунктам (1)–(4).

Математическая задача состоит в том, чтобы найти оптимальное множество обменов, соответствующее данным критериям. Если немного подумать и прикинуть цифры, несложно понять, что проверить все возможные множества обменов нереально. Их попросту слишком много. Допустим, у нас имеется 250 вершин и 5000 ребер. В среднем с каждой вершиной связано 20 ребер, и для упрощения оценки будем считать, что 10 из них в эту вершину входят, а 10 – выходят. Предположим, мы хотим найти все возможные циклы длины 2. Выберем какую-нибудь вершину и пройдем вдоль 10 выходящих из нее стрелочек. Каждая стрелочка заканчивается у другой вершины, из которой тоже выходит 10 стрелочек. Мы получаем цикл длины 2, если конечная вершина после этого совпадет с начальной. Получаем 100 вариантов для проверки. Для нахождения цикла длины 3 необходимо проверить 100 × 10 = 1000 вариантов, а это означает 1100 проверок на каждую вершину. Вершин у нас 250, то есть проверять нужно 275 000 вариантов, если не учитывать упрощения, которые, конечно, могут снизить число проверок, но не изменят общего порядка величины.

Однако, даже если все получилось, вам на данный момент удалось всего лишь составить список возможных циклов длины 2 и 3. Обмен – это множество циклов, и число множеств растет экспоненциально с ростом числа циклов. В октябре 2017 года в орграфе были 381 цикл длины 2 и 3815 циклов длины 3. Число наборов из одних только циклов длины 2 составляет 2³⁸¹, а это число с 115 знаками. Число наборов из циклов длины 3 имеет 1149 знаков. А мы еще даже не проверили, какие из множеств не имеют пересечений.

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

Если в схеме участвуют только циклы длины 2, то оптимальное множество обменов может быть вычислено за полиномиальное время, класс сложности P, с использованием стандартных методов построения паросочетаний с максимальным весом в графе. Если присутствуют и циклы длины 3, даже без доноров-альтруистов, задача оптимизации становится NP-трудной. Тем не менее Мэнлав с коллегами разработал работоспособный алгоритм на базе линейного программирования, о котором мы говорили в главе 3. Их алгоритм UKLKSS перестраивает задачу оптимизации так, чтобы ее можно решить при помощи последовательности вычислений по методу линейного программирования. Результат каждого расчета подается на вход следующего как дополнительное ограничение. Так что условие (1) оптимизируется; при этом используется метод, известный как алгоритм Эдмондса в реализации Сильвио Микали и Виджая Вазирани. Алгоритм Эдмондса находит максимальное покрытие в графе за время, пропорциональное числу ребер, умноженному на квадратный корень из числа вершин. Покрытие связывает пары вершин на концах общего ребра, и задача в том, чтобы покрыть как можно большее число пар вершин без использования двух ребер, которые имеют одну общую вершину.

После того как оптимизация по условию (1) проведена, полученное решение оптимизируется по условию (2) с использованием алгоритма, известного как целочисленный программный решатель COIN-Cbc, части библиотеки алгоритмов проекта Вычислительной инфраструктуры для исследования операций, и т. д.