Поиск с возвратом

Привет, Хаброжители! Мы открыли предзаказ на книгу «Паттерны Coding Interview. Подготовка к сложному техническому интервью» Алекса Сюя и Шона Гунавардана. Предлагаем ознакомиться с главой 14 «Поиск с возвратом».

Основные понятия

Представьте, что вы находитесь на перекрестке в лабиринте и знаете, что один из трех маршрутов впереди ведет к выходу:

Однако вы не знаете, какой путь выбрать. Чтобы найти выход, вы решаете попробовать каждый вариант по очереди, начиная с варианта A. Идя по коридору A, вы доходите до нового перекрестка, где открываются еще два маршрута — D и E:

Вы пробуете вариант D, но он ведет в тупик. Тогда вы возвращаетесь назад к предыдущему перекрестку:

Затем вы пробуете вариант E, но он также приводит в тупик, поэтому вы возвращаетесь ко второму перекрестку. После того как становится ясно, что ни путь D, ни путь E не подходят, вы снова возвращаетесь к первому перекрестку:

Определив, что путь A не ведет к выходу, вы переходите к пути B и обнаруживаете, что он ведет к выходу:

Этот метод перебора всех возможных путей с возвратом при неудаче называется поиском с возвратом (backtracking).

Дерево состояний

В поиске с возвратом дерево состояний, также называемое деревом решений, — это концептуальное дерево, которое строится с учетом всех возможных решений, которые можно принять в каждой точке процесса.

Например, так можно представить дерево состояний для сценария с лабиринтом:

Основными структурными элементами дерева состояний являются:

• Ребра: каждое ребро представляет возможное решение, ход или действие.

• Корневой узел представляет исходное состояние или позицию до принятия каких-либо решений.

• Промежуточные узлы представляют частично завершенные состояния или промежуточные позиции.

• Концевые узлы представляют полные или недопустимые решения.

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

Построение дерева состояний помогает визуализировать все пространство решений и все возможные варианты действий. Кроме того, это отличный способ понять работу алгоритма. Определив, как обходить это дерево, мы, по сути, создаем алгоритм поиска с возвратом.

Алгоритм поиска с возвратом

Обход дерева состояний обычно выполняется с помощью рекурсивного обхода в глубину. Рассмотрим его реализацию на высоком уровне.

Условие завершения определяет, когда путь должен завершиться, и показывает, когда найдено допустимое или недопустимое решение.

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

1. применяем решение и обновляем текущее состояние соответственно;

2. рекурсивно исследуем все ветви, исходящие из обновленного состояния, вызывая функцию обхода в глубину для этого состояния;

3. возвращаемся назад, отменяя принятое решение и восстанавливая предыдущее состояние.

Ниже приведен упрощенный шаблон для поиска с возвратом:

def dfs(state):
    # Условие завершения.
    if meets_termination_condition(state):
        process_solution(state)
        return
    # Исследуем каждое возможное решение для текущего
    # состояния.
    for decision in possible_decisions(state):
        make_decision(state, decision)
        dfs(state)
        undo_decision(state, decision) # Возврат назад.

Анализ временной сложности

Анализ временной сложности алгоритмов поиска с возвратом требует понимания коэффициента ветвления и глубины дерева состояний:

• Коэффициент ветвления — это количество потомков у каждого узла. Обычно этот коэффициент представляет максимальное число решений, которые можно принять для данного состояния.

• Глубина — это длина самого глубокого пути в дереве состояний. Соответствует числу решений или шагов, необходимых для достижения полного решения.

Временная сложность часто оценивается как О(bd), где b — коэффициент ветвления, а d — глубина. Это связано с тем, что в худшем случае необходимо исследовать каждый узел на каждом уровне дерева при типичном алгоритме поиска с возвратом.

Когда использовать поиск с возвратом

Поиск с возвратом полезен, когда нужно исследовать все возможные решения задачи. Например, если необходимо найти все возможные способы расположения элементов или сгенерировать все возможные подмножества, перестановки или комбинации, поиск с возвратом поможет определить каждое возможное решение.

Пример из реальной жизни

Алгоритмы ИИ для игр. Поиск с возвратом используется в алгоритмах искусственного интеллекта для игр, таких как шахматы и го, для исследования возможных ходов и стратегий. Программы анализируют каждый потенциальный ход, симулируют развитие игры и оценивают результат. Если ход приводит к неблагоприятной позиции, программа возвращается к предыдущему ходу и пробует альтернативные варианты, поэтапно исследуя дерево игры до нахождения оптимальной стратегии.

Содержание главы

Нахождение всех перестановок

Вернуть все возможные перестановки данного массива уникальных целых чисел. Они могут быть возвращены в любом порядке.

Пример:
Ввод: nums = [4, 5, 6]
Вывод: [[4, 5, 6], [4, 6, 5], [5, 4, 6], [5, 6, 4], [6, 4, 5], [6, 5, 4]]

Разбор решения

Наша задача довольно проста: найти все перестановки данного массива. Ключевое слово здесь — «все». Для этого нужен алгоритм, который генерирует все возможные перестановки по одной. Техника, которая наилучшим образом подходит для этой задачи, — поиск с возвратом. Как и в любом решении с использованием этого метода, полезно сначала визуализировать дерево состояний.

Дерево состояний

Давайте разберем, как построить одну перестановку. Рассмотрим массив [4, 5, 6]. Можем начать с выбора одного числа из этого массива для первой позиции перестановки. Для второй позиции выбираем другое число. Продолжаем добавлять числа таким образом, пока не будут использованы все числа из массива. Чтобы избежать повторов, будем отслеживать уже использованные числа с помощью хеш-множества used:

Теперь, когда мы нашли одну перестановку, давайте используем поиск с возвратом, чтобы найти остальные. Начнем с удаления последнего добавленного числа, 6, возвращаясь к [4, 5]:

Есть ли другие числа, которые мы можем добавить к [4, 5]? В данный момент единственным вариантом является 6, который мы уже рассмотрели. Поэтому делаем очередной шаг назад, удаляя 5 и возвращаясь к [4]:

Можем ли мы добавить к [4] число, отличное от 5? Да, можем использовать 6, поэтому добавляем его и продолжаем поиск:

В данный момент единственным числом, которое можно использовать, является 5, поэтому добавляем его к [4, 6], получая еще одну перестановку:

Следуя этому процессу поиска с возвратом, пока не будут исследованы все ветви, мы можем сгенерировать все перестановки:

Каждый раз, когда мы получаем перестановку (то есть когда размер формируемой перестановки достигает n, где n — длина входного массива), добавляем ее в результат.

Обход дерева состояний

Генерация всех перестановок может быть выполнена через обход дерева состояний.

Каждый узел этого дерева, за исключением концевых, представляет кандидат в перестановку: частично построенную перестановку. Корневой узел — это пустая перестановка, а по мере продвижения вниз по дереву к каждому кандидату добавляется очередной элемент. Концевые узлы представляют собой полностью сформированные перестановки.

Начиная с корневого узла, можно обойти это дерево с помощью поиска с возвратом:

1. Выбираем неиспользованное число и добавляем его к текущему кандидату в перестановку. Отмечаем это число как использованное, добавляя его в хеш-множество used.

2. Выполняем рекурсивный вызов с обновленным кандидатом, чтобы исследовать его ветви.

3. Возврат назад: удаляем последнее добавленное число из текущего кандидата и из хеш-множества used.

Каждый раз, когда кандидат в перестановку достигает длины n, добавляем его в результат.

Реализация

def find_all_permutations(nums: List[int]) -> List[List[int]]:
    res = []
    backtrack(nums, [], set(), res)
    return res

def backtrack(nums: List[int], candidate: List[int], used: Set[int],
              res: List[List[int]]) -> None:
    # Если текущий кандидат является полной перестановкой,
    # добавляем ее в результат.
    if len(candidate) == len(nums):
        res.append(candidate[:])
        return
    for num in nums:
        if num not in used:
    # Добавляем num к текущей перестановке и
    # отмечаем как использованное.
    candidate.append(num)
    used.add(num)
    # Рекурсивно исследуем все ветви с обновленным
    # кандидатом.
    backtrack(nums, candidate, used, res)
    # Возврат назад: отменяем изменения.
    candidate.pop()
    used.remove(num)

Анализ сложности

Временная сложность функции find_all_permutations составляет О(n × n!).
Пояснение:

• Начиная с корня, мы рекурсивно исследуем n кандидатов.

• Для каждого из этих n кандидатов исследуем n – 1 кандидатов, затем n – 2 и так далее, пока не будут исследованы все перестановки. В итоге получаем n × (n – 1) × (n – 2) ×·… × 1 = n! перестановок.

• Для каждой из n! перестановок мы создаем ее копию и добавляем в результат, что занимает О(n) времени.

Итого временная сложность: О(n!) × О(n) = О(n × n!).

Пространственная сложность составляет О(n), так как максимальная глубина дерева рекурсии равна n. Алгоритм также использует структуры candidate и used, каждая из которых требует О(n) памяти. Заметьте, что массив res не учитывается в оценке пространственной сложности.

Оформить предзаказ на книгу «Паттерны Coding Interview. Подготовка к сложному техническому интервью» со скидкой 35% можно на нашем сайте по промокоду – Предзаказ