pattern heroPT–23LeetCode Extension

Поиск с возвратом (backtracking)

Строим ответ по одному выбору, а как только выбор ведёт в тупик, отменяем его и пробуем следующий. Перебираем все варианты, но ветки, которые точно не подойдут, отрезаем сразу.

Вариант
P20 Поиск с возвратом (backtracking)Подмножества · 1×

Пример задачи: все подмножества [1, 2, 3].

[ ]1[ ]1,212[ ]1,2,31,21,312,323[ ]путь—результаты—
ещё не былипо пути сюдаэтот шагсохранённое подмножествозавершено или отменено

Ищем все подмножества [1, 2, 3]

i = –path = –results = –
01/57
сначала · назад · пуск · шаг
Скорость
1function explore(i):
2 if i == len(nums):
3 add copy of path to results
4 return
5 add nums[i] to path // choose
6 explore(i + 1) // with it
7 remove last from path // un-choose
8 explore(i + 1) // without it
9
10function subsets(nums):
11 path = []
12 results = []
13 explore(0)
14 return results

← → шаг · пробел — пауза

Как узнать

перечислить все подмножества, перестановки или сочетания, или расставить что-то по правилам (ферзи, судоку); ввод маленький, часто n ≤ 20.

Как решать такие задачи

  1. Определи состояние: что уже выбрано и что осталось решить.
  2. Перечисли варианты на каждом шаге. Отбрось те, что нарушают правила.
  3. Для каждого варианта: выбери его, иди глубже, потом отмени выбор.
  4. Когда решать больше нечего, сохрани копию пути.

Вариант: Перестановки

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

  1. Держи рядом с path массив used: used[i] равен true, пока nums[i] стоит в path.
  2. В каждом вызове пробуй каждый индекс, у которого used — false: отметь его и добавь число, иди глубже, потом убери число и сними отметку.
  3. Когда в path все n чисел, сохрани копию.
  4. В сочетаниях порядок не важен: передавай начальный индекс и пробуй только с него и дальше (Combinations, Combination Sum).
  5. Отрезай ветку, как только счётчик говорит, что она не сработает: ")" не больше, чем "(" (Generate Parentheses), один ферзь на строку, столбец и диагональ (N-Queens).

Вариант: Путь по сетке

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

  1. Запускай поиск из каждой клетки с первой буквой.
  2. В вызове: если это последняя буква, верни true. Иначе пометь клетку (замени её на # или храни множество занятых).
  3. Перебери четырёх соседей: иди глубже только в того, где стоит следующая буква. Если вызов ниже вернул true, сразу верни true.
  4. Если ни один сосед не подошёл, сними пометку и верни false, чтобы клетку могли взять другие пути.
  5. Если слов много, ищи по префиксному дереву (trie) этих слов: один обход сетки ведёт сразу все слова с текущим префиксом (Word Search II).

Где встречается

  • Регулярные выражения. Движки регулярных выражений в Python, Perl и PCRE пробуют один вариант совпадения, а если дальше не сходится, откатываются и пробуют следующий. Поэтому неудачное выражение может работать очень долго.
  • Установка пакетов. dnf и zypper подбирают версии пакетов SAT-решателем (libsolv): он выбирает версию, а при конфликте отменяет выбор и пробует другую.
  • Пролог. Программа на Прологе сама перебирает варианты с возвратом: если правило не сработало, исполнитель возвращается к последнему выбору и пробует следующий вариант.