Метод 2 – это подход, знакомый многим любителям откладывать на потом. В соответствии с ним нужно оставлять сложные задачи под самый конец, а вначале делать только самое простое. Его преимущество в том, что он приносит множество небольших, но быстрых побед. Его часто называют жадным алгоритмом, но этот термин необязательно подразумевает пренебрежение какими-либо делами. Он просто подчеркивает, что алгоритм пытается достичь максимального результата за счет минимума усилий.
Удачное применение жадного алгоритма – найти самую быструю дорогу из одной точки в другую, например, между двумя городами. Мы спрашиваем себя в каждом пункте: «До какого города здесь ближе всего?» Это хороший способ принимать решения, хотя он может помешать вам увидеть оптимальные пути на ранних этапах путешествия. Мы уже встречали разновидность такого подхода в главе 4, хотя Иоаннис просто хотел выбраться из лабиринта и не задумывался, сколько времени у него это займет.
Об алгоритмах поиска кратчайшего пути написано много, и здесь есть несколько соперничающих друг с другом подходов. Один из самых известных называется алгоритмом Дейкстры. Он был создан в 1959 году голландским ученым-компьютерщиком Эдсгером В. Дейкстрой. В более общем виде этот класс алгоритмов известен как алгоритмы поиска по графу.
Другое применение жадных алгоритмов, которое стоит отметить, – это поиск потенциальных совпадений в массиве текста, часто с целью заменить совпавшие символы другими. Например, в тексте есть словосочетание «Джесса Джессика», и мы хотим унифицировать разные варианты написания этого имени. Команда «Искать сочетание «Джесс»», после которой стоит набор других букв, оканчивающийся на «а», даст нам все встречающиеся формы написания этого имени (Джесса Джессика), а не отдельные имена («Джесса», «Джессика»). Поисковик совпадений остановится на последней «а», а не на первой. Иногда это полезно, хоть в данном случае у нас другая цель поиска.
Представьте, что вы едете по незнакомой дороге и видите знак, который показывает, сколько километров до трех окрестных городов. Вы можете поддаться искушению и поехать в ближайший из них.
Нежадный алгоритм сложнее и часто приносит лучшие результаты. Можно увидеть его аналог в военных действиях, где быстрый успех, например защита столицы, приносится в жертву ради более важной победы. Вспомните, как русская армия обошлась с армией Наполеона в 1812 году.
Нежадный алгоритм может быть охарактеризован как длинная, или затянувшаяся, игра. Wall Street Journal недавно опубликовал статью о чемпионах по скрабблу из Нигерии. Их победа была обусловлена не обширным словарным запасом, а интуитивной практикой выбора более коротких слов. Вместо того чтобы подбирать семи- и восьмибуквенные слова, которые приносят больше очков, нигерийские игроки обнаружили, что игра четырех- и пятибуквенными словами приводит к улучшению стратегии в долгосрочной перспективе. Они сохраняли самые сочетаемые буквы для будущих раундов, когда им выпадали не лучшие варианты из мешка. Вот отрывок из статьи, рисующий преимущества такого подхода:
«Британцы лидируют со словом «утверждение», которое дало им 86 очков, но в следующие пять раундов им удавалось выбирать слова, которые приносили меньше 30 очков. После слова «анкета» (93) мистер Джигере вырвался вперед. В финале счет был 449 против 432. Члены команды-победительницы подняли своего чемпиона на руки и понесли по комнате под популярную нигерийскую песню «Мы победили».
Метод 3 устраняет один из недостатков метода 2, фокусируясь на задачах, которые действительно важны. Мы составляем список задач, событий или чего-либо еще и располагаем их по приоритету. Заметьте, что «приоритетность» бывает и функцией «времени завершения», поэтому можно сказать, что метод 2 также располагает задачи в соответствии с их приоритетом. Возьмем, к примеру, принтер. Если в очереди на печать стоит 10 документов по 50 страниц каждый, а за ними идет один одностраничный документ, то, возможно, для принтера имеет смысл поставить последнюю задачу в приоритет, а не заставлять ее ждать до самого конца печати. Разделение двух методов показывает, что приоритетность иногда базируется на других свойствах, а не только на времени выполнения.
Получая новое задание, мы можем поместить его не в конец списка, а куда-нибудь в середину – в зависимости от приоритетности. Включение нового пункта в середину списка приоритетных задач порой приводит к увеличению времени, пока вы стираете старые задачи, освобождая место под новые. В главе 12 мы поговорим о том, как компьютер выбирает способ хранения такого списка (который часто называют очередью с приоритетом), чтобы такие вставки совершались достаточно быстро. Часто в повседневной жизни этот алгоритм наиболее эффективен.
Вот как все три метода выглядят на графике:
При условии, что задачи не зависят друг от друга (то есть очередность выполнения более ранних заданий не связана с временем выполнения последующих задач), все три метода Кви займут одинаковое время.
[35] Как было упомянуто в главе 1, мы сравниваем основные операции во всех трех методах, то есть оцениваем, сколько времени Кви тратит на работу над задачами. Если бы мы вместо этого рассматривали, скажем, время, которое уходит у Кви на составление и ведение ее списка задач, то мы бы сказали, что метод 1 занимает постоянное время, то есть 0, а метод 2 и метод 3 занимают в худшем случае логарифмический объем времени. Для чего концентрироваться на одном наборе опций и приносить в жертву другой? Возможно, потому первый набор больше способствует достижению итоговой цели по сравнению со вторым, поскольку составление и ведение списка заданий – не такое уж сложное дело.
[36] Больше об этом будет рассказано в главах 10 и 12.
Недостаточно смотреть на относительные величины; когда речь идет о результате задания, все становится существенным. Это относится и к алгоритмам, исполняемым за постоянное время. Представьте работника парковки, который хочет впихнуть как можно больше машин в ряд, чтобы эффективнее использовать пространство. Все ваши алгоритмы по выезду с парковки могут быть таковыми, но уровень сервиса разительно отличается. Например, если не оставлять свободного проезда, то парковщику придется в худшем случае убрать восемь других машин, чтобы добраться до нужного авто. Если оставлять проезд свободным все время, то придется убирать максимум три машины. Введение временных ограничений на то, когда можно оставлять или забирать машины, с правилом «без привилегий на въезд и выезд» позволит вообще не убирать другие машины при возвращении авто клиенту.
