В офисе компании менеджер по логистике может попытаться распределить адреса между несколькими водителями, одновременно планируя их оптимальные маршруты. Сопутствующая задача маршрутизации транспортных средств даже более сложна, чем проблема коммивояжера. Эти две задачи возникают повсеместно – от планирования городских автобусных маршрутов, сбора почты из почтовых ящиков и снятия предметов со складских полок до сверления отверстий в печатных платах, изготовления микросхем и подключения компьютеров к сети.
Единственное достоинство всех этих проблем заключается в том, что хорошие решения для некоторых таких задач мы можем распознать сразу, как только увидим. Если при формулировке проблемы ввести определенное условие – например, указать, что общая протяженность маршрута доставки не должна превышать 1000 миль, то адекватность предложенного решения мы сможем проверить сразу и легко, даже если найти такой маршрут очень трудно. Подобная задача так и называется – «задача принятия решения»; в нашем случае это проблема коммивояжера с задачей принятия решения, и она требует ответа «да» или «нет». Это один из типов проблем группы NP, для которого найти решение сложно, но проверить его легко.
Несмотря на отсутствие общего решения проблемы, для некоторых ее частных случаев (определенного множеств локаций и направлений) точные решения найти можно, хотя это и достаточно сложно. Билл Кук, профессор комбинаторики и оптимизации в Университете Ватерлоо в Онтарио, потратил почти 250 лет компьютерного времени на суперкомпьютере с параллельной архитектурой, вычисляя кратчайший маршрут между всеми пабами Соединенного Королевства. Этот мегазагул предусматривает посещение 49 687 заведений и имеет протяженность всего 40 тысяч миль – в среднем на один паб приходится 0,8 мили. Задолго до того, как Кук начал свои расчеты, Брюс Мастерс из Бедфордшира в Англии решал ту же проблему своим путем – эмпирическим. Ему принадлежит мировой рекорд Гиннесса (самая подходящая книга для такого рекорда) по посещению пабов. К 2014 году 69-летний рекордсмен выпивал в 46 495 различных заведениях. Начиная с 1960 года, по оценкам Брюса, он проехал и прошел более миллиона миль, чтобы посетить все пабы Великобритании – в 25 с лишним раз больше, чем самый эффективный маршрут Билла Кука. Если вы планируете отправиться в подобную одиссею или даже просто собираетесь прошвырнуться по местным пабам, вам, вероятно, стоит для начала свериться с алгоритмом Кука [155].
•
Подавляющее большинство математиков считают, что P и NP – это принципиально разные классы проблем и что у нас никогда не будет быстрых алгоритмов для коммивояжеров или маршрутизации транспортных средств. Возможно, это к лучшему. Задача принятия решения с бинарным вариантом ответа для проблемы коммивояжера – канонический пример подгруппы задач, известной как NP-полные. Существует мощная теорема [156], утверждающая, что, если бы существовал практический алгоритм, способный решить одну NP-полную задачу, его можно было бы преобразовать для решения любой другой NP-задачи. Если эта теорема верна, она доказывала бы, что P равно NP – что P– и NP-задачи фактически являются одним и тем же классом задач. Поскольку почти вся криптография в интернете полагается на сложность решения определенных NP задач, доказательство того, что P равно NP, может быть губительным для онлайн-безопасности.
С другой стороны, тогда мы могли бы разработать быстрые алгоритмы для решения всевозможных логистических задач. Фабрики могли бы организовать производственный процесс с максимальной эффективностью, а службы доставки находили бы самые эффективные маршруты транспортировки, что потенциально снижало бы цену товара – даже если его больше нельзя было бы безопасно заказать онлайн! В научной сфере доказательство равенства P и NP может обеспечить эффективные методы машинного распознавания образов, генетического секвенирования и даже прогнозирования стихийных бедствий.
По иронии судьбы от равенства P и NP больше всего может выиграть наука, а вот сами ученые могут оказаться главными проигравшими. Некоторыми потрясающими научными открытиями человечество обязано прежде всего творческому мышлению высококвалифицированных и глубоко преданных своему делу людей: дарвиновская теория эволюции путем естественного отбора, доказательство Последней теоремы Ферма Эндрю Уайлсом, теория общей относительности Эйнштейна, ньютоновские уравнения движения. Если бы P равнялся NP, то компьютеры сумели бы найти формальные доказательства любой доказуемой математической теоремы – и многие из величайших интеллектуальных достижений человечества могли бы быть воспроизведены и вытеснены работой робота. Масса математиков остались бы без работы. По сути своей, проблема P vs NP – это очень непростая попытка выяснить, можно ли автоматизировать человеческое творчество.
Жадные алгоритмы
Проблемы оптимизации – задача коммивояжера, например, – так сложны потому, что мы пытаемся найти лучшее решение из немыслимо большого набора возможностей. Иногда, однако, мы должны быть готовы принять быстрое и хорошее решение, а не идеальное, но медленное. Может, мне, отправляясь на работу, не стоит мучительно оптимизировать вещи в сумке, чтобы они занимали как можно меньше места, а просто надо найти способ впихнуть туда все нужное. Если дело в этом, мы можем начать искать кратчайшие пути решения проблем. Мы можем использовать эвристические алгоритмы (упрощения, основанные на здравом смысле, или эмпирические правила), которые призваны приблизить нас к оптимальному решению для широкого круга типологически близких задач.
Одно из семейств таких алгоритмов называется жадными алгоритмами. Эти краткосрочные процедуры нацелены на поиск лучшего локального выбора в попытке найти глобально оптимальные решения. Несмотря на то, что они работают быстро и эффективно, они не гарантируют получение оптимального или даже хорошего решения. Представьте, что вы впервые оказались в какой-то местности и хотите подняться на самый высокий холм, чтобы осмотреться. Жадный алгоритм подъема на вершину сводится к тому, чтобы сначала найти самый крутой уклон по отношению к вашей текущей позиции, а затем сделать шаг в этом направлении. На каждом шаге эта процедура повторяется до тех пор, пока вы не окажетесь в точке, по всем направлениям от которой будут лишь скаты. Это означает, что вы достигли вершины холма – но не обязательно самого высокого холма вокруг. Жадный алгоритм не гарантирует, что вы подниметесь на самую высокую вершину, с которой открывается наилучший вид. Возможно, что маршрут к вершине небольшого холма, на который вы только что взобрались, просто начинался круче, чем тот, который привел бы вас к вершине местного горного хребта, а выбор ошибочного маршрута был продиктован вашей эвристической близорукостью. Жадные алгоритмы могут найти решения, но не всегда гарантированно лучшие. Однако для проблем определенного типа жадные алгоритмы оптимальны.
