Состояние перебора
Состояние перебора — это описание того, что алгоритм уже выбрал, на каком шаге находится и какие варианты ещё может проверить. Оно позволяет точно продолжить перебор после очередного шага или возврата.
Что входит в состояние
Для задачи на построение последовательности состоянием может быть префикс \(x_1, x_2, \ldots, x_k\), где \(k\) — число уже выбранных элементов. Также нужно знать, какие элементы использованы и какие ограничения уже нарушать нельзя. Два состояния считаются разными, если из них алгоритм может сделать разные следующие шаги.
Здесь \(x_1,\ldots,x_k\) — текущий частичный вариант, \(k\) — его длина, \(U\) — множество использованных объектов, а \(C\) — текущие ограничения или дополнительные параметры. Набор компонентов зависит от задачи: иногда достаточно хранить только \(k\) и выбранные значения.
Пусть строится перестановка чисел \(1,2,3\). После выбора \(2,1\) состояние можно записать так: текущий вариант — \((2,1)\), позиция \(k=2\), использованы числа \(\{1,2\}\), доступный следующий выбор — \(3\). После выбора \(3\) получаем полный вариант \((2,1,3)\). Если продолжение невозможно, алгоритм возвращается к состоянию \((2)\) и пробует другой второй элемент.
Состояние перебора — не обязательно готовое решение. Частичный вариант \((2,1)\) описывает положение алгоритма, но ещё не является полной перестановкой. Не следует также путать состояние с деревом вариантов: дерево содержит все возможные состояния и переходы, а состояние — только одну текущую вершину.
Какое состояние нужно восстановить при возврате после неудачного выбора?
В реализации состояние часто хранится в переменных и в стеке рекурсивных вызовов. Каждый рекурсивный вызов соответствует одному уровню перебора. При переходе к следующему уровню состояние расширяется, а при возврате изменённые данные должны быть восстановлены. В решении методом перебора с возвратом правильное управление состоянием особенно важно: ошибка в восстановлении приводит к пропуску вариантов или к повторному использованию элементов.
Главное
- Состояние перебора описывает текущий частичный вариант, позицию и ограничения алгоритма.
- При углублении состояние расширяется, а при возврате восстанавливается.
- Состояние — одна текущая вершина дерева вариантов, а не всё дерево и не обязательно готовое решение.