Это база: Зачем нужна математика в повседневной жизни - Йэн Стюарт
Шрифт:
Интервал:
Закладка:
Орграф обмена почками, использовавшийся в июле 2015 года, и оптимальное решение (показано сплошными черными линиями). Белые точки – доноры и реципиенты, не имеющие пары, серые точки – доноры-альтруисты, черные точки – доноры и реципиенты, получившие пару[5]
В приведенных выше орграфах отдельные циклы и цепочки показаны при помощи небольшого числа вершин и стрелок. В реальности пар много, доноров-альтруистов заметно меньше, а вот стрелок просто громадное количество. Это происходит потому, что орграф должен иметь стрелку между двумя любыми вершинами X и Y, где донор X совместим с реципиентом Y. Один и тот же донор может быть совместим со множеством реципиентов. Например, в октябре 2017 года было зарегистрировано 226 неальтруистических пар и 9 доноров-альтруистов, между которыми было проведено в совокупности 5964 стрелки. Рисунок иллюстрирует сложность структуры на другую дату. Математическая задача состоит в том, чтобы найти в этом орграфе не просто один обмен, а наилучшее возможное подмножество обменов.
* * *
Чтобы решить эту задачу математически, необходимо точно определить понятие «наилучший возможный». Это не просто множество обменов, при котором задействовано максимальное число людей. Есть и другие соображения, такие как стоимость и вероятный процент успеха. Здесь в дело вступают медицинская консультация и опыт. Служба переливания крови и трансплантации Министерства здравоохранения Великобритании (NHSBT) разработала стандартную систему количественной оценки пользы от каждой пересадки органа. Во внимание принимаются такие факторы, как срок ожидания пациента в очереди, уровни несовместимости по типу тканей и разница в возрасте между донором и реципиентом. При помощи статистического анализа эти факторы собираются в единую числовую оценку – действительное число, которое называют весом. Вес вычисляется для каждой стрелки на орграфе, то есть для каждой потенциальной пересадки.
Имеется одно очевидное условие: одна и та же вершина графа не может быть задействована в двух цепочках, поскольку невозможно отдать одну и ту же почку двум людям. Математически это равноценно утверждению, что циклы, составляющие множество, не пересекаются. Остальные условия тоньше. Некоторые циклы длины 3 имеют дополнительную полезную черту: лишнюю стрелку в обратном направлении между двумя вершинами. На рисунке показан случай, когда, помимо стрелок предыдущего цикла длины 3, в цикле имеется еще одна от пары Берил к паре Амелии. Это означает, что Берил совместима не только с Кэрол, но и с Амелией. Если где-то на поздней стадии Карл вдруг выпадет из договоренности по обмену, то Кэрол тоже можно исключить; останется цикл длины 2, в котором Альберт передает почку Бернарду, а Берил – Амелии, и этот обмен по-прежнему может быть реализован. Математически эти три вершины образуют цикл длины 3, и дополнительно две из его вершин образуют цикл длины 2. Подобная дополнительная стрелка называется обратной дугой. Любой цикл длины 3 с обратной дугой и циклом длины 2 называется эффективным циклом длины 2.
Согласно определению Консультативной группы по почкам при NHSBT, множество обменов почками является оптимальным, если оно:
(1) максимизирует число эффективных циклов длины 2;
(2) содержит как можно больше циклов, при выполнении условия (1);
(3) использует как можно меньше циклов длины 3, при выполнении условий (1) и (2);
(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 составляет 2381, а это число с 115 знаками. Число наборов из циклов длины 3 имеет 1149 знаков. А мы еще даже не проверили, какие из множеств не имеют пересечений.
Вряд ли стоит пояснять, что на самом деле эту задачу решают не так. Но из приведенных данных понятно, что для этого необходимо придумать какие-то достаточно эффективные методы. Я лишь набросаю некоторые из задействованных в решении идей. Вообще, все это можно рассматривать как разновидность пресловутой задачи коммивояжера: как задачу комбинаторной оптимизации с другими, конечно, ограничениями, но аналогичными рассуждениями. Принципиально важно, сколько времени требуется на поиск оптимального решения. Эту стратегию можно исследовать с точки зрения вычислительной сложности, как в главе 3.
Если в схеме участвуют только циклы длины 2, то оптимальное множество обменов может быть вычислено за полиномиальное время, класс сложности P, с использованием стандартных методов построения паросочетаний с максимальным весом в графе. Если присутствуют и циклы длины 3, даже без доноров-альтруистов, задача оптимизации становится NP-трудной. Тем не менее Мэнлав с
