Skip to content

🔙 Backtracking (Търсене с връщане)

📚 Въведение

Backtracking е алгоритмична техника за решаване на задачи чрез пълно изчерпване (brute-force), която изгражда решението стъпка по стъпка и се "връща назад" (backtracks), веднага щом установи, че текущият път не води до валидно решение.

Думата "backtrack" означава "връщане назад по следите". Представете си, че сте в лабиринт - вървите напред, докато не стигнете до задънена улица, тогава се връщате назад до последното разклонение и опитвате друг път. Това е същността на backtracking.

Техниката е особено мощна за задачи, където трябва да намерим всички възможни решения или да проверим дали съществува решение, удовлетворяващо определени ограничения.

1. Обща схема

Backtracking е по същество Дълбоко Обхождане (DFS) в дървото на състоянията. Всяко състояние представлява частично решение, а преходите между състоянията са валидни ходове.

1.1. Базов шаблон

void backtrack(State current) {
    if (isSolution(current)) {
        printSolution(current);
        return;
    }

    for (Option opt : getOptions(current)) {
        if (isValid(current, opt)) {
            makeMove(current, opt); // Напред
            backtrack(current);     // Рекурсия
            undoMove(current, opt); // Назад (Backtrack)
        }
    }
}

1.2. Ключови компоненти

Състояние (State): Представя текущата конфигурация на проблема. Може да включва: - Частично решение - Използвани ресурси - Текуща позиция в дърото на решенията

Валидиране (isValid): Проверява дали даден ход е допустим при текущото състояние. Това е критично за ефективността - колкото по-рано откажем невалидни пътища, толкова по-бързо ще работи алгоритъмът.

Решение (isSolution): Определя дали сме стигнали до валидно решение на проблема.

Ходове (makeMove/undoMove): Прилагат и отменят промени в състоянието. Важно е undoMove да възстановява състоянието точно както е било преди makeMove.

2. Класически примери

2.1. Генериране на пермутации

Да се намерят всички наредби на числата от 1 до N.

int n;
vector<int> p;
bool used[20];

void permutations() {
    if (p.size() == n) {
        for (int x : p) cout << x << " ";
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            used[i] = true;
            p.push_back(i);
            permutations();
            p.pop_back(); // Backtrack
            used[i] = false;
        }
    }
}

2.2. Задачата за N-те царици

Да се разположат \(N\) царици на дъска \(N \times N\), така че да не се бият. * Използваме масиви col, diag1, diag2, за да следим заетите линии за \(O(1)\). * diag1: \(row + col = const\) * diag2: \(row - col + N = const\)

int n, ans = 0;
bool col[20], d1[40], d2[40];

void solve(int r) {
    if (r == n) {
        ans++;
        return;
    }
    for (int c = 0; c < n; c++) {
        if (!col[c] && !d1[r + c] && !d2[r - c + n]) {
            col[c] = d1[r + c] = d2[r - c + n] = true;
            solve(r + 1);
            col[c] = d1[r + c] = d2[r - c + n] = false; // Backtrack
        }
    }
}

2.3. Генериране на подмножества

За всяка елемент имаме два избора: да го вземем или да не го вземем. Сложност: \(O(2^N)\).

int n;
vector<int> arr;
vector<int> current;

void generateSubsets(int idx) {
    if (idx == n) {
        // Принтираме текущото подмножество
        for (int x : current) {
            cout << x << " ";
        }
        cout << endl;
        return;
    }

    // Включваме arr[idx]
    current.push_back(arr[idx]);
    generateSubsets(idx + 1);
    current.pop_back();  // Backtrack

    // Не включваме arr[idx]
    generateSubsets(idx + 1);
}

2.4. Sudoku решател

Запълване на 9×9 дъска със цифри от 1 до 9, така че в всеки ред, колона и 3×3 квадрат да няма повторения.

bool isValid(int board[9][9], int row, int col, int num) {
    // Проверка на реда
    for (int c = 0; c < 9; c++) {
        if (board[row][c] == num) return false;
    }

    // Проверка на колоната
    for (int r = 0; r < 9; r++) {
        if (board[r][col] == num) return false;
    }

    // Проверка на 3×3 квадрата
    int startRow = (row / 3) * 3;
    int startCol = (col / 3) * 3;
    for (int r = 0; r < 3; r++) {
        for (int c = 0; c < 3; c++) {
            if (board[startRow + r][startCol + c] == num) {
                return false;
            }
        }
    }

    return true;
}

bool solveSudoku(int board[9][9]) {
    // Намираме следващата празна клетка
    int row = -1, col = -1;
    for (int r = 0; r < 9 && row == -1; r++) {
        for (int c = 0; c < 9; c++) {
            if (board[r][c] == 0) {
                row = r;
                col = c;
                break;
            }
        }
    }

    // Ако няма празни клетки, решението е готово
    if (row == -1) return true;

    // Опитваме цифрите от 1 до 9
    for (int num = 1; num <= 9; num++) {
        if (isValid(board, row, col, num)) {
            board[row][col] = num;  // Поставяме числото

            if (solveSudoku(board)) {
                return true;  // Намерено решение
            }

            board[row][col] = 0;  // Backtrack
        }
    }

    return false;  // Няма решение с текущата конфигурация
}

2.5. Генериране на комбинации

Избиране на \(k\) елемента от \(n\) елемента.

int n, k;
vector<int> combination;

void generateCombinations(int start) {
    if (combination.size() == k) {
        // Принтираме комбинацията
        for (int x : combination) {
            cout << x << " ";
        }
        cout << endl;
        return;
    }

    for (int i = start; i <= n; i++) {
        combination.push_back(i);
        generateCombinations(i + 1);  // Следващият елемент е по-голям
        combination.pop_back();  // Backtrack
    }
}

3. Окастряне (Pruning)

Най-важната част от Backtracking е оптимизацията. Ако сме сигурни, че текущият клон няма да даде решение (или по-добро от вече намереното), спираме веднага.

3.1. Видове окастряне

Feasibility Pruning (Окастряне по осъществимост): Спираме когато решението е невъзможно. * Пример: В задачата за раницата, ако текущото тегло надвишава капацитета, връщаме се.

Optimality Pruning (Окастряне по оптималност): Спираме когато не можем да постигнем по-добро решение от вече намереното. * Пример: В TSP (Търговския пътник), ако текущият път вече е по-дълъг от най-добрия намерен до момента, спираме.

Bound Pruning (Окастряне с граници): Използваме долна/горна граница за да преценим дали има смисъл да продължим. * Пример: В задачата за раницата, ако дори да вземем всички оставащи предмети (relaxation), не можем да подобрим текущия максимум, спираме.

3.2. Пример: Задача за раницата с backtracking

int n, capacity;
int weight[100], value[100];
int bestValue = 0;

void knapsack(int idx, int currentWeight, int currentValue) {
    if (currentWeight > capacity) return;  // Feasibility pruning

    if (idx == n) {
        bestValue = max(bestValue, currentValue);
        return;
    }

    // Optimality pruning: проверка с relaxation
    int remainingValue = 0;
    for (int i = idx; i < n; i++) {
        remainingValue += value[i];
    }
    if (currentValue + remainingValue <= bestValue) {
        return;  // Не можем да постигнем по-добро решение
    }

    // Взимаме предмета
    knapsack(idx + 1, currentWeight + weight[idx], currentValue + value[idx]);

    // Не взимаме предмета
    knapsack(idx + 1, currentWeight, currentValue);
}

3.3. Heuristics (Евристики)

Редът, по който изследваме решенията, може драматично да повлияе на производителността. Добрите евристики намират решението по-рано.

Пример: Избор на променлива в Sudoku Вместо да обхождаме клетките по ред, избираме клетката с най-малко възможни стойности (Most Constrained Variable).

pair<int, int> findBestCell(int board[9][9]) {
    int minOptions = 10;
    pair<int, int> bestCell = {-1, -1};

    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            if (board[r][c] != 0) continue;

            int options = 0;
            for (int num = 1; num <= 9; num++) {
                if (isValid(board, r, c, num)) options++;
            }

            if (options < minOptions) {
                minOptions = options;
                bestCell = {r, c};
            }
        }
    }

    return bestCell;
}

4. Сложност

Backtracking алгоритмите често имат експоненциална сложност (\(O(N!)\), \(O(2^N)\), \(O(K^N)\)). * Подходящи са за \(N \le 20\) (за подмножества) или \(N \le 10\) (за пермутации). * Ако \(N\) е по-голямо, търсете Динамично програмиране или Greedy.

4.1. Анализ на сложността

Пермутации: - Брой възли: \(1 + n + n(n-1) + n(n-1)(n-2) + \dots + n!\) - Приблизително \(O(n \cdot n!)\)

Подмножества: - Брой възли: \(2^n\) (всеки елемент - вземаме/не вземаме) - Общо време: \(O(2^n \cdot T)\) където \(T\) е времето за обработка на един възел

N-царици: - Най-лош случай: \(O(n^n)\) - С pruning на практика: много по-бързо

4.2. Практически ограничения

Тип задача Максимален N Време (ориентировъчно)
Пермутации 10-11 ~1 секунда
Подмножества 20-25 ~1 секунда
N-царици 15-20 ~1 секунда (с добро pruning)
Sudoku 9×9 Фиксиран Обикновено бързо с евристики

5. Backtracking vs Динамично програмиране

Кога да използваме Backtracking?

  • Трябва да намерим ВСИЧКИ решения
  • Проблемът няма оптимална подструктура
  • Малки constraints (\(N \leq 20\))
  • Има добри възможности за pruning

Кога да използваме ДП?

  • Търсим ЕДНО оптимално решение (или брой решения)
  • Има overlapping subproblems
  • Може да дефинираме clear state
  • По-големи constraints

Пример: Subset Sum

  • Backtracking: Генерира всички подмножества и проверява сумите (\(O(2^n)\) без памет)
  • ДП: Пази кои суми са достижими (\(O(n \cdot sum)\) с памет)

5. Задачи

  1. UVa 750: 8 Queens Chess Problem.
  2. Sudoku Solver: Класически backtracking.
  3. Codeforces 1285B: Just Eat It! (може да се реши и с Greedy, но малките constraints позволяват BT).
  4. Knight's Tour: Обхождане на дъска с кон.
  5. CSES - Chessboard and Queens: N-царици вариация.
  6. LeetCode 51: N-Queens (класическа задача).
  7. LeetCode 37: Sudoku Solver.
  8. Codeforces 580C: Kefa and Park (DFS/Backtracking в дърво).

6. Съвети и често срещани грешки

6.1. Често срещани грешки

1. Забравяне на undoMove: 

// ГРЕШНО
void backtrack(State s) {
    makeMove(s);
    backtrack(s);
    // Забравено: undoMove(s);
}

2. Модифициране на глобални променливи без възстановяване: 

vector<int> path;

void solve() {
    path.push_back(x);
    solve();
    // Забравено: path.pop_back();
}

3. Неправилна проверка за база: 

// ГРЕШНО: може да пропуснем валидни решения
if (idx > n) return;  // Трябва да е idx == n

6.2. Оптимизационни техники

1. Битови маски вместо булеви масиви: 

// Вместо bool used[20];
int usedMask = 0;

// Проверка
if (usedMask & (1 << i)) { /* използван */ }

// Поставяне
usedMask |= (1 << i);

// Премахване
usedMask &= ~(1 << i);

2. Предварително пресмятане: Ако проверките са скъпи, прекалкулирайте ги еднократно.

3. Сортиране на входа: Понякога сортирането позволява по-ранно pruning.

6.3. Debugging съвети

  1. Принтирайте пътя: Показвайте решението на всяка стъпка
  2. Ограничете дълбочината: Тествайте с малки входове първо
  3. Преброявайте извиквания: Колко рекурсивни извиквания се правят?
  4. Визуализирайте дървото: Начертайте първите няколко нива

🏁 Заключение

Винаги помнете да възстановите състоянието (undoMove) след връщане от рекурсията. Това е най-честата грешка.

Backtracking е мощна техника, но изисква внимание към детайлите. Ключът към успеха е: 1. Правилна дефиниция на състоянието - какво трябва да знаем на всяка стъпка? 2. Ефективна валидация - колкото по-рано откажем невалидни пътища, толкова по-бързо 3. Коректно backtracking - всяка промяна трябва да се отмени 4. Интелигентно окастряне - добрите евристики правят разликата между бързо и бавно решение

Практикувайте с класическите задачи (N-царици, Sudoku, пермутации) преди да преминете към по-сложни приложения. Разбирането на тези основи ще ви помогне да решавате много по-трудни задачи в състезанията.