В этом руководстве вы узнаете, что такое алгоритм обратного отслеживания. Также вы найдете пример подхода с возвратом.
Алгоритм поиска с возвратом - это алгоритм решения проблем, который использует метод грубой силы для поиска желаемого результата.
Подход грубой силы испытывает все возможные решения и выбирает желаемое / лучшее решение.
Термин "поиск с возвратом" предполагает, что, если текущее решение не подходит, следует вернуться и попробовать другие решения. Таким образом, в этом подходе используется рекурсия.
Этот подход используется для решения проблем, которые имеют несколько решений. Если вам нужно оптимальное решение, вы должны пойти на динамическое программирование.
Государственное дерево пространства
Дерево пространственных состояний - это дерево, представляющее все возможные состояния (решение или нерешение) проблемы от корня в качестве начального состояния до листа в качестве конечного состояния.
Государственное дерево пространства
Алгоритм обратного отслеживания
Backtrack (x), если x не является решением, вернуть false, если x является новым решением, добавить в список решений backtrack (развернуть x)
Пример подхода с возвратом
Задача: вы хотите найти все возможные способы расстановки 2-х мальчиков и 1 девочку на 3 скамейках. Ограничение: девушка не должна находиться на средней скамейке.
Решение: Всего их 3! = 6 возможностей. Мы попробуем все возможности и найдем возможные решения. Мы рекурсивно пробуем все возможности.
Все возможности:
Все возможности
Следующее дерево пространства состояний показывает возможные решения.
Дерево состояний со всеми решениями
Приложения алгоритма обратного отслеживания
- Чтобы найти все гамильтоновы пути, присутствующие в графе.
- Чтобы решить проблему N Queen.
- Проблема решения лабиринта.
- Проблема рыцарского тура.
