Алгоритмы с нуля
Рекурсия и backtracking: постройте решатель с pruning
Читать про pruning — не то же самое, что видеть, как он сжимает перебор. Постройте один решатель на backtracking, инструментируйте его, чтобы считать каждый рекурсивный вызов, затем добавьте pruning и наблюдайте, как дерево рекурсии схлопывается — со счётом вызовов в доказательство.
Превратите ментальную модель юнита в работающий код: реализуйте шаблон choose-explore-undo для реальной задачи ограничений, инструментируйте дерево рекурсии, добавьте pruning и подтвердите ускорение измеренным счётом узлов до и после, а не интуицией.
Постройте решатель на backtracking для задачи ограничений (N-Queens или вариант Sudoku/subset-sum/word-search), докажите, что он находит все валидные решения, затем добавьте pruning и измерьте сокращение числа рекурсивных вызовов, которое он даёт.
- Таблица до/после: размер входа, счёт рекурсивных вызовов без pruning, счёт рекурсивных вызовов с pruning и число найденных решений — всё измерено по счётчику, а не оценено.
- Pruning существенно сокращает счёт рекурсивных вызовов (для N-Queens n = 8 полный перебор по расстановкам — это миллиарды; решатель с pruning посещает лишь тысячи узлов), при этом множество решений побайтово идентично между версиями.
- Каждое записанное решение — реальная копия: изменение одного решения после прогона не меняет ни одного другого, что доказывает, что вы делали снимок current, а не хранили ссылку.
- Короткий разбор с названием base case, выбора, ограничения и условия prune, плюс одно предложение о том, почему глубина на call stack остаётся O(n), даже когда число узлов меняется.
- Добавьте трассировку глубины/визуализацию, которая печатает дерево рекурсии (с отступом по глубине) для крошечного экземпляра, чтобы вы видели choose-explore-undo и подрезанные ветки напрямую.
- Преобразуйте рекурсивный решатель в итеративную версию с явным стеком и подтвердите, что она выдаёт те же решения, затем порассуждайте, какую из них вы бы отгрузили, будь глубина входа недоверенной.
- Добавьте мемоизацию в вариант с перекрывающимися подзадачами (например, подсчёт числа способов subset-sum) и сообщите, как счёт рекурсивных вызовов падает с экспоненциального к полиномиальному.
- Обобщите решатель, чтобы он принимал генератор выборов, проверку валидности и тест завершения как параметры, чтобы один движок решал все три ваши задачи-кандидата.
Это цикл, который вы запускаете на любой задаче перебора: назовите base case, выборы и ограничение; напишите скелет choose-explore-undo и записывайте копии; измерьте дерево рекурсии счётчиком вызовов; затем добавьте prune, который проверяет ограничение перед рекурсией, и наблюдайте, как число узлов схлопывается, пока множество ответов остаётся идентичным. Сделав это однажды на игрушечном решателе, вы навсегда закрепите шаблон и причину, по которой pruning важен.