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

![](ru/docs/assets/media/image778.jpeg){width="3.630207786526684in" height="4.697916666666667in"}

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

> *Алгоритм поиска с возвратом* -- это метод решения задач путем перебора. Его основная идея заключается в том, чтобы, начиная с начального состояния, осуществлять грубый поиск всех возможных решений, фиксируя правильное найденное решение. Процесс поиска продолжается до тех пор, пока не будет найдено решение или не будут исчерпаны все возможные варианты.
>
> Алгоритмы поиска с возвратом обычно используют поиск в глубину для об- хода пространства решений. В разделе «Двоичные деревья» упоминалось, что прямой, симметричный и обратный обходы относятся к поиску в глубину. Да- лее, используя прямой обход, мы реализуем задачу поиска с возвратом, чтобы постепенно понять принцип работы этого алгоритма.
>
> Для решения этой задачи мы выполняем предварительный обход дерева и проверяем, равно ли значение текущего узла 7. Если равно, то добавляем зна- чение этого узла в список результатов res. Процесс представлен на рис. 13.1 и в следующем коде.
>
> \# === File: preorder_traversal_i_compact.py === def pre_order(root: TreeNode):
>
> \"\"\" Предварительный обход: пример 1.\"\"\" if root is None:
>
> return
>
> if root.val == 7:
>
> \# Запись решения. res.append(root)
>
> pre_order(root.left)
>
> pre_order(root.right)
>
> ![](ru/docs/assets/media/image781.jpeg)Поиск в глубину
>
> Прямой порядок обхода Посетить узел в
>
> **Выполнить прямой обход двоичного дерева и записать узлы со значением 7**
>
> **Рис. 13.1.** Поиск узлов в предварительном обходе

1.  **Попытка и возврат**

> **Алгоритм называется поиском с возвратом, потому что при поиске в пространстве решений он использует стратегию попытки и возврата**. Когда алгоритм сталкивается с состоянием, в котором невозможно продолжать или невозможно получить удовлетворительное решение, он отменяет преды- дущий выбор, возвращается к предыдущему состоянию и пробует другие воз- можные варианты.
>
> В примере 1 посещение каждого узла представляет собой попытку, а пере- ход через листовой узел или возврат к родительскому узлу через return озна- чает возврат.
>
> Стоит отметить, что **откат включает не только возврат функции**. Чтобы объяснить это, мы немного расширим пример 1.
>
> Возьмем за основу код для примера 1. Нам потребуется добавить список path для записи пути посещенных узлов. Когда будет найден узел со значением 7, скопируем path и добавим его в список результатов res. После завершения об- хода res будет содержать все решения. Код реализации представлен ниже.
>
> \# === File: preorder_traversal_ii_compact.py === def pre_order(root: TreeNode):
>
> \"\"\" Предварительный обход: пример 2.\"\"\" if root is None:
>
> return \# Попытка.
>
> path.append(root) if root.val == 7:
>
> \# Запись решения. res.append(list(path))
>
> pre_order(root.left)
>
> pre_order(root.right) \# Возврат.
>
> path.pop()
>
> В каждой попытке мы добавляем текущий узел в path для записи пути. Перед возвратом необходимо удалить этот узел из path, чтобы **восстановить состо- яние до этой попытки**.
>
> Изучив процесс выполнения алгоритма на рис. 13.2, **можно представить попытку и возврат как движение вперед и отмену**, как два противополож- ных действия.
>
> ![](ru/docs/assets/media/image784.jpeg)

![](ru/docs/assets/media/image786.jpeg)![](ru/docs/assets/media/image788.jpeg)

> **Рис. 13.2.** Попытка и возврат. Шаги 1--3
>
> ![](ru/docs/assets/media/image790.jpeg)

![](ru/docs/assets/media/image792.jpeg)![](ru/docs/assets/media/image794.jpeg)

> **Рис. 13.2.** *Продолжение*. Шаги 4--6
>
> ![](ru/docs/assets/media/image796.jpeg)

![](ru/docs/assets/media/image798.jpeg)![](ru/docs/assets/media/image800.jpeg)

> **Рис. 13.2.** *Продолжение*. Шаги 7--9
>
> ![](ru/docs/assets/media/image802.jpeg)

![](ru/docs/assets/media/image804.jpeg)

### Обрезка

> **Рис. 13.2.** *Окончание*. Шаги 10--11
>
> Сложные задачи поиска с возвратом обычно содержат одно или несколько ограничений, **которые можно использовать для обрезки**.
>
> Для выполнения данного условия **требуется добавить операцию обрезки**: в процессе поиска, если встречается узел со значением 3, следует немедленно вернуться, не продолжая поиск. Код реализации представлен ниже.
>
> \# === File: preorder_traversal_iii_compact.py ===
>
> def pre_order(root: TreeNode):
>
> \"\"\" Предварительный обход: пример 3.\"\"\" \# Обрезка.
>
> if root is None or root.val == 3: return
>
> \# Попытка.
>
> path.append(root) if root.val == 7:
>
> \# Запись решения. res.append(list(path))
>
> pre_order(root.left) pre_order(root.right) \# Возврат.
>
> path.pop()
>
> Обрезка является очень наглядным термином. В процессе поиска **мы обре- заем ветви поиска**, **не удовлетворяющие заданным условиям**, и избегаем множества бессмысленных попыток, тем самым повышая эффективность по- иска, как показано на рис. 13.3.

![](ru/docs/assets/media/image806.jpeg)

> **Рис. 13.3.** Обрезка в соответствии с заданными условиями

### Каркас кода

> Далее мы попытаемся сформировать основной каркас операций «попытка, возврат, обрезка» для повышения универсальности кода.
>
> В следующем каркасе кода state обозначает текущее состояние задачи, а choices -- возможные выборы в текущем состоянии:
>
> def backtrack(state: State, choices: list\[choice\], res: list\[state\]): \"\"\" Каркас алгоритма поиска с возвратом.\"\"\"
>
> \# Проверка, является ли состояние решением. if is_solution(state):
>
> \# Запись решения. record_solution(state, res)
>
> \# Не продолжать поиск. return
>
> \# Перебор всех вариантов. for choice in choices:
>
> \# Обрезка: проверка легитимности выбора. if is_valid(state, choice):
>
> \# Попытка: сделать выбор, обновить состояние. make_choice(state, choice)
>
> backtrack(state, choices, res)
>
> \# Возврат: отмена выбора, возврат к предыдущему состоянию. undo_choice(state, choice)
>
> Теперь на основе каркаса кода решим пример 3. Состояние state -- это путь обхода узлов, выбор choices -- это левый и правый дочерние узлы текущего узла, результат res -- список путей.
>
> \# === File: preorder_traversal_iii_template.py === def is_solution(state: list\[TreeNode\]) -\> bool:
>
> \"\"\" Проверка, является ли текущее состояние решением.\"\"\" return state and state\[-1\].val == 7
>
> def record_solution(state: list\[TreeNode\], res: list\[list\[TreeNode\]\]): \"\"\" Запись решения.\"\"\"
>
> res.append(list(state))
>
> def is_valid(state: list\[TreeNode\], choice: TreeNode) -\> bool: \"\"\" Проверка легитимности выбора в текущем состоянии.\"\"\" return choice is not None and choice.val != 3
>
> def make_choice(state: list\[TreeNode\], choice: TreeNode): \"\"\" Обновление состояния.\"\"\"
>
> state.append(choice)
>
> def undo_choice(state: list\[TreeNode\], choice: TreeNode): \"\"\" Восстановление состояния.\"\"\"
>
> state.pop()
>
> def backtrack(
>
> state: list\[TreeNode\], choices: list\[TreeNode\], res: list\[list\[TreeNode\]\]
>
> ):
>
> \"\"\" Поиск с возвратом: пример 3.\"\"\"
>
> \# Проверка, является ли состояние решением. if is_solution(state):
>
> \# Запись решения. record_solution(state, res)
>
> \# Перебор всех вариантов. for choice in choices:
>
> \# Обрезка: проверка легитимности выбора. if is_valid(state, choice):
>
> \# Попытка: сделать выбор, обновить состояние. make_choice(state, choice)
>
> \# Переход к следующему выбору.
>
> backtrack(state, \[choice.left, choice.right\], res)
>
> \# Возврат: отмена выбора, возврат к предыдущему состоянию. undo_choice(state, choice)
>
> Согласно условию задачи после нахождения узла со значением 7 необходи- мо продолжать поиск, **поэтому следует удалить оператор** return **после запи- си решения**. На рис. 13.4 сравнивается процесс поиска с сохранением и удале- нием оператора return.
>
> ![](ru/docs/assets/media/image808.jpeg)После записи решения остановить поиск
>
> **Сохранение return**
>
> Возврат после записи решения, не продолжать поиск
>
> **Удаление return**
>
> Не возвращаться после записи решения, продолжить поиск
>
> **Рис. 13.4.** Сравнение процесса поиска с сохранением и удалением return
>
> По сравнению с реализацией на основе предварительного обхода, реали- зация на основе каркаса поиска с возвратом выглядит более громоздкой, но обладает большей универсальностью. На самом деле многие задачи поиска с возвратом можно решить в рамках этого каркаса. Необходимо лишь опре- делить state и choices в соответствии с конкретной задачей и реализовать ме- тоды каркаса.

### Основные термины

> Для более четкого понимания алгоритмических задач мы систематизируем значения часто используемых терминов обратного поиска и приведем соот- ветствующие примеры для задачи 3, как показано в табл. 13.1.
>
> **Таблица 13.1.** Основные термины обратного поиска

+---------------+----------------------------------------+-----------------------------------------+
| > **Термин**  | > **Определение**                      | > **Пример 3**                          |
+===============+========================================+=========================================+
| > Решение     | > Ответ, удовлетворяющий определен-    | > Все пути от корневого узла до узла 7, |
+---------------+----------------------------------------+-----------------------------------------+
|               | > ным условиям задачи, может быть одно | > удовлетворяющие условиям              |
+---------------+----------------------------------------+-----------------------------------------+
|               | > или несколько решений                |                                         |
+---------------+----------------------------------------+-----------------------------------------+
| > Ограничение | > Ограничение на допустимость реше-    | > Путь не содержит узлов со значением 3 |
+---------------+----------------------------------------+-----------------------------------------+
|               | > ния, обычно используется для обрезки |                                         |
+---------------+----------------------------------------+-----------------------------------------+
| > Состояние   | > Ситуация задачи в определенный мо-   | > Текущий посещенный путь узлов, т. е.  |
+---------------+----------------------------------------+-----------------------------------------+
|               | > мент, включая сделанные выборы       | > список узлов path                     |
+---------------+----------------------------------------+-----------------------------------------+
| > Попытка     | > Процесс исследования пространства    | > Рекурсивный доступ к левому (право-   |
+---------------+----------------------------------------+-----------------------------------------+
|               | > решений на основе доступных вы-      | > му) дочернему узлу, добавление узла   |
+---------------+----------------------------------------+-----------------------------------------+
|               | > боров, включая выбор, обновление     | > в path, проверка значения узла на     |
+---------------+----------------------------------------+-----------------------------------------+
|               | > состояния, проверку на решение       | > равенство 7                           |
+---------------+----------------------------------------+-----------------------------------------+
| > Возврат     | > Отмена предыдущих выборов и воз-     | > При переходе через листовой узел,     |
+---------------+----------------------------------------+-----------------------------------------+
|               | > врат к предыдущему состоянию при     | > завершении посещения узла, встрече    |
+---------------+----------------------------------------+-----------------------------------------+
|               | > встрече состояния, не удовлетворяю-  | > узла со значением 3 поиск прекраща-   |
+---------------+----------------------------------------+-----------------------------------------+
|               | > щего ограничению                     | > ется, происходит выход из функции     |
+---------------+----------------------------------------+-----------------------------------------+
| > Обрезка     | > Метод избегания бессмысленных путей  | > При встрече узла со значением 3 по-   |
+---------------+----------------------------------------+-----------------------------------------+
|               | > поиска на основе условий и ограниче- | > иск прекращается                      |
+---------------+----------------------------------------+-----------------------------------------+
|               | > ний задачи, повышающий эффектив-     |                                         |
+---------------+----------------------------------------+-----------------------------------------+
|               | > ность поиска                         |                                         |
+---------------+----------------------------------------+-----------------------------------------+

### Преимущества и ограничения

> Алгоритм поиска с возвратом, по сути, является алгоритмом поиска в глуби- ну, который пытается найти все возможные решения до тех пор, пока не будет найдено решение, удовлетворяющее условиям. Преимущество этого метода заключается в возможности нахождения всех возможных решений, и при раз- умной обрезке он обладает высокой эффективностью.
>
> Однако при решении крупных или сложных задач **эффективность работы алгоритма возврата может оказаться неприемлемой.**

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

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

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

- **Обрезка**: избегание поиска по путям, которые заведомо не приведут к решению, что позволяет сэкономить время и пространство.

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

### Типичные задачи поиска с возвратом

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

- Задача о перестановках: дано множество, требуется найти все возмож- ные перестановки элементов.

- Задача о сумме подмножеств: дано множество и целевая сумма, необхо- димо найти все подмножества, сумма которых равна целевой.

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

> **Задачи с ограничениями**: цель этих задач -- найти решение, удовлетворя- ющее всем ограничениям.

- Задача об *n* ферзях: разместить *n* ферзей на шахматной доске размером

> *n*×*n* так, чтобы они не рубили друг друга.

- Судоку: заполнить числами от 1 до 9 сетку 9×9 так, чтобы в каждой стро- ке, каждом столбце и каждой подгруппе 3×3 числа не повторялись.

- Задача о раскраске графа: дан неориентированный граф, требуется рас- красить его вершины минимальным числом цветов так, чтобы соседние вершины имели разные цвета.

> **Задачи комбинаторной оптимизации**: цель этих задач -- найти опти- мальное решение в комбинаторном пространстве, удовлетворяющее опреде- ленным условиям.

- Задача о рюкзаке 0-1: дано множество предметов и рюкзак. Каждый предмет имеет определенную ценность и вес, требуется выбрать пред- меты так, чтобы их общая ценность была максимальной при ограничен- ной вместимости рюкзака.

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

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

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

- Задача о рюкзаке 0-1 обычно решается с помощью динамического программирования для достижения более высокой временной эффек- тивности.

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

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

#### задача о перестановках

> Задача о перестановках является типичным примером применения алгорит- ма поиска с возвратом. Она определяется как задача нахождения всех воз- можных перестановок элементов в заданном множестве (например, массиве или строке).
>
> В табл. 13.2 представлено несколько примеров данных, включая входной массив и все соответствующие перестановки.
>
> **Таблица 13.2.** Примеры полных перестановок

+----------------------+--------------------------------------------------------------------------------+
| > **Входной массив** | > **Все перестановки**                                                         |
+======================+================================================================================+
| > \[1\]              | > \[1\]                                                                        |
+----------------------+--------------------------------------------------------------------------------+
| > \[1, 2\]           | > \[1, 2\], \[2, 1\]                                                           |
+----------------------+--------------------------------------------------------------------------------+
| > \[1, 2, 3\]        | > \[1, 2, 3\], \[1, 3, 2\], \[2, 1, 3\], \[2, 3, 1\], \[3, 1, 2\], \[3, 2, 1\] |
+----------------------+--------------------------------------------------------------------------------+

### Случай без равных элементов

> С точки зрения алгоритма поиска с возвратом **процесс генерации пере- становок можно представить как результат серии выборов**. Предполо- жим, что входной массив равен \[1, 2, 3\]. Если сначала выбрать 1, затем 3, а в
>
> конце 2, то получится перестановка \[1, 3, 2\]. Возврат означает отмену выбора и продолжение попыток других вариантов.
>
> С точки зрения кода реализации поиска с возвратом множество кандидатов
>
> choices -- это все элементы входного массива, а состояние state -- это элементы,
>
> выбранные до текущего момента. Следует отметить, что каждый элемент мо- жет быть выбран только один раз, **поэтому все элементы в** state **должны быть уникальными**.
>
> Процесс поиска можно развернуть в виде рекурсивного дерева, в котором каждый узел представляет текущее состояние state, как показано на рис. 13.5. Начиная с корневого узла, после трех раундов выбора достигается листовой узел, а каждый листовой узел соответствует одной перестановке.

![](ru/docs/assets/media/image810.jpeg)

> **Рис. 13.5.** Рекурсивное дерево полных перестановок

##### Обрезка повторного выбора

> Чтобы обеспечить выбор каждого элемента только один раз, вводится булев массив selected, где selected\[i\] указывает, был ли выбран элемент choices\[i\], и на его основе выполняется следующая обрезка.

- После выбора choice\[i\] значение selected\[i\] устанавливается в True, т. е. элемент помечается как выбранный.

- При обходе списка выбора choices пропускаются все уже выбранные узлы, т. е. выполняется обрезка.

> Предположим, что в первом раунде выбирается 1, во втором -- 3, а в тре- тьем -- 2, тогда во втором раунде необходимо обрезать ветвь элемента 1, а в третьем -- ветви элементов 1 и 3, как показано на рис. 13.6.
>
> Из рис. 13.6 видно, что это отсечение уменьшает размер пространства поис- ка с *O*(*nn*) до *O*(*n*!).
>
> ![](ru/docs/assets/media/image812.jpeg)
>
> **Рис. 13.6.** Пример обрезки в задаче полных перестановок

##### Код реализации

> На основе вышеизложенное можно заполнить пробелы в каркасе кода. Чтобы сократить код, функции каркаса кода не реализуются отдельно, а объединены в функцию backtrack().
>
> \# === File: permutations_i.py === def backtrack(
>
> state: list\[int\], choices: list\[int\], selected: list\[bool\], res:
>
> list\[list\[int\]\]
>
> ):
>
> \"\"\" Поиск с возвратом: полные перестановки I.\"\"\"
>
> \# Когда длина состояния равна количеству элементов, фиксируется решение. if len(state) == len(choices):
>
> res.append(list(state)) return
>
> \# Обход всех выборов.
>
> for i, choice in enumerate(choices):
>
> \# Обрезка: не допускается повторный выбор элементов. if not selected\[i\]:
>
> \# Попытка: сделать выбор, обновить состояние. selected\[i\] = True
>
> state.append(choice)
>
> \# Переход к следующему выбору. backtrack(state, choices, selected, res)
>
> \# Возврат: отмена выбора, восстановление предыдущего состояния. selected\[i\] = False
>
> state.pop()
>
> def permutations_i(nums: list\[int\]) -\> list\[list\[int\]\]: \"\"\" Полные перестановки.\"\"\"
>
> res = \[\]
>
> backtrack(state=\[\], choices=nums, selected=\[False\] \* len(nums), res=res) return res

### Учет равных элементов

> Предположим, что входной массив равен \[1, 1, 2\]. Для удобства различения двух повторяющихся элементов 1 второй 1 обозначим как 1\^.
>
> Как видно на рис. 13.7, половина перестановок, сгенерированных вышеука- занным методом, являются одинаковыми.

![](ru/docs/assets/media/image814.jpeg)

> **Рис. 13.7.** Повторяющиеся перестановки
>
> Как же избавиться от повторяющихся перестановок? Самый прямой спо- соб -- использовать хеш-набор для удаления дубликатов из результата пере- становок. Однако это не самый изящный подход, **так как ветви поиска, гене- рирующие повторяющиеся перестановки**, **излишни**, **и их нужно заранее распознавать и обрезать** -- это повысит эффективность алгоритма.

##### Обрезка равных элементов

> В первом раунде выбор 1 или 1\^ эквивалентен, так как все перестановки, сге- нерированные под этими двумя выборами, повторяются, как показано на рис. 13.8. Поэтому элемент 1\^ нужно обрезать.
>
> Аналогично после выбора 2 в первом раунде выбор 1 и 1\^ во втором раун- де также создадут повторяющиеся ветви, поэтому 1\^ во втором раунде также нужно обрезать.

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

![](ru/docs/assets/media/image816.jpeg)

> **Рис. 13.8.** Обрезка повторяющихся перестановок

##### Код реализации

> Возьмем за основу код из предыдущей задачи. В каждом раунде выбора вве- дем хеш-набор duplicated, который будет использоваться для записи элемен- тов, уже проверенных в этом раунде, и для обрезки повторяющихся элементов.
>
> \# === File: permutations_ii.py === def backtrack(
>
> state: list\[int\], choices: list\[int\], selected: list\[bool\], res: list\[list\[int\]\]
>
> ):
>
> \"\"\" Поиск с возвратом: полные перестановки II.\"\"\"
>
> \# Когда длина состояния равна количеству элементов, решение фиксируется. if len(state) == len(choices):
>
> res.append(list(state)) return
>
> \# Обход всех выборов. duplicated = set\[int\]()
>
> for i, choice in enumerate(choices):
>
> \# Обрезка: не допускается повторный выбор элементов и выбор равных элементов if not selected\[i\] and choice not in duplicated:
>
> \# Попытка: сделать выбор, обновить состояние. duplicated.add(choice) \# Запись выбранного значения элемента.
>
> selected\[i\] = True state.append(choice)
>
> \# Переход к следующему выбору. backtrack(state, choices, selected, res)
>
> \# Возврат: отмена выбора, восстановление предыдущего состояния. selected\[i\] = False
>
> state.pop()
>
> def permutations_ii(nums: list\[int\]) -\> list\[list\[int\]\]: \"\"\" Полные перестановки II.\"\"\"
>
> res = \[\]
>
> backtrack(state=\[\], choices=nums, selected=\[False\] \* len(nums), res=res) return res
>
> Предположим, что элементы попарно различны, тогда *n* элементов имеют *n*! перестановок (факториал). При записи результата необходимо скопировать список длиной *n* за время *O*(*n*). Таким образом, **временная сложность со- ставляет** *O*(*n*!*n*).
>
> Максимальная глубина рекурсии равна *n*, используется *O*(*n*) пространства стека вызовов. Для selected требуется *O*(*n*) пространства. В любой момент времени в duplicated может содержаться максимум *n* элементов, что соответ- ствует *O*(*n*2) пространства. Таким образом, **пространственная сложность составляет** *O*(*n*2).

##### Сравнение двух видов обрезки

> Обратите внимание, что, хотя и selected, и duplicated используются для обрез- ки, их цели различны.

- **Обрезка повторного выбора**: в процессе всего поиска существует только один массив selected. В нем фиксируется элементы, включен- ные в текущее состояние, а его цель -- избежать повторного появления элемента в state.

- **Обрезка равных элементов**: каждый раунд выбора (каждый вызов функции backtrack) включает один хеш-набор duplicated. Он фиксирует, какие элементы были выбраны в текущем обходе (цикл for), а его цель -- гарантировать, что равные элементы выбираются только один раз.

> На рис. 13.9 демонстрируется область действия двух условий обрезки. Об- ратите внимание, что каждый узел в дереве представляет собой выбор, а узлы на пути от корня до листа составляют одну перестановку.
>
> ![](ru/docs/assets/media/image818.jpeg)
>
> **Рис. 13.9.** Область действия двух условий обрезки

1.  **задача о сумме подмножеств**

### Случай без повторяющихся элементов

> Например, для входного множества {3, 4, 5} и целевого числа 9 решениями
>
> будут {3, 3, 3}, {4, 5}. Следует обратить внимание на следующие два момента:

- элементы входного множества можно выбирать неограниченное коли- чество раз;

- порядок элементов в подмножестве не имеет значения, например {4, 5} и {5, 4} -- одно и то же подмножество.

##### Сравнение с решением задачи о полных перестановках

> Подобно задаче о полных перестановках, процесс генерации подмножеств можно представить как серию выборов, а в процессе выбора в реальном вре- мени обновлять сумму элементов. Когда сумма элементов равна target, под- множество записывается в список результатов.
>
> Однако, в отличие от задачи о полных перестановках, **в данной задаче элементы множества можно выбирать неограниченное количество раз**,
>
> поэтому нет необходимости использовать булев список selected для записи выбранных элементов. Для получения начального решения можно просто не- много изменить код для полных перестановок.
>
> \# === File: subset_sum_i_naive.py === def backtrack(
>
> state: list\[int\], target: int, total: int,
>
> choices: list\[int\], res: list\[list\[int\]\],
>
> ):
>
> \"\"\" Поиск с возвратом: сумма подмножеств I.\"\"\"
>
> \# Если сумма подмножества равна target, записать решение. if total == target:
>
> res.append(list(state)) return
>
> \# Перебор всех вариантов выбора. for i in range(len(choices)):
>
> \# Обрезка: если сумма подмножества превышает target, пропустить этот выбор. if total + choices\[i\] \> target:
>
> continue
>
> \# Попытка: сделать выбор, обновить сумму элементов total. state.append(choices\[i\])
>
> \# Переход к следующему выбору.
>
> backtrack(state, target, total + choices\[i\], choices, res)
>
> \# Возврат: отмена выбора, восстановление предыдущего состояния. state.pop()
>
> def subset_sum_i_naive(nums: list\[int\], target: int) -\> list\[list\[int\]\]: \"\"\" Решение задачи о сумме подмножеств I (включая повторяющиеся
>
> подмножества).\"\"\"
>
> state = \[\] \# Состояние (подмножество). total = 0 \# Сумма подмножества.
>
> res = \[\] \# Список результатов (список подмножеств). backtrack(state, target, total, nums, res)
>
> return res
>
> При вводе в этот код массива \[3, 4, 5\] и целевого элемента 9 будет выведено \[3, 3, 3\], \[4, 5\], \[5, 4\]. **Хотя удалось найти все подмножества с суммой 9**, **среди**
>
> **них есть повторяющиеся подмножества** \[4, 5\] **и** \[5, 4\].
>
> Это происходит потому, что процесс поиска различает порядок выбора, тогда как в подмножествах порядок элементов не важен. Как показано на рис. 13.10, сначала выбрать 4, а затем 5 и сначала выбрать 5, а затем 4 -- это разные ветви, но они соответствуют одному и тому же подмножеству.
>
> ![](ru/docs/assets/media/image820.jpeg)
>
> **Рис. 13.10.** Поиск подмножеств и обрезка по превышению целевого значения
>
> **Одним из очевидных подходов к устранению повторяющихся подмно- жеств является удаление дубликатов из списка результатов**. Однако этот метод очень неэффективен по двум причинам.

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

- Сравнение подмножеств (массивов) на различия очень затратная по вре- мени операция. Она требует сначала сортировки массивов, затем срав- нения различий каждого элемента в массиве.

##### Обрезка повторяющихся подмножеств

> Рассмотрим устранение дубликатов в процессе поиска с помощью обрез- ки. На рис. 13.11 показано, что повторяющиеся подмножества возникают при выборе элементов массива в разном порядке, например в следующих случаях:

1)  пусть на первом и втором этапах выбираются 3 и 4 соответственно, соз- даются все подмножества, содержащие эти два элемента, обозначенные как \[3, 4, ...\];

2)  затем если на первом этапе выбирается 4, **то на втором этапе следует пропустить** 3, так как подмножество \[4, 3, ...\] полностью повторяет под- множество, созданное на этапе 1.

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

1.  На первых двух этапах выбираются 3 и 5 и создаются подмножества \[3, 5, ...\].

2.  На первых двух этапах выбираются 4 и 5 и создаются подмножества \[4, 5, ...\].

3.  Если на первом этапе выбирается 5, **то на втором этапе следует про- пустить** 3 **и** 4, так как подмножества \[5, 3, ...\] и \[5, 4, ...\] полностью повто- ряют подмножества, описанные на этапах 1 и 2.

![](ru/docs/assets/media/image822.jpeg)

> **Рис. 13.11.** Повторяющиеся подмножества, полученные в результате различного порядка выбора
>
> Обобщим эту мысль. Пусть задан входной массив \[*x*1, *x*2, ..., *xn*\]. Тогда в про- цессе поиска последовательность выбора \[*xi*1, *xi*2, ..., *xim*\] должна удовлетво- рять условию *i*1 ≤ *i*2 ≤ ⋯ ≤ *im*, **в противном случае она приведет к дубликатам, и ее нужно обрезать**.

##### Код реализации

> Для реализации этой обрезки мы инициализируем переменную start, которая указывает начальную точку обхода. **После выбора** *xi* **следующая итерация начинается с индекса** *i*. Это позволяет для последовательности выбора со- блюдать условие *i*1 ≤ *i*2 ≤ ⋯ ≤ *im*, обеспечивая уникальность подмножеств.
>
> Кроме того, в код были внесены следующие две оптимизации.

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

- Исключение переменной total, подсчет суммы элементов осуществля- ется с помощью вычитания из target. Решение фиксируется, когда target равен 0.

> \# === File: subset_sum_i.py ===
>
> def backtrack(
>
> state: list\[int\], target: int, choices: list\[int\], start: int, res: list\[list\[int\]\]
>
> ):
>
> \"\"\" Поиск с возвратом: сумма подмножеств I\"\"\"
>
> \# При равенстве суммы подмножества target фиксируется решение. if target == 0:
>
> res.append(list(state)) return
>
> \# Обход всех вариантов.
>
> \# Обрезка 2: обход начинается с start, чтобы избежать создания \# повторяющихся подмножеств.
>
> for i in range(start, len(choices)):
>
> \# Обрезка 1: если сумма подмножества превышает target, цикл завершается. \# Это связано с тем, что массив отсортирован, последующие элементы
>
> \# больше, и сумма подмножества обязательно превысит target. if target - choices\[i\] \< 0:
>
> break
>
> \# Попытка: выбор, обновление target, start. state.append(choices\[i\])
>
> \# Переход к следующему выбору.
>
> backtrack(state, target - choices\[i\], choices, i, res)
>
> \# Возврат: отмена выбора, восстановление предыдущего состояния. state.pop()
>
> def subset_sum_i(nums: list\[int\], target: int) -\> list\[list\[int\]\]: \"\"\" Решение задачи суммы подмножеств I.\"\"\"
>
> state = \[\] \# Состояние (подмножество). nums.sort() \# Сортировка nums.
>
> start = 0 \# Начальная точка обхода.
>
> res = \[\] \# Список результатов (список подмножеств). backtrack(state, target, nums, start, res)
>
> return res
>
> На рис. 13.12 показан полный процесс поиска с возвратом для массива \[3, 4, 5\] и целевого элемента 9.
>
> ![](ru/docs/assets/media/image824.jpeg)
>
> **Рис. 13.12.** Процесс поиска с возвратом для реализации задачи о сумме подмножеств I

### Случай с повторяющимися элементами

> В отличие от предыдущей задачи **входной массив может содержать по- вторяющиеся элементы**, что создает новую проблему. Например, для мас- сива \[4, 4, 5\] и целевого элемента 9, текущий код выдает результат \[4, 5\], \[4, 5\], что приводит к повторяющимся подмножествам.
>
> **Причина этих повторов в том**, **что равные элементы выбираются не- сколько раз на одном этапе**. На рис. 13.13 показано, что на первом этапе есть три варианта выбора, два из которых равны 4. Это приводит к двум повторя- ющимся ветвям поиска и, следовательно, к повторяющимся подмножествам. Аналогично два элемента 4 на втором этапе также создают повторяющиеся подмножества.
>
> ![](ru/docs/assets/media/image826.jpeg)
>
> **Рис. 13.13.** Повторяющиеся подмножества из-за равных элементов

##### Обрезка равных элементов

> Для решения этой проблемы **необходимо сделать выбор равных элементов на каждом этапе однократным**. Реализация этого подхода довольно изящ- на: поскольку массив отсортирован, равные элементы находятся рядом друг с другом. Это означает, что если текущий элемент равен предыдущему, то он уже был выбран, и его следует пропустить.
>
> В то же время **в этой задаче предусмотрено**, **что каждый элемент мас- сива может быть выбран только один раз**. К счастью, можно использовать переменную start для выполнения этого ограничения: после выбора *xi* начи- наем следующий цикл с индекса *i* + 1. Это позволяет исключить повторяющие- ся подмножества и избежать повторного выбора элементов.

##### Код реализации

> \# === File: subset_sum_ii.py === def backtrack(
>
> state: list\[int\], target: int, choices: list\[int\], start: int, res: list\[list\[int\]\]
>
> ):
>
> \"\"\" Поиск с возвратом: сумма подмножеств II.\"\"\"
>
> \# Когда сумма подмножества равна target, фиксируется решение. if target == 0:
>
> res.append(list(state)) return
>
> \# Перебор всех вариантов выбора.
>
> \# Обрезка 2: перебор начинается со start, чтобы избежать создания \# повторяющихся подмножеств.
>
> \# Обрезка 3: перебор начинается со start, чтобы избежать повторного выбора \# одного и того же элемента.
>
> for i in range(start, len(choices)):
>
> \# Обрезка 1: если сумма подмножества превышает target, цикл завершается. \# Это связано с тем, что массив уже отсортирован, и последующие
>
> \# элементы больше, сумма подмножества обязательно превысит target. if target - choices\[i\] \< 0:
>
> break
>
> \# Обрезка 4: если элемент равен левому элементу, значит, эта ветвь \# поиска повторяется, и ее можно пропустить.
>
> if i \> start and choices\[i\] == choices\[i - 1\]:
>
> continue
>
> \# Попытка: сделать выбор, обновить target, start. state.append(choices\[i\])
>
> \# Переход к следующему выбору.
>
> backtrack(state, target - choices\[i\], choices, i + 1, res)
>
> \# Возврат: отмена выбора, восстановление предыдущего состояния. state.pop()
>
> def subset_sum_ii(nums: list\[int\], target: int) -\> list\[list\[int\]\]: \"\"\" Решение задачи суммы подмножеств II.\"\"\"
>
> state = \[\] \# Состояние (подмножество).
>
> nums.sort() \# Сортировка nums.
>
> start = 0 \# Начальная точка перебора.
>
> res = \[\] \# Список результатов (список подмножеств). backtrack(state, target, nums, start, res)
>
> return res
>
> На рис. 13.14 демонстрируется процесс обратного отслеживания для масси- ва \[4, 4, 5\] и целевого элемента 9, включающий четыре вида обрезки. Проана- лизируйте рисунок и комментарии в коде, чтобы лучше понять весь процесс поиска и как работают различные операции обрезки.
>
> ![](ru/docs/assets/media/image828.jpeg)*1-й раунд выбора*
>
> *2-й раунд выбора*
>
> **Обрезка 4**
>
> *В одном раунде равные элементы можно выбирать только один раз*
>
> **Обрезка 2**
>
> *Не допускать создания повторяющихся подмножеств*
>
> **Обрезка 1**
>
> *Сумма элементов*
>
> *не может превышать*
>
> **target**
>
> **Рис. 13.14.** Процесс поиска с возвратом для реализации задачи о сумме подмножеств II

1.  **задача об n ферзях**

> Для *n* = 4 можно найти два решения, которые изображены на рис. 13.15. С точки зрения алгоритма поиска с возвратом шахматная доска размером *n*×*n* имеет *n*2 клеток, которые предоставляют собой все варианты выбора. В про- цессе размещения ферзей состояние доски постоянно меняется, и в каждый момент времени доска имеет состояние state.

![](ru/docs/assets/media/image829.jpeg){width="3.312998687664042in" height="1.2706244531933508in"}

> **Рис. 13.15.** Решения задачи о 4 ферзях
>
> На рис. 13.16 изображено три условия ограничения для данной задачи: несколько ферзей не могут находиться на одной строке, в одном столбце или на одной диагонали. Стоит отметить, что диагонали делятся на главную диа- гональ \\ и побочную диагональ /.

![](ru/docs/assets/media/image831.jpeg)

> **Рис. 13.16.** Ограничения задачи об n ферзях

##### Стратегия построчного размещения

> Количество ферзей и количество строк на доске равно *n*, поэтому можно сделать вывод: **на каждой строке доски может быть размещен только один ферзь**. Из этого следует, что мы можем использовать стратегию построчного раз- мещения: размещать по одному ферзю на каждой строке, начиная с первой
>
> и заканчивая последней.
>
> На рис. 13.17 изображен процесс построчного размещения для задачи о 4 ферзях. Из-за ограничений на размер изображения, на рис. 13.17 развернута только одна ветвь поиска первой строки, а все решения, не удовлетворяющие ограничениям по столбцам и диагоналям, обрезаны.

![](ru/docs/assets/media/image833.jpeg)

> **Рис. 13.17.** Стратегия построчного размещения
>
> По сути**, стратегия построчного размещения выполняет функцию об- резки**, отсекая все ветви поиска, в которых на одной строке может находиться более одного ферзя.

##### Обрезка по столбцам и диагоналям

> Чтобы выполнить ограничениям по столбцам, можно использовать булев мас- сив cols длиной *n*, в котором будет фиксироваться наличие ферзя в каждом столбце. На его основе перед каждым решением о размещении будут обре- заться столбцы, в которых уже есть ферзь. Состояние cols будет динамически обновляться в процессе возврата.
>
> Как теперь отследить ограничения по диагоналям? Пусть индексы строки и столбца какой-либо клетки на доске равны (row, col). Выбрав определенную главную диагональ в матрице, можно заметить, что разность индексов строки и столбца всех клеток на этой диагонали одинакова, т. е. **для всех клеток на главной диагонали значение** row − col **является постоянной величиной**.
>
> Это означает, что если для двух клеток выполняется условие row1 -- col2 = row2 -- col2, то они находятся на одной главной диагонали. Пользуясь этим пра- вилом, можно с помощью массива diags1 фиксировать наличие ферзя на каж- дой главной диагонали, как показано на рис. 13.18.
>
> Аналогично **сумма** row + col **для всех клеток на побочной диагонали яв- ляется постоянной величиной**. Мы можем использовать еще один массив diags2 для обработки ограничений на побочной диагонали.

![](ru/docs/assets/media/image835.jpeg)

> **Рис. 13.18.** Обработка ограничений по столбцам и диагоналям

##### Код реализации

> Следует отметить, что в *n*-мерной матрице диапазон row -- col составляет \[−*n* + 1, *n* − 1\], а диапазон row + col составляет \[0, 2*n* − 2\], поэтому количество главных и побочных диагоналей равно 2*n* − 1, т. е. длина массивов diags1 и diags2 также равна 2*n* − 1.
>
> \# === File: n_queens.py === def backtrack(
>
> row: int, n: int,
>
> state: list\[list\[str\]\], res: list\[list\[list\[str\]\]\], cols: list\[bool\],
>
> diags1: list\[bool\], diags2: list\[bool\],
>
> ):
>
> \"\"\" Поиск с возвратом: задача об n ферзях.\"\"\"
>
> \# При размещении всех строк фиксируется решение. if row == n:
>
> res.append(\[list(row) for row in state\]) return
>
> \# Перебор всех столбцов. for col in range(n):
>
> \# Вычисление главной и побочной диагоналей для данной клетки. diag1 = row - col + n - 1
>
> diag2 = row + col
>
> \# Обрезка: не допускается наличие ферзя в данном столбце, на главной \# или побочной диагонали.
>
> if not cols\[col\] and not diags1\[diag1\] and not diags2\[diag2\]: \# Попытка: размещение ферзя в данной клетке. state\[row\]\[col\] = \"Q\"
>
> cols\[col\] = diags1\[diag1\] = diags2\[diag2\] = True \# Переход к следующей строке.
>
> backtrack(row + 1, n, state, res, cols, diags1, diags2) \# Возврат: восстановление клетки в пустое состояние. state\[row\]\[col\] = \"#\"
>
> cols\[col\] = diags1\[diag1\] = diags2\[diag2\] = False
>
> def n_queens(n: int) -\> list\[list\[list\[str\]\]\]: \"\"\" Решение задачи об n ферзях.\"\"\"
>
> \# Инициализация шахматной доски размером n\*n, где \'Q\' обозначает ферзя,
>
> \# а \'#\' обозначает пустую клетку.
>
> state = \[\[\"#\" for \_ in range(n)\] for \_ in range(n)\] cols = \[False\] \* n \# Учет наличия ферзя в столбце.
>
> diags1 = \[False\] \* (2 \* n - 1) \# Учет наличия ферзя на главной диагонали. diags2 = \[False\] \* (2 \* n - 1) \# Учет наличия ферзя на побочной диагонали. res = \[\]
>
> backtrack(0, n, state, res, cols, diags1, diags2) return res
>
> Размещение *n* раз по строкам с учетом ограничений по столбцам предпо- лагает, что от первой до последней строки имеется *n*, *n* − 1, \..., 2, 1 вариантов выбора, что требует времени *O*(*n*!). При фиксации решения необходимо копи- ровать матрицу state и добавлять результат в res, что требует времени *O*(*n*2). Таким образом, **общая временная сложность составляет** *O*(*n*! ⋅ *n*2). На прак- тике обрезка по ограничениям диагоналей значительно сокращает простран- ство поиска, поэтому эффективность поиска часто превосходит указанную временную сложность.
>
> Массив state использует *O*(*n*2) пространства, массивы cols, diags1 и diags2 ис- пользуют *O*(*n*) пространства. Максимальная глубина рекурсии составляет *n*, что требует *O*(*n*) пространства стека. Следовательно, **пространственная слож- ность равна** *O*(*n*2).

1.  Резюме ❖ **395**

> **13.5. резюме**

##### Ключевые моменты

- Алгоритм поиска с возвратом по сути является методом полного пере- бора, который ищет подходящие решения путем обхода в глубину про- странства решений. В процессе поиска фиксируются удовлетворяющие условиям решения до тех пор, пока не будут найдены все решения или обход не будет завершен.

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

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

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

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

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

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

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

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

<!-- -->

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

##### Вопросы и ответы

> **Вопрос**. Какова связь между возвратом и рекурсией?
>
> **Ответ**. В общем, возврат -- это стратегия алгоритма, тогда как рекурсия ско- рее является инструментом.

- Алгоритмы поиска с возвратом обычно реализуются на основе рекурсии. Однако поиск с возвратом -- это один из вариантов применения рекур- сии, а именно применение рекурсии в задачах поиска.

- Структура рекурсии отражает парадигму разбиения на подзадачи и ча- сто используется для решения задач, связанных со стратегией «разделяй и властвуй», поиском с возвратом, динамическим программированием (мемоизация рекурсии) и др.

> Глава 14