Перейти к содержанию

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

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

Идея очень проста:

  1. строим решение по частям;
  2. после каждого выбора проверяем, не нарушены ли условия;
  3. если нарушены — возвращаемся назад;
  4. если нет — продолжаем углубляться.

Такой подход перебирает все возможные способы построить ответ, но делает это не «в лоб», а постепенно, с возможностью вовремя откатиться.

Пример: расстановка ферзей

Рассмотрим классическую задачу: нужно посчитать количество способов расставить n ферзей на шахматной доске n × n так, чтобы никакие два ферзя не били друг друга.

Например, при n = 4 существует ровно два корректных расположения.

Вместо того чтобы сразу перебирать все доски целиком, удобнее строить решение по строкам. Мы будем ставить по одному ферзю в каждую строку так, чтобы новый ферзь не конфликтовал с уже поставленными.

Когда мы успешно разместили ферзей во всех n строках, найдено одно полное решение.

Как устроен перебор

Пусть мы уже расставили ферзей в первых нескольких строках. Тогда для следующей строки мы пробуем все столбцы подряд:

  • если клетка безопасна, ставим туда ферзя;
  • рекурсивно переходим к следующей строке;
  • после возврата убираем ферзя и пробуем следующий столбец.

Именно это «поставить → углубиться → убрать» и составляет суть поиска с возвратом.

Небольшой пример

Пусть мы хотим расставить 4 ферзя на доске 4 × 4.

Сначала ставим ферзя в первую строку. Допустим, выбрали столбец 1. Затем переходим ко второй строке и ищем там допустимое место. Если позже окажется, что для какой-то строки свободной клетки уже нет, это значит, что ранее сделанный выбор был неудачным. Тогда мы:

  • возвращаемся на предыдущий шаг;
  • снимаем последнего ферзя;
  • пробуем его поставить в другой столбец.

Например, одна частичная конфигурация может быстро привести к тупику:

  • строка 0 → столбец 1;
  • строка 1 → столбец 3;
  • строка 2 → подходящей клетки нет.

Значит, размещение ферзя во второй строке надо изменить.

А другая конфигурация может успешно продолжаться:

  • строка 0 → столбец 1;
  • строка 1 → столбец 3;
  • строка 2 → столбец 0;
  • строка 3 → столбец 2.

Это уже полное корректное решение.

flowchart TD
    A["Старт"] --> B["Строка 0"]

    B --> C1["Поставить в (0,0)"]
    B --> C2["Поставить в (0,1)"]
    B --> C3["Поставить в (0,2)"]
    B --> C4["Поставить в (0,3)"]

    C1 --> D1["Строка 1: допустимо только (1,2)"]
    D1 --> E1["Строка 2: нет допустимых позиций"]
    E1 --> X1["Откат"]

    C2 --> D2["Строка 1: допустимо только (1,3)"]
    D2 --> E2["Строка 2: допустимо только (2,0)"]
    E2 --> F2["Строка 3: допустимо только (3,2)"]
    F2 --> S1["Решение: [1,3,0,2]"]

    C3 --> D3["Строка 1: допустимо только (1,0)"]
    D3 --> E3["Строка 2: допустимо только (2,3)"]
    E3 --> F3["Строка 3: допустимо только (3,1)"]
    F3 --> S2["Решение: [2,0,3,1]"]

    C4 --> D4["Строка 1: допустимо только (1,1)"]
    D4 --> E4["Строка 2: нет допустимых позиций"]
    E4 --> X2["Откат"]
Hold "Ctrl" to enable pan & zoom

Реализация идеи

Ниже приведён типичный код на C++, реализующий такой перебор:

void search(int y) {
    if (y == n) {
        count++;
        return;
    }

    for (int x = 0; x < n; x++) {
        if (column[x] || diag1[x+y] || diag2[x-y+n-1]) continue;

        column[x] = diag1[x+y] = diag2[x-y+n-1] = 1;
        search(y+1);
        column[x] = diag1[x+y] = diag2[x-y+n-1] = 0;
    }
}

Поиск запускается вызовом:

search(0);

Здесь:

  • y — номер текущей строки;
  • x — столбец, куда мы пытаемся поставить ферзя;
  • count — число найденных решений.

Если y == n, значит, мы уже обработали все строки и получили одну корректную расстановку.

Какие массивы используются

Чтобы быстро проверять, можно ли поставить ферзя в клетку, удобно хранить информацию о занятых направлениях:

  • column[x] — занят ли столбец x;
  • diag1[x+y] — занята ли диагональ вида «слева сверху → справа снизу»;
  • diag2[x-y+n-1] — занята ли диагональ вида «справа сверху → слева снизу».

Почему именно такие индексы?

Столбцы

Со столбцами всё просто: если в столбце уже стоит ферзь, второй туда ставить нельзя.

Главные диагонали

Для клеток одной диагонали сумма x + y одинакова.

Например, на доске 4 × 4:

  • (0,0) и (1,1) и (2,2) и (3,3) лежат на одной диагонали,
  • для них x + y равно 0, 2, 4, 6 в зависимости от клетки,
  • а клетки с одинаковой суммой принадлежат одной и той же диагонали этого направления.

Побочные диагонали

Для другой диагонали одинаковой является разность x - y.

Но разность может быть отрицательной, поэтому к ней добавляют n - 1, чтобы индекс стал неотрицательным:

x - y + n - 1

Это позволяет хранить информацию в обычном массиве.

Почему алгоритм корректен

Алгоритм перебирает все способы поставить по одному ферзю в каждую строку. При этом он сразу отбрасывает варианты, где новый ферзь бьёт уже поставленного.

Значит:

  • ни одно корректное решение не будет пропущено;
  • ни одна некорректная конфигурация не будет засчитана как ответ.

Следовательно, итоговое значение count действительно равно числу всех допустимых расстановок.

Оценка сложности

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

Например:

  • для 8 × 8 существует 92 решения;
  • для 16 × 16 число решений уже равно 14772512.

Поэтому даже хороший backtracking быстро начинает тормозить при росте n.

Главная мысль раздела

Поиск с возвратом полезен в задачах, где:

  • решение строится по шагам;
  • на каждом шаге можно проверить корректность частичного ответа;
  • нужно перебрать все допустимые варианты или посчитать их количество.

Этот подход особенно удобен, когда решение можно описать как последовательность выборов: выбрать столбец, выбрать вершину, выбрать число, выбрать следующий ход и так далее.

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

По итогу что ?

  • Backtracking строит решение постепенно.
  • После каждого шага алгоритм проверяет, не испорчена ли конфигурация.
  • Если продолжать нельзя, выполняется откат.
  • Для задачи о ферзях удобно идти по строкам и хранить занятые столбцы и диагонали.
  • Метод гарантирует правильный ответ, но может быть медленным при больших размерах входа.

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