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

Что такое алгоритм возврата?

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

Этот алгоритм считается лучше и эффективнее, чем подход Brute Force. В отличие от Bruteforce, который пробует все возможные решения, Backtracking фокусируется на поиске только одного окончательного решения в соответствии с заданными ограничения. Он также экономит время и память, отменяя последний шаг (возврат) и пробуя другой вариант после достижения тупика. Кроме того, он останавливается, как только находится допустимое решение.

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

Как работает алгоритм возврата?

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

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

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

Алгоритм обратного отслеживания в общем случае состоит из следующих шагов для решения проблемы:

Шаг 1) Инициализация: Начните с первоначального пустого/частичного решения.

Шаг 2) Выбор: На основе определенных критериев и ограничений выберите один вариант для расширения текущего решения.

Шаг 3) Исследование: Рекурсивное решение путем рассмотрения выбранного кандидата и продвижения вперед в процессе решения проблемы.

Шаг 4) Проверка ограничений: Проверьте, нарушает ли текущее частичное решение какие-либо ограничения на каждом шаге. Если это так, вернитесь к предыдущему шагу и попробуйте другого кандидата.

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

Шаг 6) Возврат: Если текущий вариант не решает данную проблему, он возвращается в предыдущее состояние. Затем он рассматривает новый вариант для решения данной проблемы.

Шаг 7) Повторить: Продолжайте выполнять эти шаги до тех пор, пока проблема не будет решена или пока не будут исследованы все варианты.

Рекурсивная природа алгоритма обратного отслеживания

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

def find_solutions(n, other_params):
    if found_a_solution():
        increment_solutions_found()
        display_solution()
        if solutions_found >= solution_target:
            exit_program()
        return	

    for val in range(first, last+1):
        if is_valid(val, n):
            apply_value(val, n)
            find_solutions(n + 1, other_params)
            remove_value(val, n)

Общие термины, связанные с проблемами возврата

Вот некоторые основные термины, связанные с методом обратного отслеживания:

  • Вектор решения: Представляет решения в виде n-кортежей, например (X1, X2, …, Xn).
  • ограничения: Правила, ограничивающие значения X, неявные и явные.
  • Пространство решений: Все допустимые значения X, удовлетворяющие явным ограничениям.
  • Дерево пространства состояний: Представляет пространство решений в виде дерева.
  • Государственное пространство: Описывает пути в дереве пространства состояний.
  • Состояние проблемы: Узлы в дереве поиска, представляющие частичные решения.
  • Решение Состояний: Состояния, формирующие допустимые кортежи решений в S.
  • Ответить Штаты: Удовлетворить неявным ограничениям и получить желаемые решения.
  • Перспективный узел: Приводит к желаемым решениям и остается осуществимым.
  • Неперспективный узел: Приводит к невозможным состояниям, которые далее не исследуются.
  • Живой узел: Создано с неисследованными потомками.
  • E-узел: Активный узел с продолжающейся генерацией дочерних элементов.
  • Мертвый узел: Дальнейшее расширение всех созданных потомков не производится.
  • Генерация узлов в глубину: Использует последний активный узел в качестве следующего E-узла.
  • Ограничивающая функция: Максимизирует или минимизирует B(x1, x2, …, Xa) для оптимизации.
  • Статические деревья: Формулировка дерева, независимая от экземпляра проблемы.
  • Динамические деревья: Формулировка дерева меняется в зависимости от конкретного случая проблемы.

Когда следует использовать алгоритм возврата?

Мы можем выбрать метод обратного отслеживания для решения сложной проблемы, когда:

  • Существует множество вариантов: Откат назад подходит, если на каждом этапе процесса решения проблемы существует много вариантов. Эти варианты могут относиться к выбору элементов и ходов.
  • Нет однозначно лучшего выбора: Когда недостаточно информации для определения наилучшего выбора среди доступных вариантов, можно использовать алгоритм обратного отслеживания.
  • Решение приводит к большему выбору: Вы можете выбрать метод возврата для систематического пересмотра вариантов.
  • Необходимо изучить все возможные решения: Метод возврата систематически исследует все решения, принимая ряд решений, основанных друг на друге.

Типы проблем с возвратом

В алгоритмах обратного отслеживания есть три типа проблем: проблемы принятия решений, проблемы оптимизации и проблемы перечисления. Давайте узнаем о них ниже.

  1. Решение проблемы: В этом типе задач цель состоит в том, чтобы определить, существует ли допустимое решение. Мы проверяем ответы «да» и «нет». Например, задача n-ферзей. Это задача на решение, которая проверяет вероятность размещения n ферзей на шахматной доске n × n без нападения друг на друга.
  2. Проблема оптимизации: В задачах оптимизации цель состоит в том, чтобы найти наилучшее возможное решение среди множества вариантов. Это может включать определение максимального и минимального значений определенной функции или переменной. Например, рассмотрим задачу о рюкзаке, где цель состоит в том, чтобы максимизировать общую стоимость предметов в сумке, соблюдая при этом ограничение по весу.
  3. Проблема перечисления: Его цель — найти все возможные решения данной проблемы. Мы перечисляем все допустимые варианты без каких-либо пропусков. Примером может служить генерация всех возможных комбинаций букв из заданного набора символов.

Применение возврата и примеры

Существуют различные применения Backtracking. Некоторые из них описаны ниже с помощью их псевдокода.

  1. Sudoku Solver: Эта задача содержит подсетку 3×3 с повторяющимися числами. Метод обратного отслеживания покажет, что решение возвращает false, что указывает на необходимость другого размещения чисел.
  2. function solveSudoku(board):
        if no empty cells:
            return true  # Sudoku is solved
        for each empty cell (row, col):
            for num from 1 to 9:
                if num is valid in (row, col):
                    place num in (row, col)
                    if solveSudoku(board):
                        return true
                    remove num from (row, col)
        return false  # No valid solution
    
  3. Проблема N-ферзя: Метод обратного отслеживания определяет, как расставить ферзей на шахматной доске N × N так, чтобы ни один из них не угрожал друг другу.
  4. function solveNQueens(board, col):
        if col >= N:
            return true  # All queens are placed
        for each row in the column col:
            if isSafe(board, row, col):
                place queen at (row, col)
                if solveNQueens(board, col + 1):
                    return true
                remove queen from (row, col)
        return false  # No valid solution in this branch
    
  5. Задача о сумме подмножества: Он используется для нахождения подмножества чисел из заданного набора, которое в сумме дает определенную целевую сумму.
  6. function subsetSum(nums, target, index, currentSubset):
        if target == 0:
            print(currentSubset)  # Subset with the target sum found
            return
        if index >= len(nums) or target < 0:
            return
       currentSubset.add(nums[index])
       subsetSum(nums, target - nums[index], index + 1, currentSubset)
       currentSubset.remove(nums[index])
       subsetSum(nums, target, index + 1, currentSubset)
    
  7. Проблема гамильтонова цикла: Возврат можно применить для поиска замкнутого тура в графе, который посещает каждую вершину ровно один раз.
  8. Проблема крысы в ​​лабиринте: Метод возврата используется для нахождения пути крысы от начальной точки лабиринта до выхода.

Преимущества и недостатки алгоритма возврата

Преимущества алгоритма возврата

Методы обратного отслеживания используются для решения сложных проблем. Они имеют много преимуществ, таких как:

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

Недостатки алгоритма возврата

Методы обратного отслеживания также имеют некоторые ограничения, такие как временная сложность. Этот метод имеет следующие недостатки:

  • Гарантированного решения не существует.
  • Он медленнее из-за большого количества комбинаций.
  • Он имеет высокую временную сложность из-за множества возможностей.
  • Он не подходит для условий реального времени, поскольку поиск наилучшего решения может занять много времени.
  • Эффективность зависит от уровня сложности проблемы.

Разница между возвратом и рекурсией

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

Заключение

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

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

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