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

.

•

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

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

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

Жадные алгоритмы

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

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

Карту, «зашитую» в спутниковый навигатор, можно рассматривать как набор перекрестков, соединенных между собой протяженностью дорог. Проблема, с которой сталкиваются спутниковые навигаторы, пытаясь найти кратчайший путь между двумя точками через лабиринт дорог и перекрестков, выглядит столь же сложной, как и задача коммивояжера. Действительно, с ростом количества дорог и перекрестков число возможных маршрутов растет астрономически быстро. Достаточно горстки дорог и кучки развязок, чтобы довести количество возможных маршрутов до триллионов. Если бы единственным способом найти решение был подсчет всех возможных маршрутов и сравнение общего пройденного расстояния для каждого из них, то это была бы проблема NP-класса. К счастью для всех, кто использует спутниковую навигацию, для этого есть эффективный метод – алгоритм Дейкстры, который находит кратчайшие маршруты в заданных условиях за полиномиальное время