Методы перебора в задачах поиска

Методы перебора – это класс алгоритмических подходов, в которых решение ищется путём систематического перечисления вариантов и проверки каждого на соответствие целевому предикату. Несмотря на «простоту» идеи, грамотный перебор опирается на строгие формальные основания: спецификацию поискового пространства, корректные инварианты, стратегию обхода и правила отсечения (pruning). Для ЕГЭ по информатике методы перебора критичны: ими решаются задачи на поиск и подсчёт объектов по условию, оптимизационные мини-/макс-задачи с малыми ограничениями, а также задания на моделирование, где требуется гарантированная полнота и корректность результата.

Модель поисковой задачи

Полнота и корректность

Перебор корректен, если:

• Полнота: каждый допустимый кандидат будет либо построен, либо доказано, что он отсечён корректно (невозможность продолжить до решения).

• Непротиворечивость: один и тот же кандидат не учитывается более одного раза – нет дублей.

• Инвариант построения: на каждом шаге частичный кандидат удовлетворяет префиксным ограничениям (например, «частичная сумма не превышает верхней границы»).

Экспоненциальность и «разумные» границы

Полный перебор часто имеет экспоненциальную сложность O(b^d) (ветвление b, глубина d). Поэтому ключ к практике – структурирование и отсечения, уменьшающие фактическое число перебранных узлов.

Классификация методов перебора

1. Полный перебор (exhaustive): простейшая схема «перечислить всё и проверить». Применим при очень малых размерах.

2. Перебор подмножеств: битовые маски, генераторы подмножеств/комбинаций; типично O(2ⁿ)

3. Перебор перестановок: next_permutation, алгоритм Хипа; типично O(n!).

4. Перебор с возвратом (backtracking): пошаговая сборка решения с ранними проверками и откатами; строится дерево состояний.

5. Ветви и границы (branch & bound): backtracking + нижние/верхние оценки целевой функции для агрессивных отсечений.

6. Итерированное углубление: поиск в глубину с ограничением глубины, постепенно наращиваемым.

7. Стратегии обхода: DFS/BFS/лексикографический порядок – влияет на память, время первых находок и удобство отсечений.

Правила эффективного перебора (памятка)

1. Формализуйте пространство: чётко задайте порядок генерации элементов и исключите дубликаты конструкцией (а не пост-фильтром).

2. Проверяйте рано (early check): применяйте предикаты-ограничители к частичному решению, не дожидаясь полной сборки.

3. Оценки и отсечения: используйте верхние/нижние оценки по целевой функции (bound), чтобы «резать» бесперспективные ветви.

4. Упорядочивайте: правильный порядок добавления элементов радикально повышает полезность отсечений (сначала «дорогие» или «часто конфликтующие»).

5. Кэшируйте состояние: мемоизация/табулирование подзадач (по возможности) исключает повторный просмотр эквивалентных частичных конфигураций.

6. Битовое кодирование: подмножества, наборы ограничений и занятости (например, диагоналей в задачах на доске) удобно кодировать битами для O(1) проверок.

7. Чётко фиксируйте инвариант: после каждого шага частичное решение удовлетворяет всем применимым ограничениям.

8. Оценивайте сложность: заранее прикиньте верхнюю границу числа узлов; при необходимости ужесточите отсечения или смените метод.

Корректность перебора: инварианты и доказательство

Стандартный подход – структурная индукция по глубине:

• База: пустое состояние удовлетворяет инварианту (нет нарушений).

• Переход: добавление элемента по правилам сохраняет инвариант; ветви, нарушающие инвариант или оценку, корректно отсечены (никакого истинного решения в них нет).

• Вывод: найденные листья – все и только корректные решения; при наличии оптимизационного критерия – минимальность/максимальность следует из глобального отсечения по bound. 

Форматы задач ЕГЭ, решаемых перебором

• Подсчёт/поиск чисел, строк, пар/троек, удовлетворяющих условиям (делимость, разряды, монотонность, различность).

• Поиск конфигураций с ограничениями (например, расстановки, кратчайшие/допустимые пути в малых графах).

• Минимизация/максимизация функции на малых nnn (подмножества, перестановки).

• Моделирование процессов (итеративные преобразования с проверкой состояний).

Совет для ЕГЭ: распознайте размерность. Если n≤20 – часто применим перебор подмножеств; если n≤10 – допустим перебор перестановок с отсечениями; если есть «естественные» ранние проверки – используйте backtracking.

Шаблоны реализации (Python)

1. Перебор подмножеств (битмаска)

def subsets(a):

    n = len(a)

    for mask in range(1 << n):

        sub = []

        for i in range(n):

            if mask & (1 << i):

                sub.append(a[i])

        yield sub

2. Backtracking с ранними проверками

def backtrack(prefix, candidates, ok_prefix, consume):

    if consume(prefix):        # готовое решение

        yield prefix[:]

        return

    for x in candidates(prefix):

        if ok_prefix(prefix, x):

            prefix.append(x)

            yield from backtrack(prefix, candidates, ok_prefix, consume)

            prefix.pop()

3. Ветви и границы (эскиз)

best_val = float('inf')

best_ans = None 

def bb(prefix, lower_bound, complete, extend):

    global best_val, best_ans

    if complete(prefix):

        val = value(prefix)

        if val < best_val:

            best_val, best_ans = val, prefix[:]

        return

    if lower_bound(prefix) >= best_val:    # отсечение

        return

    for x in extend(prefix):

        prefix.append(x)

        bb(prefix, lower_bound, complete, extend)

        prefix.pop()

4. Meet-in-the-middle (схема)

from bisect import bisect_right 

def mitm_subset_sum(a, S):

    mid = len(a)//2

    L, R = a[:mid], a[mid:]

    left_sums = [0]

    for x in L:

        left_sums += [s + x for s in left_sums]

    right_sums = [0]

    for x in R:

        right_sums += [s + x for s in right_sums]

    right_sums.sort()

    # максимум ≤ S

    best = None

    for s in left_sums:

        if s > S: continue

        j = bisect_right(right_sums, S - s) - 1

        if j >= 0:

            cur = s + right_sums[j]

            if best is None or cur > best:

                best = cur

    return best

Пять упражнений (с подробными решениями)

Упражнение 1. Подмножество с заданной суммой (перебор + ранние отсечения)

Условие. Дано n≤20, массив положительных чисел a_i и целевое S. Требуется:

проверить существование подмножества с суммой ровно S;

вывести количество таких подмножеств.

Идея. Линейный порядок по индексам, backtracking с префиксной суммой и отсечением sum_prefix > S.

Решение (Python).

def count_subsets_sum(a, S):

    a.sort(reverse=True)                 # крупные элементы раньше – лучшее отсечение

    cnt = 0

    def dfs(i, s):

        nonlocal cnt

        if s == S:

            cnt += 1

            return

        if s > S or i == len(a):

            return

        # включить a[i]

        dfs(i+1, s + a[i])

        # исключить a[i]

        dfs(i+1, s)

    dfs(0, 0)

    return cnt

# пример:

# a = [7, 3, 2, 5, 8], S = 10 -> подмножества: {7,3}, {8,2}

Корректность. Инвариант: s – сумма выбранных первых i элементов; если s > S, расширение бесполезно (все числа положительные) – корректное отсечение.
Сложность. Худший случай O(2ⁿ), но отсечения уменьшают фактическое дерево.

Упражнение 2. Классическая задача «8 ферзей» (backtracking + битовые маски)

Условие. Расставить 8 ферзей на шахматной доске 8×8, чтобы они не били друг друга. Найти количество размещений.

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

Решение (Python).

def n_queens_count(n=8):

    # columns, diag1 (r-c), diag2 (r+c)

    def dfs(r, col_mask, d1_mask, d2_mask):

        if r == n:

            return 1

        count = 0

        free = ((1 << n) - 1) & ~col_mask

        while free:

            bit = free & -free

            c = (bit.bit_length() - 1)

            if (d1_mask >> (r - c + n - 1)) & 1: 

                free &= free - 1

                continue

            if (d2_mask >> (r + c)) & 1:

                free &= free - 1

                continue

            count += dfs(r+1,

                         col_mask | bit,

                         d1_mask | (1 << (r - c + n - 1)),

                         d2_mask | (1 << (r + c)))

            free &= free - 1

        return count

    return dfs(0, 0, 0, 0)

Инвариант. На шаге r корректно расставлены ферзи на строках 0..r-1; маски отражают занятые направления.
Сложность. Значительно меньше n! благодаря отсечениям; для n=8 вычисляется мгновенно.
Связь с ЕГЭ. Демонстрация дисциплины инвариантов и битовых масок.

Упражнение 3. Перестановки с оптимизацийе (ветви и границы)

Решение (Python, эскиз).

def minimize_path(a):

    n = len(a)

    idx = list(range(n))

    idx.sort(key=lambda i: a[i])

    # предвычислим минимальную разницу соседей в отсортированном списке

    mindiff = min(abs(a[idx[i+1]] - a[idx[i]]) for i in range(n-1)) if n > 1 else 0

    used = [False]*n

    best = float('inf') 

    def dfs(path, s):

        nonlocal best

        k = len(path)

        if k == n:

            best = min(best, s)

            return

        # нижняя оценка: даже в лучшем случае оставшиеся (n-k-1) связки добавят >= mindiff каждая

        if s + max(0, (n-k-1))*mindiff >= best:

            return

        for i in range(n):

            if used[i]: 

                continue

            if k == 0:

                used[i] = True

                dfs([i], 0)

                used[i] = False

            else:

                prev = path[-1]

                cost = abs(a[prev] - a[i])

                if s + cost >= best:

                    continue

                used[i] = True

                path.append(i)

                dfs(path, s + cost)

                path.pop()

                used[i] = False

    dfs([], 0)

    return best

Замечания. Чем точнее bound, тем сильнее отсечения (можно учитывать ближайших соседей по отсортированному массиву).
Связь с ЕГЭ. Пример оптимизационной задачи на малых nnn с доказуемой корректностью отсечений.

Упражнение 4. Meet-the-middle для "почти неперераемого" суммирования.

Упражнение 5. Перебор цифр с условиями (ЕГЭ-стиль)

Условие. Найдите количество 6-значных чисел в десятичной системе счисления, удовлетворяющих:

• первая цифра не ноль;

• все цифры различны;

• сумма цифр кратна 5.

Идея. Перебор без повторений по позициям (backtracking с «занятыми» цифрами), ранняя проверка по остатку суммы по модулю 5.

Решение (Python).

def count_six_digit():

    used = [False]*10

    cnt = 0

    def dfs(pos, s_mod5):

        nonlocal cnt

        if pos == 6:

            if s_mod5 % 5 == 0:

                cnt += 1

            return

        start = 1 if pos == 0 else 0

        for d in range(start, 10):

            if used[d]: 

                continue

            # раннее отсечение бессильно по mod 5 кроме накопления остатка,

            # но упорядочивание «редких» цифр помогает мало – ограничения простые

            used[d] = True

            dfs(pos+1, (s_mod5 + d) % 5)

            used[d] = False

    dfs(0, 0)

    return cnt

Корректность. Инвариант: на шаге pos выбраны попарно различные цифры; первая цифра ненулевая за счёт start=1; остаток суммы поддерживается инкрементально.
Оценка. Верхняя граница 9⋅P(9,5)=9⋅9⋅8⋅7⋅6⋅5 – выполнимо за доли секунды.
Связь с ЕГЭ. Типовая конструкция «перебор по позициям + модульная проверка», важна дисциплина инварианта «все цифры различны» и начального ограничения на старший разряд.

Заключение

Методы перебора – не «грубая сила», а формальная технология:

• задание пространства,

• строгие инварианты,

• грамотные отсечения и оценки,

• осмысленный порядок генерации.

Именно такая дисциплина превращает экспоненциальную схему в практично работающую на реальных ограничениях ЕГЭ. Освоив описанные правила и шаблоны (подмножества, перестановки, backtracking, branch & bound, meet-in-the-middle), вы сможете уверенно распознавать переборные задачи, строить корректные решения и получать максимально возможные баллы за счёт прозрачного обоснования корректности и оценки сложности.