Алгоритмы неформально. Инструкция для начинающих питонистов - [24]

Как и в примере с ловлей мяча, мы видим, что такие алгоритмы, как градиентный подъем, естественны для человеческой жизни и принятия решений. Они естественны для нас даже в том случае, если мы никогда не посещали уроки математики и не написали ни единой строки кода. Инструменты, описанные в этой главе, всего лишь формализуют и уточняют уже имеющиеся у нас интуитивные представления.

Когда не следует применять алгоритм

Часто изучение нового алгоритма наполняет нас ощущением силы. Нам начинает казаться, что в любой ситуации, требующей максимизации или минимизации, следует немедленно применить градиентный подъем или спуск и довериться полученному результату. Однако иногда знать алгоритм — не главное. Еще важнее знать, когда не следует его применять, когда это неуместно или недостаточно для текущей задачи либо когда есть другое, более эффективное решение.

Когда использовать градиентный подъем (и спуск), а когда не стоит этого делать? Градиентный подъем хорошо работает в том случае, если у вас с самого начала имеются правильные ингредиенты:

• математическая функция для максимизации;

• информация о текущей точке;

• однозначный критерий максимизации функции;

• возможность изменять текущую точку.

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

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

Можно пойти еще дальше: у вас могут быть все ингредиенты, необходимые для градиентного подъема (или любого другого алгоритма), но при этом вы все равно будете воздерживаться от его применения по более глубоким философским причинам. Допустим, вы точно определяете функцию ставки налога/поступлений и вас назначили премьер-министром с полным контролем над ставкой налого­обложения в вашей стране. Прежде чем применять градиентный подъем и искать пик, максимизирующий поступления, стоит спросить себя, является ли максимизация налоговых поступлений правильной целью, с которой следует начинать. Возможно, вас в большей степени интересует личная свобода граждан, экономический рост, справедливость перераспределения или результаты опросов общественного мнения, чем поступления в бюджет. Даже если вы решили, что хотите обеспечить максимальный приток средств, неясно, приведет ли максимизация доходов в краткосрочной перспективе (например, за год) к максимизации поступлений за долгий срок.

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

Резюме

В этой главе представлены градиентный подъем и градиентный спуск — простые и мощные алгоритмы, используемые для нахождения максимумов и минимумов функций соответственно. Кроме того, рассматривалась серьезная потенциальная проблема локальных экстремумов и некоторые философские соображения относительно того, когда следует применять алгоритмы, а когда от них лучше воздержаться.

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

2 Здесь и далее речь об американской системе образования. — Примеч. ред.

4. Сортировка и поиск

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

Некоторые методы сортировки и поиска принадлежат к числу таких фундаментальных алгоритмов. Их стоит знать, поскольку они часто применяются и пользуются любовью поклонников алгоритмов (и садистов, проводящих собеседования для программистов). Реализация этих алгоритмов может быть простой и короткой, но некоторые теоретики постоянно стараются сделать так, чтобы они проводили сортировку и поиск с головокружительной скоростью. Вследствие этого в данной главе мы рассмотрим скорость выполнения алгоритмов и специальные обозначения, которые используются для сравнения эффективности алгоритмов.