hello-algo/ru/docs/chapter_backtracking/summary.md

Резюме

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

• Алгоритм поиска с возвратом по своей сути является методом полного перебора, который ищет решения, удовлетворяющие условиям, путем обхода пространства решений в глубину. В процессе поиска при обнаружении решения, удовлетворяющего условиям, оно записывается, и процесс продолжается до тех пор, пока не будут найдены все решения или не завершится обход.
• Процесс поиска алгоритма с возвратом включает две части: попытку и возврат. Он пробует различные варианты с помощью поиска в глубину, и когда встречается ситуация, не удовлетворяющая ограничениям, отменяет предыдущий выбор, возвращается к предыдущему состоянию и продолжает пробовать другие варианты. Попытка и возврат -- это два противоположных действия.
• Задачи поиска с возвратом обычно содержат несколько ограничений, которые можно использовать для реализации операции обрезки. Обрезка позволяет заранее завершить ненужные ветви поиска, значительно повышая эффективность поиска.
• Алгоритм поиска с возвратом в основном применяется для решения задач поиска и задач удовлетворения ограничений. Хотя задачи комбинаторной оптимизации можно решать с помощью алгоритма поиска с возвратом, часто существуют более эффективные или лучшие методы решения.
• Задача полной перестановки направлена на поиск всех возможных перестановок элементов заданного множества. Мы используем массив для записи того, был ли выбран каждый элемент, обрезая ветви поиска с повторным выбором одного и того же элемента, гарантируя, что каждый элемент выбирается только один раз.
• В задаче полной перестановки, если в множестве есть повторяющиеся элементы, в конечном результате появятся повторяющиеся перестановки. Нам нужно ограничить выбор одинаковых элементов в каждом раунде только один раз, что обычно реализуется с помощью хеш-множества.
• Цель задачи о сумме подмножеств -- найти все подмножества в заданном множестве, сумма которых равна целевому значению. Множество не различает порядок элементов, но процесс поиска выводит результаты во всех порядках, создавая повторяющиеся подмножества. Мы сортируем данные перед поиском с возвратом и устанавливаем переменную для указания начальной точки обхода в каждом раунде, тем самым обрезая ветви поиска, генерирующие повторяющиеся подмножества.
• Для задачи о сумме подмножеств одинаковые элементы в массиве создают повторяющиеся множества. Мы используем предварительное условие отсортированного массива, проверяя равенство соседних элементов для реализации обрезки, тем самым гарантируя, что одинаковые элементы могут быть выбраны только один раз в каждом раунде.
• Задача о n ферзях направлена на поиск способов размещения n ферзей на доске размером n \times n так, чтобы все ферзи не могли атаковать друг друга. Ограничения этой задачи включают ограничения по строкам, столбцам, главной диагонали и побочной диагонали. Для удовлетворения ограничения по строкам мы используем стратегию размещения по строкам, гарантируя размещение одного ферзя в каждой строке.
• Обработка ограничений по столбцам и диагоналям аналогична. Для ограничения по столбцам мы используем массив для записи наличия ферзя в каждом столбце, тем самым указывая, является ли выбранная клетка допустимой. Для ограничения по диагоналям мы используем два массива для записи наличия ферзя на главной и побочной диагоналях соответственно; сложность заключается в нахождении закономерности индексов строк и столбцов для клеток, находящихся на одной главной (побочной) диагонали.

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

В: Как понять связь между поиском с возвратом и рекурсией?

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

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