09.01.324 Алгоритм backtracking - justjune/AiSD2026 GitHub Wiki
Перебор с возвратом (backtracking) позволяет систематически исследовать все возможные конфигурации области поиска. Эти конфигурации могут представлять все возможные расположения объектов (т. е. перестановки) или все возможные наборы объектов (т. е. подмножества). [Скиена 2022, с. 324]
Метод перебора с возвратом обеспечивает правильность результата, перечисляя все возможные комбинации, а эффективность его обеспечивается тем, что никакое состояние не исследуется более одного раза. [Скиена 2022, с. 326]
Три процедуры, настраивающие каркас перебора с возвратом на генерацию подмножеств и перестановок.
is_a_solution(a, k, input)
Эта булева функция проверяет, составляют ли первые k элементов вектора a полное решение задачи. Последний аргумент — input — позволяет передавать в процедуру общую информацию. Например, с его помощью можно указать значение n, представляющее заданный размер решения. Эта информация может быть полезной при создании перестановок или подмножеств из n элементов, но при создании объектов переменного размера, таких как последовательности ходов игры, можно передавать другие данные, более соответствующие ситуации. [Скиена 2022, с. 326 и с. 327]
is_a_solution(a, k, input)
вход: a[] ──► вектор решения
k ──► сколько позиций уже заполнено
n ──► сколько всего нужно заполнить
вернуть (k == n) ?
│
true false
│ │
решение готово идём глубже
→ process_solution → construct_candidates
construct_candidates(a, k, input, c, &nc)
Эта процедура записывает в массив c полный набор возможных кандидатов на k-ю позицию вектора a при заданном содержимом первых k − 1 позиций. Количество кандидатов, содержащихся в этом массиве, заносится в переменную nc. Так же, как в предыдущей функции, аргумент input можно использовать для передачи в процедуру вспомогательной информации. [Скиена 2022, с. 326 и с. 327]
construct_candidates(a, k, input, c, &nc)
вход: a[] ──► вектор решения
k ──► какая позиция заполняется
n ──► сколько всего нужно заполнить
выход: c[] ──► массив кандидатов
nc ──► сколько кандидатов
записать в c[] все варианты
для позиции k, вернуть nc
│
┌───────────┴───────────┐
подмножества перестановки
│ │
c = {true, false} c = {все ещё не занятые v}
nc = 2 nc = n − (k−1)
process_solution(a, k, input)
Эта процедура выводит, вычисляет, сохраняет или обрабатывает полное решение после его создания. [Скиена 2022, с. 326 и с. 327]
process_solution(a, k, input)
вход: a[] ──► вектор решения
k ──► сколько позиций заполнено
n ──► сколько всего нужно заполнить
вывести / сохранить / посчитать
готовое решение
│
┌───────────┴───────────┐
подмножества перестановки
│ │
вывод {1, 3} вывод (2, 1, 3)
(порядок не важен) (порядок важен)
Что делает backtrack по шагам
backtrack(a, k, n)
1. Проверяет, готово ли решение:
вызвать is_a_solution(a, k, n)
2. Если готово:
вызвать process_solution(a, k, n) ← вывести / сохранить
вернуться
3. Если НЕ готово:
k = k + 1 ← перейти на следующий уровень
вызвать construct_candidates(...) ← получить список вариантов c[]
для каждого кандидата c[i]:
a[k] = c[i] ← сделать выбор
backtrack(a, k, n) ← уйти вглубь (рекурсия)