Жадные алгоритмы. Перебор с возвратом: ЕГЭ по информатике

Жадные алгоритмы и перебор с возвратом (backtracking) — два подхода к решению задач оптимизации и поиска. Жадный алгоритм на каждом шаге делает локально оптимальный выбор, надеясь на глобальный оптимум; он прост и быстр, но не всегда даёт верный ответ. Перебор с возвратом систематически перебирает…

Что нужно знать

• Жадный алгоритм: выбор на каждом шаге локально оптимального решения без пересмотра предыдущих выборов.
• Жадный алгоритм не всегда приводит к глобально оптимальному решению; для доказательства оптимальности нужно свойство жадного выбора и оптимальность подзадач.
• Примеры жадных алгоритмов: задача о выборе заявок (интервалов), алгоритм Дейкстры (с оговорками), алгоритм Прима и Краскала для минимального остовного дерева, задача о рюкзаке (жадность по удельной стоимости не всегда…
• Перебор с возвратом (backtracking) — метод поиска решения, при котором строится дерево вариантов и происходит возврат при обнаружении тупика.
• Перебор с возвратом часто реализуется рекурсивно; важна отсечка (pruning) для сокращения перебора.
• Классические задачи на перебор с возвратом: задача о ферзях, судоку, генерация перестановок/сочетаний, задача о рюкзаке (полный перебор), лабиринт.

Термины и понятия

• Жадный алгоритм: алгоритм, который на каждом шаге делает локально оптимальный выбор, не учитывая будущие последствия, и не пересматривает…
• Перебор с возвратом (backtracking): метод решения задач, при котором решение строится по шагам, и при обнаружении невозможности продолжения…
• Отсечка (pruning): исключение из рассмотрения части вариантов, которые заведомо не могут привести к решению, для ускорения перебора.
• Пространство состояний: множество всех возможных конфигураций в задаче поиска, представленное в виде дерева или графа.
• Оптимальное решение: решение задачи, обладающее наилучшим значением целевой функции среди всех допустимых.
• Локальный оптимум: наилучшее решение в некоторой окрестности текущего состояния, но не обязательно глобальное.
• Глобальный оптимум: наилучшее решение среди всех допустимых.
• Рекурсия: способ определения функции, при котором она вызывает саму себя.

Частые ошибки

• Уверенность, что жадный алгоритм всегда даёт оптимальное решение (например, в задаче о рюкзаке жадность по стоимости или весу может быть неоптимальной).
• Неправильная реализация перебора с возвратом: отсутствие возврата состояния (отката) после рекурсивного вызова, что приводит к неверным результатам.
• Забывают про отсечку в переборе, что ведёт к экспоненциальному времени и превышению лимита на экзамене.
• Ошибки в рекурсивных функциях: неверное условие выхода из рекурсии или отсутствие такового.

Как пройти тему

В курсе «Информатика» тема «Жадные алгоритмы. Перебор с возвратом» занимает 2 занятия по 40 минут: репетитор объясняет материал, задаёт вопросы как на экзамене, разбирает ваши ответы и в конце ставит оценку. Это обзор темы, полный разбор — в занятии. ИИ может ошибаться: проверяйте важное по учебнику. Занятия не заменяют живого репетитора и не гарантируют результат на экзамене.

Другие темы раздела

• Понятие алгоритма. Свойства алгоритмов. Способы записи
• Базовые алгоритмические конструкции: следование, ветвление, цикл
• Вспомогательные алгоритмы. Рекурсия
• Анализ алгоритмов. Определение результата работы алгоритма
• Поиск ошибок в алгоритмах. Отладка
• Обработка одномерных массивов: поиск, сортировка, статистика

← Предыдущая тема: Динамическое программирование в задачах обработки данных
Следующая тема: Структуры данных: стеки, очереди, списки, деревья

Все темы: ЕГЭ по информатике