Алгоритм бэктрекинга

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

Особенно полезен для задач удовлетворения ограничений: головоломок, перестановок, сочетаний и поиска путей.

Основные принципы#

Алгоритм бэктрекинга следует таким принципам:

1. Выбор. На каждом шаге у вас есть набор возможных вариантов.
2. Ограничения. Есть ограничения, которые сужают выбор.
3. Цель. Условие, при котором решение считается найденным, и можно откатиться от тупика.

Базовый шаблон#

Базовый шаблон алгоритма бэктрекинга на JavaScript:

function backtrack(path, options) {
    if (isSolution(path)) {
        processSolution(path);
        return;
    }

    for (const choice of options) {
        if (isValid(path, choice)) {
            path.push(choice);
            backtrack(path, options);
            path.pop();
        }
    }
}

Применения#

Бэктрекинг используется в самых разных задачах:

• Головоломки. Судоку, кроссворды, поиск слов.
• Перестановки. Генерация всех перестановок множества элементов.
• Сочетания. Генерация всех сочетаний.
• Графы. Поиск путей, циклов, остовных деревьев.
• CSP. Планирование, оптимизация.
• Игры. Шахматы, шашки.
• Подмножества. Поиск подмножеств, удовлетворяющих условиям.

Сложность#

Сложность алгоритмов бэктрекинга зависит от задачи. В худшем случае она экспоненциальна — O(b^d), где b — фактор ветвления, а d — глубина рекурсии.