Кит Йейтс - Математика жизни и смерти. 7 математических принципов, формирующих нашу жизнь

Несмотря на отсутствие общего решения проблемы, для некоторых ее частных случаев (определенного множеств локаций и направлений) точные решения найти можно, хотя это и достаточно сложно. Билл Кук, профессор комбинаторики и оптимизации в Университете Ватерлоо в Онтарио, потратил почти 250 лет компьютерного времени на суперкомпьютере с параллельной архитектурой, вычисляя кратчайший маршрут между всеми пабами Соединенного Королевства. Этот мегазагул предусматривает посещение 49 687 заведений и имеет протяженность всего 40 тысяч миль – в среднем на один паб приходится 0,8 мили. Задолго до того, как Кук начал свои расчеты, Брюс Мастерс из Бедфордшира в Англии решал ту же проблему своим путем – эмпирическим. Ему принадлежит мировой рекорд Гиннесса (самая подходящая книга для такого рекорда) по посещению пабов. К 2014 году 69-летний рекордсмен выпивал в 46 495 различных заведениях. Начиная с 1960 года, по оценкам Брюса, он проехал и прошел более миллиона миль, чтобы посетить все пабы Великобритании – в 25 с лишним раз больше, чем самый эффективный маршрут Билла Кука. Если вы планируете отправиться в подобную одиссею или даже просто собираетесь прошвырнуться по местным пабам, вам, вероятно, стоит для начала свериться с алгоритмом Кука [155] Cook, W. (2012). In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton University Press. .

Подавляющее большинство математиков считают, что P и NP – это принципиально разные классы проблем и что у нас никогда не будет быстрых алгоритмов для коммивояжеров или маршрутизации транспортных средств. Возможно, это к лучшему. Задача принятия решения с бинарным вариантом ответа для проблемы коммивояжера – канонический пример подгруппы задач, известной как NP-полные. Существует мощная теорема [156] Мощными называются теоремы, применимые в большом количестве разных систем (этот полуофициальный термин, как правило, применяется в отношении абстрактных алгебраических теорем). – Прим. пер. , утверждающая, что, если бы существовал практический алгоритм, способный решить одну NP-полную задачу, его можно было бы преобразовать для решения любой другой NP-задачи. Если эта теорема верна, она доказывала бы, что P равно NP – что P– и NP-задачи фактически являются одним и тем же классом задач. Поскольку почти вся криптография в интернете полагается на сложность решения определенных NP задач, доказательство того, что P равно NP, может быть губительным для онлайн-безопасности.

С другой стороны, тогда мы могли бы разработать быстрые алгоритмы для решения всевозможных логистических задач. Фабрики могли бы организовать производственный процесс с максимальной эффективностью, а службы доставки находили бы самые эффективные маршруты транспортировки, что потенциально снижало бы цену товара – даже если его больше нельзя было бы безопасно заказать онлайн! В научной сфере доказательство равенства P и NP может обеспечить эффективные методы машинного распознавания образов, генетического секвенирования и даже прогнозирования стихийных бедствий.

По иронии судьбы от равенства P и NP больше всего может выиграть наука, а вот сами ученые могут оказаться главными проигравшими. Некоторыми потрясающими научными открытиями человечество обязано прежде всего творческому мышлению высококвалифицированных и глубоко преданных своему делу людей: дарвиновская теория эволюции путем естественного отбора, доказательство Последней теоремы Ферма Эндрю Уайлсом, теория общей относительности Эйнштейна, ньютоновские уравнения движения. Если бы P равнялся NP, то компьютеры сумели бы найти формальные доказательства любой доказуемой математической теоремы – и многие из величайших интеллектуальных достижений человечества могли бы быть воспроизведены и вытеснены работой робота. Масса математиков остались бы без работы. По сути своей, проблема P vs NP – это очень непростая попытка выяснить, можно ли автоматизировать человеческое творчество.

Проблемы оптимизации – задача коммивояжера, например, – так сложны потому, что мы пытаемся найти лучшее решение из немыслимо большого набора возможностей. Иногда, однако, мы должны быть готовы принять быстрое и хорошее решение, а не идеальное, но медленное. Может, мне, отправляясь на работу, не стоит мучительно оптимизировать вещи в сумке, чтобы они занимали как можно меньше места, а просто надо найти способ впихнуть туда все нужное. Если дело в этом, мы можем начать искать кратчайшие пути решения проблем. Мы можем использовать эвристические алгоритмы (упрощения, основанные на здравом смысле, или эмпирические правила), которые призваны приблизить нас к оптимальному решению для широкого круга типологически близких задач.

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

Карту, «зашитую» в спутниковый навигатор, можно рассматривать как набор перекрестков, соединенных между собой протяженностью дорог. Проблема, с которой сталкиваются спутниковые навигаторы, пытаясь найти кратчайший путь между двумя точками через лабиринт дорог и перекрестков, выглядит столь же сложной, как и задача коммивояжера. Действительно, с ростом количества дорог и перекрестков число возможных маршрутов растет астрономически быстро. Достаточно горстки дорог и кучки развязок, чтобы довести количество возможных маршрутов до триллионов. Если бы единственным способом найти решение был подсчет всех возможных маршрутов и сравнение общего пройденного расстояния для каждого из них, то это была бы проблема NP-класса. К счастью для всех, кто использует спутниковую навигацию, для этого есть эффективный метод – алгоритм Дейкстры, который находит кратчайшие маршруты в заданных условиях за полиномиальное время [157] Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1 (1), 269–71. .