Бэктрекинг
Бэктрекинг (или бектрекинг) — это метод поиска решения, при котором алгоритм последовательно строит вариант, а при нарушении условия отменяет последний выбор и пробует другой. Такой подход особенно полезен, когда решения образуют дерево возможных вариантов.
Бэктрекинг является способом построения алгоритма поиска. На каждом шаге выбирается один из допустимых вариантов и изменяется текущее состояние перебора. Если частичное решение уже не может стать полным, ветвь прекращают. Этот приём называют отсечением ветвей перебора.
Как работает метод
- Выбрать очередной вариант.
- Добавить его к частичному решению.
- Проверить ограничения.
- Если решение допустимо, перейти к следующему шагу.
- Если продолжение невозможно, отменить выбор и вернуться назад.
Нужно составить двузначные числа из цифр 1, 2 и 3 без повторений. Сначала выбираем 1, затем пробуем 2 и получаем 12. После возврата к позиции единиц выбираем 3 и получаем 13. Затем возвращаемся к первой позиции и рассматриваем ветви, начинающиеся с 2 и 3.
Что делает алгоритм, если выбранный вариант нарушает ограничение?
При обычном полном переборе варианты часто строятся и проверяются только в конце. Бэктрекинг проверяет частичное решение по ходу построения и поэтому может не рассматривать заведомо невозможные ветви. Однако он не всегда быстрее: время зависит от числа вариантов и эффективности проверок.
Главное
- Бэктрекинг строит решение по шагам и возвращается назад при нарушении условий.
- Каждый выбор образует ветвь дерева вариантов; невозможные ветви можно отсекать.
- Метод применяют при построении перестановок, комбинаций и других задач перебора.