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

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

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

Например, в поисках кратчайшего пути от дома до кинотеатра алгоритм Дейкстры выстраивает маршрут в обратном направлении – от кинотеатра. Если известно кратчайшее расстояние от дома до всех перекрестков, соединенных с кинотеатром одним отрезком дороги, то работа существенно упрощается. Мы можем просто рассчитать кратчайший путь до кинотеатра, добавляя к длине дорог, соединяющих кинотеатр с ближайшими к нему перекрестками, длину путей от дома до этих перекрестков. Конечно, в начале процесса расстояния от дома до ближайших к кинотеатру перекрестков неизвестны. Однако, использовав ту же процедуру снова, мы можем найти кратчайшие пути до этих предпоследних перекрестков, используя кратчайшие пути от дома до тех перекрестков, которые с ними соединяются. Применяя эту логику рекурсивно, перекресток за перекрестком, мы возвращаемся дому, откуда и начинаем путешествие. Поиск кратчайшего маршрута через дорожную сеть, который просто требует от нас неоднократно делать правильный локальный выбор, – жадный алгоритм. Чтобы реконструировать маршрут, мы просто отслеживаем развязки, через которые нам пришлось пройти, чтобы найти это кратчайшее расстояние. Когда вы ищете через Google Maps наилучший маршрут до кинотеатра, в недрах программы обработку данных начинает, скорее всего, какая-то из вариаций алгоритма Дейкстры.

Когда вы, добравшись до кинотеатра, намереваетесь оплатить парковку, в билетном автомате вполне может не оказаться сдачи. Если у вас достаточно монет, то вы, скорее всего, захотите, как можно быстрее набрать точную сумму. Жадный алгоритм, который в такой ситуации многие используют интуитивно, состоит в том, чтобы вставлять в прорезь монету наивысшего достоинства, но меньше оставшейся к оплате суммы.

Большинство денежных систем – в Великобритании, Австралии, Новой Зеландии, ЮАР, Европе и т. д. – имеют структуру 1–2–5, при этом достоинства монет или банкнот в этой структуре увеличиваются кратно деноминации. В Великобритании, например, в обращении 1-, 2– и 5-пенсовые монеты. Далее следуют монеты достоинством 10, 20 и 50 пенсов, затем монеты в 1 фунт и 2 фунта стерлингов, за которыми следуют 5-, 10-, 20– и, наконец, 50-фунтовые банкноты. Таким образом, чтобы в рамках этой системы набрать 58 пенсов мелочью с помощью жадного алгоритма, нужно взять 50-пенсовик, оставив 8 пенсов до требуемой суммы; 20 и 10 пенсов уже превысят нужную величину, поэтому добавляем 5 пенсов, затем 2 пенса и наконец пенни. Получается, что во всех валютных системах такого типа, включая американскую, исполнение описанного выше жадного алгоритма позволяет набрать нужную сумму из наименьшего количества монет.

Но вовсе не обязательно, что этот алгоритм будет работать в любой валютной системе. Если бы вдруг существовала еще и 4-пенсовая монета, то последние 8 пенсов из 58 можно было бы набрать всего двумя 4-пенсовыми монетами вместо монет по 5, 2 и 1 пенсу. Любая валюта, для которой каждая монета или банкнота по крайней мере в два раза дороже, чем предыдущая по номиналу, удовлетворяет условиям жадного алгоритма. Это объясняет преобладание структуры «1–2–5» – соотношения 2 или 2,5 между номиналами гарантируют, что жадный алгоритм будет работать, а простая десятеричная система сохраняется. Поскольку мелочь требуется практически повсеместно, почти все валюты мира организованы таким образом, чтобы удовлетворять условиям жадного алгоритма – за исключением Таджикистана, где в обращении ходят монеты достоинством в 5, 10, 20, 25 и 50 дирамов. 40 дирамов проще набрать двумя монетами по 20, чем монетами по 25, 10 и 5 дирамов, что предлагает жадный алгоритм.

Кстати, о жадности: вы когда-нибудь пробовали заказать 43 макнаггетса в «Макдоналдсе»? Как ни странно, эти жареные во фритюре панированные кусочки курицы породили интересную математику. В Великобритании макнаггетсы первоначально подавали в коробках по 6, 9 или 20 штук. Обедая с сыном в «Макдоналдсе», математик Анри Пиччотто решил подсчитать, сколько наггетсов он не сможет заказать одномоментно, используя комбинации из трех коробок. Ответом стал числовой ряд 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37 и 43. Все остальные «наборы» наггетсов составить было можно; эти числа с того дня стали известны как числа Макнаггетса. Самое большое число, которое нельзя получить, комбинируя с кратными величинами заданного набора чисел, называется числом Фробениуса. Числом Фробениуса для куриных макнаггетсов, таким образом, было 43. К сожалению, когда «Макдоналдс» добавил в ассортимент упаковки по 4 наггетса, число Фробениуса упало до 11. Забавно, что даже с добавлением этой новой коробки, жадный алгоритм не позволит набрать 43 наггетса (две порции по 20 дадут сразу 40, а порции из 3 наггетсов нет), так что получить на заказ 43 наггетса в «Макавто» сегодня все еще непросто – хотя набрать это количество и возможно.