Понимание возврата к началу с использованием Python Руководство для начинающих

Возвращение к основам с помощью Python Руководство для начинающих

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

Backtracking

Типы Backtracking:

Хотя backtracking можно использовать для решения таких задач, как задачи принятия решения, задачи оптимизации и задачи перечисления, существуют различные типы Backtracking —

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

Подход:

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

Давайте научимся делать Backtracking в Python, рассмотрев несколько примеров:

1. Найти все подмножества заданного массива

Учитывая целочисленный массив nums с уникальными элементами, вернуть все возможные подмножества (множество всех подмножеств).

Результат не должен содержать повторяющихся подмножеств. Вернуть решение в любом порядке

Пример 1:

Input: nums = [1,2,3]Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Пример 2:

Input: nums = [0]Output: [[],[0]]

Код:

class Solution:    def subsets(self, nums: List[int]) -> List[List[int]]:        result, subset, = [], []        result = self.retrieve_subsets(nums, result, subset, 0)        return result        def retrieve_subsets(self, nums, result, subset, index):        result.append(subset[:])        for i in range(index, len(nums)):            subset.append(nums[i])            self.retrieve_subsets(nums, result, subset, i+1)            subset.pop()        return result

Объяснение:

* Начнем выполнение, взяв исходный массив - [1,2,3]* Начальное состояние    - Массив(nums) = [1,2,3]    - result = []    - subset = []    - index = 0* Состояние - 1 [Первый вызов функции]    - Результат: result = [[]]* Состояние - 2 [Рекурсивный вызов с индексом 0]    - index = 0    - subset = [1]    - рекурсивный вызов с обновленным subset и index = 1* Состояние - 3 [Рекурсивный вызов с индексом 1]    - index = 1    - subset = [1,2]    - рекурсивный вызов с обновленным subset и index = 2* Состояние - 4[Рекурсивный вызов с индексом 2]    - index = 2    - subset = [1,2,3]    - рекурсивный вызов с обновленным subset, так как нет элементов,      цикл завершается* Состояние - 5[Возврат к индексу 1]    - Возврат к предыдущему рекурсивному вызову, где index = 1    - Извлечение последнего элемента из subset, subset = [1,2]    - Цикл переходит к следующей итерации, i = 2,      добавление Arr[2] в subset, subset = [1, 2, 3].* Состояние - 6[Возврат к индексу 0]    - Возврат к предыдущему рекурсивному вызову, где index = 1    - Извлечение последнего элемента из subset, subset = [1]    - Цикл переходит к следующей итерации, i = 1,      добавление Arr[1] в subset, subset = [1, 3].и процесс продолжается, пока все возможные состояния не будут исследованы.Результат: result = [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

2. Все пути от источника до цели

Дан ориентированный ациклический граф (DAG) с узлами, помеченными от 0 до n – 1, найти все возможные пути от узла 0 к узлу n – 1 и вернуть их в любом порядке.

Граф задается следующим образом: граф [i] – это список всех узлов, которые можно посетить из узла i (то есть, есть направленное ребро от узла i к узлу graph[i][j]).

Пример 1:

Ввод: graph = [[1,2],[3],[3],[]]
Вывод: [[0,1,3],[0,2,3]]
Объяснение: Есть два пути: 0 -> 1 -> 3 и 0 -> 2 -> 3.

Пример 2:

Ввод: graph = [[4,3,1],[3,2,4],[3],[4],[]]
Вывод: [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

Код:

class Solution:    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:        hash_map = {i:graph[i] for i in range(len(graph))}        result, interm_res, current_node = [], [], 0        self.retrieve_path(hash_map, result, interm_res, current_node)        return result    def retrieve_path(self, hash_map, result, interm_res, current_node):        if current_node == len(hash_map.keys()) - 1:            result.append(interm_res + [current_node])        elif hash_map[current_node]:            for i in hash_map[current_node]:                self.retrieve_path(hash_map, result, interm_res+[current_node], i)

Объяснение:

- Метод allPathsSourceTarget:  * Принимает граф, содержащий список списков в качестве входных данных.  * Шаг первый - сопоставление направлений с узлами,     Для этого создается словарь для хранения информации о узлах и направлениях.  * Инициализация двух списков - result для сбора всех найденных путей и,    interm_res для хранения промежуточного пути в процессе построения и,    current_node для отслеживания текущего узла.  * Наконец, происходит вызов метода retrieve_path, который принимает все вышеуказанные    переменные в качестве входных данных.- Метод retrieve_path:  * Этот метод использует рекурсию для выполнения обратного поиска и нахождения всех     возможных путей.  * Для рекурсии нам нужно условие завершения, и здесь, если текущий узел    равен последнему числу в списке, то это означает, что путь найден, поэтому     он добавляет iterm_res с текущим узлом и добавляет его в result.  * если текущий узел имеет соединения, как в примере -1, [0,1,2] имеет    подключения, но 3 не имеет соединений, если существуют соединения,     то код перебирает их, чтобы найти возможные пути  * Для каждого соединения код выполняет рекурсивный вызов метода, передавая     обновленные параметры, пока не будут исследованы все соединения.

3. N-queens

Задача о n ферзях заключается в размещении n ферзей на шахматной доске размером n x n таким образом, чтобы ни одна ферзь не находилась под угрозой.

Учитывая целое число n, верните количество различных решений задачи n ферзей.

Пример 1:

Введите: n = 4Вывод: 2Пояснение: Как показано на картинке, есть два различных решения головоломки 4-ферзя.

Пример 2:

Введите: n = 1Вывод: 1

Код:

class Solution:    def totalNQueens(self, n: int) -> int:        def is_safe(board, current_queen, col):            for i in range(current_queen):                if board[i] == col or \                   board[i] - i == col - current_queen or \                   board[i] + i == col + current_queen:                    return False            return True        def solve(current_queen):            if current_queen== n:                nonlocal count                count += 1                return            for col in range(n):                if is_safe(board, current_queen, col):                    board[current_queen] = col                    solve(current_queen+ 1)            board = [-1] * n        count = 0        solve(0)        return count

Пояснение:

* Метод totalNQueens используется для вычисления N ферзей,   где N представляет количество ферзей, возможных на шахматной доске размером N*N.* Функция is_safe проверяет, безопасно ли разместить ферзя в   заданной позиции на шахматной доске. Она перебирает прямые линии и   диагонали ферзя и возвращает True, если безопасно, и наоборот.* Функция solve является рекурсивной функцией, которая   размещает всех ферзей на шахматной доске.* Если текущая ферзя равна n, это означает, что все ферзи   размещены на доске, поэтому результат увеличивается на 1.* В противном случае она проверяет каждую позицию в этой   строке, сделав рекурсивный вызов и пытаясь разместить ферзя,   если это безопасно, переходит к следующему ферзю в следующей строке.* Процесс продолжается до успешного исследования всех позиций.

Оптимизация и отсечение в возврате

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

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

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

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

  • Экспоненциальная сложность: Из-за множественных рекурсий у них может быть экспоненциальная сложность в худшем случае, что делает их непрактичными для больших проблем.
  • Потребление памяти: Рекурсивный возврат может потреблять значительное количество памяти из-за рекурсивного вызова стека, что может привести к переполнению стека или ошибкам связанным с памятью.
  • Баланс оптимизации: Чрезмерная оптимизация может привести к пропущенным решениям, в то время как не достаточная оптимизация может замедлить алгоритм, поэтому нахождение оптимальной оптимизации может быть сложным.

Есть и недостатки, и не забудьте о преимуществах, поскольку такова структура вселенной.

Если вы хотите изучить больше проблем с возвратом, используйте эту ссылку, которая содержит около 100 проблем.

Напишите мне, если вы застряли в какой-либо точке. Готов помочь. Счастливого кодинга….