Алгоритм поиска с возвратом - это действительно крутая техника для решения каких-то головоломок, таких как проблема N королевы, задача судоку.
Этот пост представляет собой основу или план для решения подобных проблем.
Введение
Отслеживание с возвратом - это общий алгоритм поиска решений некоторых вычислительных проблем.
Он постепенно создает кандидатов для решений и отбрасывает каждого частичного кандидата, как только определяет, что кандидат не может быть завершен.
Подобно алгоритму грубой силы, алгоритм поиска с возвратом по существу исследует все решения. Однако при отслеживании с возвратом мы прекращаем оценку возможности, как только она нарушает какое-либо ограничение, предусмотренное в задаче. Этот механизм делает его более эффективным, чем алгоритм грубой силы.
Отслеживание с возвратом Blueprint
Проблемы, связанные с возвратом, иногда бывают очень сложными. Так что Blueprint помогает.
- Алгоритм поиска с возвратом - это алгоритм на основе логических значений.
- Сначала есть набор вариантов, после того, как вы сделали выбор, следует новый набор вариантов.
- Как сделать возврат? мы отменяем определенные присвоения значений переменным, чтобы переназначить их другим возможным значениям, чтобы посмотреть, приводят ли они к правильному решению.
это похоже на поиск в глубину (DFS) с добавленным ограничением: мы прекращаем исследование поддерева, как только мы точно знаем, что это не приведет к правильному решению.
Концептуально мы начинаем с корня дерева, доступные варианты представлены узлом дерева. Мы стремимся получить хороший лист или несколько хороших листьев.
Пояснение к примеру:
- Начиная с корня, мы выбираем A и B.
- Сначала мы выбираем A, затем доступны варианты C и D.
- После того, как мы выберем C, в C. больше нет доступных вариантов, поэтому мы отменяем действие выбора C и возвращаемся к A.
- В A, потому что мы уже пробовали C, и это не удалось. Попробуйте на этот раз D.
- В D у нас нет доступных вариантов, а D - это плохо. Итак, мы отменяем действие выбора D и возвращаемся к A.
- В A у нас не остается выбора (и C, и C - плохой выбор). Так что вернитесь в корень.
- В Root мы уже попробовали A. Сделайте следующий выбор: B.
- В B доступны варианты E и F. Попробуйте E.
- E хорошо, закончено, если мы хотим получить хороший лист
- Если мы хотим получить несколько листьев, вернитесь к B от E
- Выберите F в качестве следующего варианта, F - плохо
- вернуться к B из F снова
- Закончите поиски!
Проблемы
Теперь давайте воспользуемся планом для решения настоящих проблем.
1. Проблема перестановок
Учитывая массив nums различных целых чисел, верните все возможные перестановки. Вы можете вернуть ответ в любом порядке.
Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
2. Проблема подмножеств (проблема комбинации)
Учитывая целочисленный массив nums из уникальных элементов, верните все возможные подмножества (набор мощности).
Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
3. Поиск слова
Учитывая m x n board и word, найдите, существует ли слово в сетке.
Слово может быть составлено из букв последовательно соседних ячеек, где «соседние» ячейки соседствуют по горизонтали или вертикали. Одна и та же буквенная ячейка не может использоваться более одного раза.
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" Output: true
4. Создайте круглые скобки.
Учитывая n пар круглых скобок, напишите функцию для генерации всех комбинаций правильно сформированных скобок.
Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"]
