Объясняется визуально на трех примерах: N королев, маршрут полета и судоку.

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

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

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

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

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

Проблема N-Queens

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

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

Решение проблемы методом перебора состоит в том, чтобы попробовать каждую комбинацию из N ферзей в каждой из N на N точек - N² выберите N возможностей.

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

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

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

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

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

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

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

Можно ли подтвердить решение как законченное?

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

Давайте построим подход с возвратом, чтобы быстрее решить проблему N королев.

Функция n_queens:

  1. Взять N и board, список чисел.
  2. Инициализируйте board как пустой список, если он не указан, и count равным 0.
  3. Для каждого столбца X в N,
  4. ›› Добавить индекс столбца X ’ в board.
  5. ›› Если board допустимо, добавьте выход n_queens с входами N и board в count (это инициализирует другой цикл функции и является процессом туннелирования или построения дерева с возвратом. Поскольку частичное решение считается допустимым в этом случае, он инициирует другой экземпляр функции n_queens).
  6. ›› В противном случае удалите столбец X.
  7. Вернуть count.

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

  1. Введите board, список чисел, где каждое число соответствует одному столбцу.
  2. Последняя добавленная строка ферзя - это текущая длина доски минус один (поскольку индексы начинаются с 0), а столбец текущего ферзя - это последний элемент доски.
  3. Для каждой строки R и столбца C на доске (которая состоит только из размещенных ферзей),
  4. ›› Найдите разницу между недавно добавленным столбцом ферзя и текущим столбцом C. Если он равен 0 (два столбца одинаковые), вернуть False и выйти из функции.
  5. ›› Найдите разницу между добавленным рядом ферзя и текущим R. Если он равен 0 (две строки одинаковы), вернуть False и выйти из функции.
  6. В противном случае верните True.

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

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

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

Проблема маршрута полета

Учитывая неупорядоченный список чьих-либо рейсов, каждый из которых представлен парой (вылет, пункт назначения) и аэропортом отправления, вычислите маршрут этого человека. Если такового не существует, верните «нет» - в маршруте должны использоваться все рейсы.

Возьмем для примера такие полеты:

  • HNL ➔ AKL
  • YUL ➔ ORD
  • SFO ➔ HNL
  • ЗАКАЗ ➔ SFO

Решение проблемы методом грубой силы состоит в том, чтобы пробовать каждую перестановку рейсов и проверять, является ли это допустимым маршрутом, делая это O (n!) Временем.

Давайте еще раз зададим наш контрольный список из трех вопросов для использования отслеживания с возвратом.

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

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

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

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

Можно ли подтвердить решение как законченное?

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

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

Функция get_itinerary:

  1. Составьте неупорядоченный список flights с элементами в форме (origin, destination) и current_itinerary, список маршрута (где первый элемент - это аэропорт отправления, а второй - пункт назначения первого рейса и пункт отправления второго рейса и т. Д. ).
  2. Если flights были израсходованы, верните current_itinerary.
  3. last_stop будет равен последнему элементу current_itinerary.
  4. Для каждой (origin, destination) пары в рейсах
  5. ›› Добавьте destination в current_itinerary.
  6. ›› Если origin равно last_stop (это проверка, удостоверяющая, что рейс является действительным соединением),
  7. ›› ›› Верните еще один запуск get_itinerary со всеми рейсами, кроме текущей пары (origin, destination), и прервите функцию.
  8. ›› В противном случае удалите самые последние destination.
  9. Вернуть None, если ни один из предыдущих поисков по дереву не дал никакого решения.

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

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

Судоку

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

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

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

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

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

Можно ли подтвердить решение как законченное?

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

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

Функция sudoku:

  1. Возьмите переменную board, которая представляет собой массив, каждое значение которого представляет собой ячейку на доске судоку.
  2. Если board завершен, верните board и прервите выполнение функции.
  3. Пусть r и c представляют строку и столбец первого пустого значения на доске.
  4. Для каждого значения i в [1, 2, 3, 4, 5, 6, 7, 8, 9],
  5. ›› Установите r-ю строку и c-ю ячейку столбца равными i.
  6. ›› Если board действителен,
  7. ›› ›› Запустить еще один экземпляр sudoku для board.

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

Заключение

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