Алгоритмы для жизни: Простые способы принимать верные решения (Гриффитс, Кристиан) - страница 151

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

И более того, выясняется, что в задаче о коммивояжере минимальное остовное дерево – это одна из лучших стартовых точек, с которой начинаются поиски действительного решения. Этот подход позволяет решить даже самую сложную задачу о коммивояжере, какую только можно себе представить (найти кратчайший маршрут, который пройдет через все города Земли), и решить ее в пределах 0,05 % от (неизвестного) оптимального решения.

Хотя большинство из нас не сталкивались с формальной алгоритмической версией смягчения ограничений, ее основная идея знакома каждому, кто много размышлял над жизненными вопросами. «Что бы вы сделали, если бы не боялись?» – гласит мантра, которую вы не раз могли видеть в кабинете школьного психолога или на семинарах по мотивации. «Что бы вы сделали, если бы знали, что не потерпите неудачу?» Аналогичным образом, когда мы касаемся вопросов профессии и карьеры, мы интересуемся, «что вы сделаете, если выиграете в лотерею?» или, если зайти с другой стороны, «что бы вы делали, если бы все работы оплачивались одинаково?». Смысл этих мысленных упражнений точно такой же, как и в смягчении ограничений: сделать неразрешимое легко решаемым, добиться успеха в идеализированном мире, чтобы потом перенести результат в мир реальный. Если вы не можете решить стоящую перед вами проблему, попробуйте решить ее упрощенную версию и посмотрите, даст ли вам это решение отправную точку, послужит ли маяком для работы с полномасштабной проблемой. Возможно, что да.