В этом параграфе вы познакомитесь с одним из самых простых, но фундаментальных методов проектирования алгоритмов — полным перебором.
Ключевые вопросы параграфа
- Что такое алгоритм полного перебора и когда его стоит применять?
- Почему переборные алгоритмы считаются неэффективными?
- Как метод ветвей и границ помогает ускорить перебор?
Основные методы проектирования алгоритмов
За полвека программисты обнаружили, что многие алгоритмы основаны на схожих концептах, хотя и используются для решения разных проблем. Получается, основных методов проектирования алгоритмов относительно немного. Некоторые из них мы охватим в задачах, а пока расскажем о наиболее распространённых. Последующие примеры можно будет категоризировать по методологии проектирования.
Для демонстрации мы рассмотрим очень простую ситуацию, с которой может столкнуться едва ли не каждый обладатель беспроводного домашнего телефона.
Метод полного перебора
Алгоритм, использующий полный перебор (также этот метод называют «исчерпывающий поиск» или «метод грубой силы»), рассматривает все возможные варианты и находит определенное решение.
Если бы вы искали телефон по такому алгоритму, то игнорировали бы звонок и проверяли бы каждый квадратный сантиметр вашего дома. Вряд ли вы бы успели взять трубку, — иначе вашей удаче можно позавидовать, — но исчерпывающий поиск гарантирует, что рано или поздно вы найдете телефон, где бы он ни был.
BruteForceChange — это алгоритм «грубой силы». Наши задачи включают несколько дополнительных примеров таких алгоритмов. Они самые легкие с точки зрения проектирования, но слишком медленные для решения более серьёзных задач, нежели самых маленьких. Мы советуем или избегать алгоритмов «грубой силы» или находить решения, которые ускоряют их работу.
Метод ветвей и границ
Если рассмотреть варианты, предложенные алгоритмом «грубой силы», мы увидим, что многие из них можно опустить. Эта техника называется методом ветвей и границ.
Представьте, что вы прочёсываете первый этаж и слышите, как над вами звонит телефон. Значит, на первом этаже и в подвале можно больше не искать — и вы сэкономили себе время.
Хотя алгоритмы полного перебора и не подходят для построения эффективных алгоритмов, мы рекомендуем использовать их для стресс-тестирования — техники поиска ошибок в алгоритмах, подробнее о которой мы поговорим в параграфе 4.3.
Что дальше
Теперь вы знаете, как работает полный перебор и почему он не всегда подходит для сложных задач. Вы также познакомились с методом ветвей и границ — первым шагом к ускорению перебора.
Далее — жадные алгоритмы. Вы узнаете, когда можно принимать решения на каждом шаге, не заглядывая вперёд, и почему это иногда приводит к оптимальному результату, а иногда — нет.
А пока вы не ушли дальше — закрепите материал на практике:
- Отметьте, что урок прочитан, при помощи кнопки ниже.
- Пройдите мини-квиз, чтобы проверить, насколько хорошо вы усвоили тему.
- Перейдите к задачам этого параграфа и потренируйтесь.
- Перед этим — загляните в короткий гайд о том, как работает система проверки.
Хотите обсудить, задать вопрос или не понимаете, почему код не работает? Мы всё предусмотрели — вступайте в сообщество Хендбука! Там студенты помогают друг другу разобраться.
Ключевые выводы параграфа
- Полный перебор перебирает все возможные варианты и гарантирует нахождение решения, если оно существует. Такой подход прост, но становится неэффективным при росте объёма входных данных.
- Метод ветвей и границ помогает отсекать заведомо бесполезные варианты и ускорять перебор.
- Несмотря на неэффективность, переборные алгоритмы полезны для тестирования и понимания структуры задач.