Алгоритм поиска с возвратом: практическое руководство на Python

Что такое поиск с возвратом и зачем он нужен?

Когда я впервые услышал термин «поиск с возвратом» (backtracking), он показался мне сложным алгоритмом, доступным только учёным. Но после нескольких недель изучения и реализации в проекте Тетрис Оптимизатор я понял удивительную вещь: поиск с возвратом — это просто искусство принять решение, проверить, работает ли оно, и если нет — отменить его и попробовать что-то другое. Эта статья объясняет алгоритм на практическом примере, а не на абстрактных задачах.

Постановка задачи: укладка тетрамино

Представьте, что у вас есть несколько фигурок тетриса (тетрамино), и ваша цель — разместить их все в наименьшем возможном квадрате. Вот пример фигур:

A A
A A

B B B
  B

C C C C

D
D
D D

Задача — разместить каждую фигуру так, чтобы:

• Фигуры не перекрывались.
• Ни одна фигура не выходила за границы поля.
• Каждая фигура использовалась ровно один раз.
• Поле было минимально возможного размера.

Это гораздо сложнее, чем кажется на первый взгляд.

Первая мысль: последовательное размещение

Сначала я думал, что можно просто размещать фигуры одну за другой: поставить A, потом B, потом C, потом D — и готово. Но программирование не всегда так любезно. Иногда первая позиция, которую вы выбрали для фигуры A, делает невозможным размещение D позже. Ошибка была не в D — ошибка случилась гораздо раньше.

Как работает поиск с возвратом

Алгоритм поиска с возвратом работает так:

1. Поставить фигуру.
2. Попробовать поставить следующую.
3. Если зашли в тупик — убрать последнюю фигуру.
4. Попробовать другую позицию.
5. Повторять, пока все фигуры не встанут.

По сути, это означает: «Если этот путь не работает, давай вернёмся и исследуем другой».

Визуализация поиска

Предположим, у нас есть четыре тетрамино. Дерево решений выглядит так:

Начало
 ├── Поставить A в (0,0)
 │      ├── Поставить B
 │      │      ├── Поставить C
 │      │      │      ├── D встаёт ✅
 │      │      │      └── D не встаёт ❌
 │      │      └── Попробовать другую позицию
 │      └── Переместить A в другое место
 └── Попробовать другую позицию для A

Каждая ветка — это ещё одна возможность. Поиск с возвратом исследует эти ветки, пока не найдёт работающую.

Реализация на Python

Сердце алгоритма удивительно компактно. Вот пример на Python:

def solve(index):
    # Базовый случай: все фигуры размещены
    if index == len(pieces):
        return True
    
    # Перебираем все возможные позиции для текущей фигуры
    for x in range(board_size):
        for y in range(board_size):
            # Проверяем, можно ли поставить фигуру
            if can_place(pieces[index], x, y):
                # Размещаем фигуру
                place(pieces[index], x, y)
                # Рекурсивно пытаемся разместить следующую
                if solve(index + 1):
                    return True
                # Если не получилось — убираем фигуру (возврат)
                remove(pieces[index], x, y)
    
    # Ни одна позиция не подошла
    return False

Всё вращается вокруг четырёх действий:

• Проверить, входит ли фигура.
• Разместить её.
• Продолжить рекурсивно.
• Убрать её, если необходимо.

Последний шаг — удаление фигуры — и даёт алгоритму название «поиск с возвратом».

Зачем нужно удалять фигуру?

Представьте, что вы решаете лабиринт. Вы выбрали левый путь, прошли немного и упёрлись в тупик. Останетесь ли вы там навсегда? Нет. Вы вернётесь к последнему перекрёстку и попробуете другое направление. Ваш алгоритм делает то же самое.

Поставить фигуру
     ↓
Тупик
     ↓
Убрать фигуру
     ↓
Попробовать другое место

Самый важный урок, который я усвоил

Код не был сложной частью. Сложно было понять, как мыслят рекурсивные вызовы. Как только я перестал представлять рекурсию как «функции, вызывающие функции», и начал представлять её как исследование дерева решений, всё стало гораздо яснее. Рисование деревьев рекурсии на бумаге помогло мне понять, почему алгоритм ведёт себя именно так.

Почему это не полный перебор

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

Может ли фигура C встать?

Нет.

Не продолжай.

Вернись немедленно.

Такое раннее отклонение экономит огромное количество работы.

Как ускорить решатель

Мой проект «Тетрис Оптимизатор» научил меня, что одного поиска с возвратом недостаточно. Несколько улучшений могут кардинально сократить время выполнения:

• Начинайте с наименьшего возможного поля.
• Размещайте самые «проблемные» фигуры первыми. (те, которые труднее всего вписать)
• Пропускайте позиции, где фигура заведомо не встанет.
• Останавливайте поиск, как только найдена валидная комбинация.
• Избегайте повторения состояний поля, которые вы уже просматривали.

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

Что я вынес для себя

Изучение поиска с возвратом изменило то, как я думаю о программировании. Оно научило меня, что решение сложных задач не всегда требует немедленного знания ответа. Вместо этого нужно иметь смелость:

• Принять решение.
• Проверить его.
• Признать, когда оно не работает.
• Отменить его.
• Попробовать снова.

Этот урок применим далеко за пределами алгоритмов. Иногда самый быстрый путь к решению начинается с готовности сделать шаг назад.

Практический вывод

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

Что делать прямо сейчас: Возьмите любую задачу комбинаторной оптимизации (например, задачу о ферзях или судоку) и попробуйте реализовать её на Python с использованием поиска с возвратом. Начните с маленького размера, нарисуйте дерево решений и убедитесь, что каждый шаг понятен. Удачи в кодинге!