Алгоритмы для жизни. Простые способы принимать верные решения - Том Гриффитс

Это пример известной математикам и программистам задачи по оптимизации с заданными ограничениями: как найти единственный лучший вариант с рядом переменных при определенных заданных правилах и системе ведения счета. По сути, это самая известная задача по оптимизации из всех. Если бы ее изучали в XIX веке, она наверняка получила бы название «задача адвоката прерий», а если бы с ней впервые столкнулись в XX веке, то ее окрестили бы задачей по перемещениям беспилотника. Но, так же как и задача о секретаре, она появилась в середине XХ века под названием «задача о коммивояжере».

Задача о планировании маршрута не привлекала внимание математического сообщества до 1930-х годов, но, когда это случилось, задача была отомщена. Математик Карл Менгер упоминал о задаче почтового служащего в 1930 году, отмечая, что не существует более простого из известных решений, кроме как испытывать каждую возможность по очереди. Хасслер Уитни из Принстона обозначил эту проблему в 1934 году, тогда она и засела плотно в уме его друга математика Меррила Флада (который, как вы помните из главы 1, причастен к распространению первого решения задачи о секретаре). Когда Флад переехал в Калифорнию в 40-е годы, он передал эту задачу своим коллегам в Институте Айн Рэнд. Каноническое название задачи впервые было упомянуто в газетной публикации в 1949 году благодаря математику Джулии Робинсон. По мере обсуждения задачи в математических кругах она постепенно приобрела печальную известность. Множество величайших умов были ею одержимы, но никто, казалось, даже не начал двигаться в верном направлении, решая ее.

В задаче о коммивояжере вопрос заключается не в том, может ли компьютер (или математик) найти кратчайший путь: теоретически можно просто составить список всех возможностей и оценить каждую из них. Скорее, сложность состоит в том, что по мере роста количества городов список возможных маршрутов стремительно растет. Маршрут – это всего лишь последовательность городов, поэтому метод перебора всех маршрутов и приводит нас к той вселяющей ужас формуле О(n!) факториального времени – вычислительному эквиваленту попытки отсортировать колоду карт в нужном порядке, подбрасывая их в воздух.

Вопрос: а есть ли надежда на лучшее решение?

Десятилетия работы помогли добиться некоторых результатов в укрощении задачи о коммивояжере. К примеру, Флад писал в 1956 году, спустя более 20 лет после первой встречи с этой задачей: «Представляется очень вероятным, что нужен абсолютно другой подход относительно уже испробованных для успешного прохождения этой головоломки. По сути, может не существовать общего способа ее решения, и результаты, демонстрирующие невозможность решения, тоже ценны». Спустя 10 лет общее настроение было еще более унылым. «Я предполагаю, – писал Джек Эдмондс, – что не существует правильного алгоритма для решения задачи о коммивояжере».

Эти слова оказались пророческими.

В середине 1960-х годов Эдмондс, сотрудник Национального института стандартов и технологии, и Алан Кобхэм из IBM сформулировали рабочее определение того, что делает задачу решаемой или наоборот. Они доказывали утверждение, ныне известное как гипотеза Кобхэма и Эдмондса: алгоритм считается эффективным, если его действие происходит в так называемом полиномиальном времени, а именно O(n2), O(n3) или, в сущности, n в любой степени. Задача, в свою очередь, считается решаемой, если мы знаем, как решить ее, используя эффективный алгоритм. Задача, которую мы не можем решить в полиномиальном времени, напротив, считается нерешаемой. И везде, кроме мельчайших масштабов, нерешаемые задачи не поддаются решению с помощью компьютеров, какими бы мощными они ни были[27].

Таким образом, измерить сложность задачи возможно. Но какие-то задачи просто… сложные.

И чем же заканчивается тогда история с задачей о коммивояжере? Довольно любопытно, что мы до сих пор в этом не уверены. В 1972 году профессор Университета Беркли Ричард Карп продемонстрировал, что задача о коммивояжере связана со спорно пограничным классом задач, которые еще не были определены как решаемые или нерешаемые. Но пока что эффективных решений этих задач найдено не было (что делает их, по сути, нерешаемыми), и большинство программистов считают, что решений не найти. Таким образом, результат, свидетельствующий о невозможности решения задачи о коммивояжере, о котором говорил Флад в 1950-е годы, оказался фатальным. Более того, многие другие задачи по оптимизации, касающиеся всевозможных вопросов от политической стратегии до здравоохранения и пожарной безопасности, аналогичным образом попадают в класс нерешаемых.

Но для программистов, которые продолжают искать ответ, такой вердикт – вовсе не конец истории. Наоборот, для многих это призыв к действию. Вы же не можете просто опустить руки, определив, что проблема не имеет решения. Как говорил эксперт в области планирования Ян Карел Ленстра, «если задача трудная, это не значит, что вы можете забыть о ней. Это означает, что она просто находится в другом статусе. Это серьезный враг, но вы все равно должны бороться». И здесь мы приходим к бесценному выводу относительно того, как лучше всего подходить к задачам, где оптимальные решения недоступны. Как расслабиться.

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

Одна из самых простых форм релаксации в компьютерной науке – это смягчение ограничений. Согласно этому методу исследователи убирают ряд ограничений из задачи и приступают к решению получившейся задачи. Затем, по мере достижения некоторых успехов, они пытаются снова добавить эти ограничения. То есть они временно делают задачу проще в решении, прежде чем вернуть ее к реальности.

Например, вы можете ослабить задачу о коммивояжере, если позволите ему посетить один и тот же город несколько раз и возвращаться бесплатно. Поиск кратчайшего маршрута в этих новых ослабленных условиях приводит к тому, что называется «минимальное остовное дерево». (Если хотите, можете принять минимальное остовное дерево за наименьшее количество километров дорог, соединяющих один город с другим. Кратчайший путь коммивояжера и минимальное остовное дерево для судебной схемы Линкольна показаны ниже.) Как оказалось, на решение этой ослабленной задачи компьютеру не требуется времени вовсе. И в то время как минимальное остовное дерево не обязательно ведет прямо к решению реальной задачи, оно тем не менее весьма полезно. С одной стороны, остовное дерево с его свободным механизмом возврата никогда не заменит реального решения, которое должно следовать всем правилам. Таким образом, мы можем принять ослабленную задачу – фантазию – за нижнюю границу реальности. Вычислив, что остовное дерево расстояний между определенными городами – это 100 миль, мы можем быть уверены, что расстояние, покрытое коммивояжером, не будет меньше этого значения. И если мы найдем, к примеру, маршрут расстоянием в 110 миль, он будет не более чем на 10 % длиннее оптимального решения. Таким образом, мы можем получить представление о том, насколько близко мы подошли к настоящему решению, даже не зная, какое оно.