Метод поиска с возвратом. Общая схема рекурсивного поиска с возвратом. - EcsFlash/DataTypes GitHub Wiki

Метод поиска с возвратом (backtracking) — это алгоритмический подход для решения задач, где нужно найти все возможные решения или одно подходящее, перебирая варианты и возвращаясь назад, если текущий путь не приводит к решению. Он особенно полезен для комбинаторных задач, таких как задачи о расстановке ферзей, лабиринты или головоломки вроде судоку.

Общая схема рекурсивного поиска с возвратом

1. Определение состояния:

   • Задача представляется в виде дерева решений, где каждый узел — это частичное решение, а листья — полные решения (или тупики).
   • Состояние включает текущую конфигурацию (например, позиции фигур на доске) и параметры, определяющие, какие шаги уже сделаны.

2. Рекурсивная функция:

   • Функция принимает текущее состояние и пытается расширить его, добавляя следующий шаг (например, размещение следующего ферзя).
   • Для каждого возможного варианта шага:
     • Делается шаг (добавляется элемент в решение).
     • Проверяется, является ли текущее состояние допустимым (например, не нарушает ли правила задачи).
     • Если состояние допустимо, рекурсивно вызывается та же функция для следующего шага.
     • Если шаг приводит к тупику (нет решения), происходит возврат (backtrack): шаг отменяется, и пробуется следующий вариант.

3. База рекурсии:

   • Условие остановки:
     • Если найдено полное решение (например, все ферзи расставлены), оно сохраняется или выводится.
     • Если текущее состояние недопустимо или невозможно продолжить, рекурсия завершается, и происходит возврат к предыдущему состоянию.

4. Обработка возврата:

   • После проверки всех вариантов для текущего шага, если решение не найдено, алгоритм возвращается к предыдущему шагу и пробует другой вариант.

func backtrack(состояние){
    if является_решением(состояние) {
        сохранить_решение(состояние)
        return
    }
    for вариант, _ := range возможные_варианты(состояние){ //типо for .. in ...
        if допустимый_вариант(вариант, состояние):
            применить_вариант(вариант, состояние)
            backtrack(состояние)  // рекурсивный вызов
            отменить_вариант(вариант, состояние)  // возврат
    }
}