Поиск с возвратом в решении типичных задач на собеседовании

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

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

Обратный поиск состоит из трех частей: рекурсивной функции, получающей набор решений, который может быть незавершенным n, мутации  —  дополнения к n, добавляемой к набору n, а также проверки решения на завершенность и верность, которая проверяет завершение мутаций набора решений  —  полноценно ли данное решение? и верность  —  является ли решение приемлемым с подставленными на данный момент значениями?.

Обратный поиск автоматически создает чистое и эффективное, с точки зрения вычислений, дерево поиска, основанное на очень простых элементах.

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

Задача об N-ферзях

Это стандартная задача для обратного поиска: дана шахматная доска размера N на N. Сколькими способами можно расположить N-ферзей так, чтобы они не угрожали друг другу, т.е. чтобы один ферзь не находился в одном ряду, столбце или по диагонали с другим?

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

Решение методом грубой силы (brute-force) будет следующим: нужно перебрать каждую комбинацию N-ферзей в каждой из N на N точек  —  N² и выбрать N возможных вариантов. 

Если изобразить график, где x представляет N, а y  —  число вероятностей для поиска, то он устремится вверх.

Только для стандартной сетки 8 на 8 существует 4,426,165,368 возможных комбинаций, перебор которых займет непозволительно много времени. Это можно частично улучшить, никогда не располагая двух ферзей в одном ряду или столбце, но нам по-прежнему потребуется перебрать каждый ряд и каждую клетку  —  время выполнения O(N²) будет недостаточно быстрым. 

Теперь давайте пройдемся по чек листу вопросов, чтобы определить, поможет ли нам здесь обратный поиск.

Можно ли построить частичные решения?

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

Можно ли оценить эти частичные решения как верные или неверные?

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

Можно ли оценить решение как конечное?

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

Давайте построим алгоритм обратного поиска для решения этой задачи за более короткое время.

Функция n_queens:

Получает N и список чисел board.

Инициализирует board как пустой список, если он не определен, и count как 0.

Для каждого столбца x в N

>> добавляет индекс столбца x к board.

>> Если board верна  —  добавляет вывод n_queens с вводами N и board к count, что инициализирует очередной цикл функции и представляет туннелирование или процесс построения дерева обратного поиска. Поскольку частичное решение рассматривается в данном кейсе как верное, оно инициирует еще один экземпляр функции n_queens.

>> В противном случае удаляет столбец x. 

Возвращает count.

Телескопирование построения дерева

Функция для оценки верности доски действует следующим образом:

Получает список чисел board, где каждое число соответствует одному столбцу.

Ряд последнего добавленного ферзя представляет текущую длину доски минус один, так как индексация начинается с 0, а столбец текущего ферзя является последним элементом доски.

Для каждого ряда R и столбца C на доске, состоящей только из расставленных ферзей.

>> находит разницу между столбцом только что добавленного ферзя и текущим столбцом C. Если она равна 0, т.е. два столбца одинаковы, то возвращает False и выходит из функции.

>> находит разницу между столбцом только что добавленного ферзя и текущим столбцом R. Если она равняется 0, т.е. оба столбца одинаковы, то возвращает False и выходит из функции.

В противном случае возвращает True.

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

Результаты, где индекс указывает значение N:

1, 1, 0, 0, 2, 10, 4, 40, 92, 352

Задача с маршрутом полетов

Дается начальный аэропорт и неупорядоченный список рейсов, каждый из которых представлен парой откуда-куда. Нужно вычислить маршрут пассажира. Если таковой не существует  —  вернуть na, при этом в маршруте должны быть использованы все рейсы. 

Давайте в качестве примера возьмем эти рейсы:

• HNL ➔ AKL
• YUL ➔ ORD
• SFO ➔ HNL
• ORD ➔ SFO

С помощью грубой силы переберем пермутацию рейсов и проверим, является ли она верным маршрутом, делая это O(n!) раз.

Давайте снова пройдем по чек листу вопросов.

Можно ли построить частичные решения?

Да, такие решения можно построить путем составления неполного маршрута наподобие SFO ➔ HNL ➔ ORD ➔ ?.

Можно ли оценить эти частичные решения как верные или неверные?

Решение можно оценить как неверное, если из последнего пункта “куда” маршрута нет доступных рейсов и при этом остаются рейсы, которые можно осуществить. А поскольку использовать необходимо все рейсы, можно считать, что мы достигли заключительного узла. 

Можно ли оценить решение как конечное?

Да, решение оценивается как конечное, когда маршрут включает все рейсы.

Построение логики решения:

Функция get_itinerary:

Получает неупорядоченный список flights с элементами в форме origin/destination (откуда/куда) и current_itinerary, представляющим список маршрута, где первый элемент представляет начальный аэропорт, а второй пункт “куда” первого рейса (он же пункт “откуда” для второго рейса и т.д.).

Если все flights были использованы, возвращает current_itinerary.

last_stop будет равна последнему элементу current_itinerary.

Для каждой пары origin/destination в рейсах:

>> добавляет destination к current_itinerary.

>> Если origin равняется last_stop (это проверка, определяющая верность связи рейсов) — 

>>>> возвращает еще одно выполнение get_itinerary со всеми рейсами за исключением текущей пары origin/destination и выходит из функции.

>> В противном случае удаляет последнюю destination.

Возвращает None, если ни один из предыдущих поисков по дереву не смог вернуть решение.

Уменьшенная версия дерева, построенного методом поиска с возвратом

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

Обратите внимание, что для конкретно этой задачи существует гораздо более эффективное решение, и поиск с возвратом здесь мы использовали просто в качестве примера. В реальности быстрее было бы просто взять начальный аэропорт (например, SFO), найти среди рейсов связанный с ним аэропорт (SFO в HNL) и добавить пункт “куда” в расписание, продолжая это делать рекурсивно.

Судоку

Можем ли мы применить поиск с возвратом для решения стандартной загадки судоку?

Можно ли построить частичное решение?

Да, можно частично заполнить позиции на доске судоку.

Можно ли оценить эти частичные решения как верные или неверные?

Да, если в частичном решении присутствуют какие-либо числа, совпадающие с числами в строке, столбце или блоке  —  такое решение будет неверным. В противном случае  —  верным.

Можно ли оценить решение как конечное?

Да, решение будет конечным, когда вся доска будет заполнена.

Давайте попробуем заполнять каждую пустую ячейку одну за другой и возвращаться при достижении неверного состояния. Выглядеть это будет так:

Функция sudoku:

Получает переменную board, являющуюся массивом, где каждое значение представляет ячейку доски.

Если board заполнена, возвращает board и выходит из функции.

Пусть r и c представляют строку и столбец первого пустого значения на доске.

Для каждого значения i в [1, 2, 3, 4, 5, 6, 7, 8, 9]

>> устанавливает ячейку r строки и c столбца как i.

>> Если board остается верна,

>> >> выполняет еще один экземпляр sudoku для данной board.

Так может работать поиск с возвратом в версии судоку 4х4

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

Заключение

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

---

Перевод статьи Andre Ye: Backtracking: How to Approach Search Programming Interview Questions