Шаг 184.
Рекурсия на Python.
Множественная рекурсия III: перебор с возвратами (общие сведения)

    На этом шаге мы кратко опишем реализацию такого перебора.

    Перебор с возвратами (backtracking) - одна из самых важных парадигм разработки алгоритмов. Её можно считать "интеллектуальной" стратегией грубой силы (решением "в лоб"), выполняющей исчерпывающий поиск решений задач с заданными ограничениями и задач дискретной оптимизации. Подход может использоваться для решения огромного числа головоломок и задач, включая задачи о восьми ферзях, поиска пути в лабиринте, судоку, оптимизации рюкзака 0-1 и многие другие.

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

    На следующем шаге мы продолжим изучение этого вопроса.




Предыдущий шаг Содержание Следующий шаг