Сокращение поиска ради соблюдения лимита времени
Отсекайте ветви, которые не могут улучшить результат
«Сокращение поиска ради соблюдения лимита времени» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
Почему важно отсечение
Обычный поиск с возвратом может исследовать слишком много ветвей и превысить ограничение времени. Отсечение заранее удаляет безнадёжные ветви, чтобы программа работала быстро. ✂️
Что на самом деле означает отсечение
Отсечение означает остановку ветви в тот момент, когда можно доказать, что она не приведёт к допустимому или лучшему ответу. Вы полностью пропускаете её исследование.
Отсечение по допустимости
Если текущий частичный выбор уже нарушает правило, немедленно возвращайте результат. Такая проверка допустимости не позволяет строить решение на некорректном состоянии.
if violates(cur):
returnОтсечение по границе
Отслеживайте лучший найденный ответ. Если наилучший результат, которого теоретически может достичь ветвь, хуже текущего лучшего результата, отсеките её. Это и есть граница для ветви.
Отсечение в коде
Здесь граница останавливает ветвь, когда даже оптимистичная оценка не может превзойти текущий лучший результат.
if cur_cost + best_possible <= best:
returnРазумно упорядочивайте варианты
Если сначала пробовать наиболее перспективный вариант, хороший ответ будет найден раньше. Это повышает границу и позволяет отсечь больше последующих ветвей.
Распространение ограничений
После выбора сузьте возможности последующих шагов. Удаление невозможных вариантов заранее называется распространением ограничений и уменьшает дерево поиска.
Устранение симметрии
Если две ветви являются зеркальными отражениями друг друга, исследуйте только одну. Устранение симметрии может вдвое или ещё сильнее сократить работу без потери ответов.
Мемоизируйте повторяющиеся состояния
Если одно и то же частичное состояние возникает снова, сохраните его результат. Мемоизация превращает повторяющиеся поддеревья в один быстрый поиск.
from functools import lru_cache
@lru_cache(maxsize=None)
def solve(state):
...Отсекайте рано, а не поздно
Проверяйте условие отсечения до рекурсивного вызова, а не после него. Раннее отсечение предотвращает напрасное расширение обречённой ветви.
Оценивайте до запуска
Всегда оценивайте количество ветвей в худшем случае с учётом ограничений. Если оно слишком велико, нужно усилить отсечение или выбрать новый подход.
Быстрая проверка
Какова цель отсечения в поиске с возвратом?
Повторение: отсекайте безнадёжные ветви
Вы научились выполнять отсечение с помощью проверок допустимости и границ, разумного упорядочивания, устранения симметрии и мемоизации, чтобы укладываться в ограничение времени. 🎯
Изучай Python с ИИ-репетитором — бесплатно
Пиши и запускай код прямо в браузере, получай мгновенную помощь от ИИ-репетитора 24/7 и продолжи учиться на сайте или в приложении.
- Курсы
- 30
- Уроки
- 120
Часто задаваемые вопросы
Урок «Сокращение поиска ради соблюдения лимита времени» бесплатный?
Да — полный текст урока «Сокращение поиска ради соблюдения лимита времени» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «Сокращение поиска ради соблюдения лимита времени»?
Отсекайте ветви, которые не могут улучшить результат Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.
Сколько времени занимает урок «Сокращение поиска ради соблюдения лимита времени»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Рекурсивное мышление: база и рекурсия
- Генерация всех подмножеств
- Перестановки и идея задачи о N ферзях
- Сокращение поиска ради соблюдения лимита времени