эффективным циклом длины 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-трудной. Тем не менее Мэнлав с коллегами разработал работоспособный алгоритм на базе линейного программирования, о котором мы говорили в главе 3. Их алгоритм UKLKSS перестраивает задачу оптимизации так, чтобы ее можно решить при помощи последовательности вычислений по методу линейного программирования. Результат каждого расчета подается на вход следующего как дополнительное ограничение. Так что условие (1) оптимизируется; при этом используется метод, известный как алгоритм Эдмондса в реализации Сильвио Микали и Виджая Вазирани. Алгоритм Эдмондса находит максимальное покрытие в графе за время, пропорциональное числу ребер, умноженному на квадратный корень из числа вершин. Покрытие связывает пары вершин на концах общего ребра, и задача в том, чтобы покрыть как можно большее число пар вершин без использования двух ребер, которые имеют одну общую вершину.
После того как оптимизация по условию (1) проведена, полученное решение оптимизируется по условию (2) с использованием алгоритма, известного как целочисленный программный решатель COIN-Cbc, части библиотеки алгоритмов проекта Вычислительной инфраструктуры для исследования операций, и т. д.
К концу 2017 года при помощи этих методов теории графов было найдено 1278 потенциальных вариантов пересадки, но реализовали только 760 из них, потому что на последних этапах оценки вылезают разные проблемы: выясняется, например, что типы тканей не так хорошо совместимы, как считалось ранее, или что доноры или реципиенты по состоянию здоровья не могут выдержать операции. Однако систематическое использование алгоритмов из теории графов для эффективной организации пересадки почек – серьезный шаг вперед по сравнению с прежними методами. Кроме того, это указывает нам путь к дальнейшим усовершенствованиям, поскольку сегодня мы можем хранить почки вне тела дольше, так что все операции в цепочке не обязательно проводить в один день. Теперь можно задуматься и о более длинных цепочках, а это ставит перед нами новые математические задачи.
Я не пытаюсь утверждать, что Эйлер умел предвидеть будущее. Он, конечно, не думал, что его остроумное решение глупой головоломки когда-нибудь пригодится в медицине. И уж точно он не мог предположить, что оно найдет применение в трансплантологии – ведь в те времена хирургия не слишком отличалась от ремесла мясников. Но я хочу отдать ему должное – даже в те далекие дни он видел, что эта головоломка намекает математикам на нечто более глубокое, и прямо говорил об этом. Взгляните на эпиграф к этой главе. Эйлер неоднократно упоминает «геометрию положения» в контексте данной задачи. Это понятие он обозначает на латыни как analysis situs и отдает Лейбницу честь изобретения термина и, косвенно, осознания того, что такой предмет может оказаться важен. Самого Эйлера, очевидно, заинтриговала идея геометрии, имеющей дело не с традиционными евклидовыми фигурами. Он не отвергает эту идею из-за ее неортодоксальности, совсем наоборот. Ему приятно внести свой вклад в развитие такой геометрии. Он развлекается.
Мечта Лейбница осуществилась в XX веке после весьма существенных достижений XIX века. Мы сегодня называем эту область математики топологией, и в главе 13 я покажу некоторые ее новые применения. Теория графов по-прежнему не теряет связи с топологией, но их развитие шло разными путями. Такие понятия, как вес ребра, имеют численный, а не топологический характер. Но идея о том, что графы можно использовать для моделирования сложных взаимодействующих систем и решения задач оптимизации, восходит к Эйлеру. Он занялся вопросами нового типа потому, что они захватили его воображение, и придумал собственные способы поиска ответов на них. Произошло это в Санкт-Петербурге, в России, куда он приехал по приглашению недавно созданной Академии наук почти три столетия назад. Всякий, кому пересаживают почку, будь то в Великобритании или в любой другой стране, где пользуются методами теории графов для более эффективного распределения органов, должен восхищаться тем, что сделал Эйлер.
5Будьте осторожны в киберпространстве
Никому еще не удалось обнаружить ни одну военную или имеющую отношение к войне задачу, которой служила бы теория чисел или теория относительности, и маловероятно, что кому-нибудь удастся обнаружить нечто подобное, на сколько бы лет мы ни заглядывали в будущее.
Пьер де Ферма знаменит своей Великой теоремой, которая гласит, что если n равно по крайней мере 3, то сумма двух n-х степеней целых чисел не может также быть n-й степенью целого числа. Эндрю Уайлс в конечном итоге нашел этому современное формальное доказательство в 1995 году, примерно 358 лет спустя после того, как Ферма высказал свою гипотезу{39}. По профессии Ферма был юристом, советником парламента в Тулузе, но большую часть времени посвящал математике. У него был друг по имени Френикль де Бесси, парижский математик, известный прежде всего полным каталогом 880 магических квадратов четвертого порядка. Они активно переписывались, и 18 октября 1640 года Ферма написал де Бесси (по-французски), что «каждое простое число делит… одну из степеней любой прогрессии за вычетом единицы, а показатель этой степени делит данное простое число за вычетом единицы».
Если перевести этот текст на алгебраический язык, то Ферма утверждал, что если p – простое число и a – произвольное число, то ap–1–1 делится на p (без остатка). Например, поскольку 17 – простое число, то, согласно его утверждению, все числа
116–1 216–1 316–1 … 1616–1 1816–1…
кратны 17. Очевидно, 1716–1 придется пропустить: это число никак не может быть кратно 17, поскольку оно на единицу меньше такого числа, а именно 1716. Ферма понимал, что такое дополнительное условие необходимо, но не упомянул этого в письме. Проверим такой случай: