Опыт работы с возвратом
Когда я впервые начал готовиться к техническим собеседованиям, я тратил массу времени на изучение различных структур данных, алгоритмов и временной сложности. Я смог получить общее представление о различных концепциях с помощью замечательных статей на среднем уровне и проблем с рангом хакера, но я не смог хорошо понять концепцию обратного отслеживания, потому что это было настолько теоретическим, и большинство проблем были сложными задачами собеседования.
Надеемся, что эта статья станет тем недостающим элементом, который позволит вам использовать реальный пример с простыми объяснениями, чтобы вы могли быстро вернуться к подготовке к собеседованию или использовать обратный поиск в своей собственной программе, чтобы сделать что-нибудь крутое!
Эта проблема
Примечание. Если вы уже знакомы с правилами Содоку, не стесняйтесь переходить к разделу «Отслеживание с возвратом».
В этой статье мы рассмотрим принцип обратного отслеживания, используя его для решения игры в судоку. Если вы никогда раньше не слышали о судоку, это логическая игра-головоломка, в которой вам нужно объединить числа, чтобы полностью заполнить доску. Задача состоит в том, чтобы заполнить сетку 9x9 так, чтобы каждый столбец, каждая строка и каждая из девяти подсеток 3x3, составляющих сетку, содержали все цифры от 1 до 9. При запуске некоторые сетки частично заполняются. Вот пример стартовой доски.
И вот решение указанной выше платы. Обратите внимание, что каждая строка и каждый столбец имеют цифры от 1 до 9.
Кроме того, судоку - идеальная головоломка для изучения обратного поиска, поскольку она очень логична. Однако эта статья не о том, как решить доску судоку вручную. Если вы хотите узнать, как это сделать, я рекомендую эту статью, которую я также использовал для изображений, показанных выше.
Возврат
Примечание. Если вы уже знаете, что такое отслеживание с возвратом, и вы здесь только для того, чтобы использовать его для отслеживания с возвратом, не стесняйтесь перейти к разделу «Решение судоку» ниже.
До сих пор я довольно часто упоминал термин «возврат», но что это, черт возьми? Отслеживание с возвратом - это общий алгоритм поиска всех (или некоторых) решений проблемы, который постепенно создает кандидатов для решения. Как только он определяет, что кандидат не может быть решением проблемы, он отказывается от него («возвращается»).
Когда алгоритм отказывается от кандидата, он обычно возвращается к предыдущему этапу процесса решения проблемы. Это ключ к алгоритму, а также то, откуда он получил свое название.
Восемь Королев (N-Queens) и другие проблемы
Самый распространенный пример этого, о котором вы, вероятно, слышали, и который является очень теоретическим, - это загадка с восемью ферзями. Восемь ферзей требуют расположения восьми шахматных ферзей на стандартной шахматной доске, чтобы ни один ферзь не напал на других.
При обычном подходе к решению этой проблемы частичными кандидатами являются расположение k ферзей в первых k строках доски, все в разных строках и столбцах. От любого частичного решения, содержащего двух взаимно атакующих ферзей, можно отказаться.
Я не буду углубляться в N-Queens, потому что это довольно теоретический вопрос, и цель этой статьи - использовать простые примеры из реальных слов, но если вы хотите прочитать больше, вот - фантастическая статья от Сачина Малхотры. который вникает в него глубже.
Другие распространенные проблемы, о которых вы, вероятно, уже слышали в отношении обратного отслеживания, - это его использование в кроссвордах, словесной арифметике и поиск пути через лабиринт. Это также наиболее удобный (если не самый эффективный) метод разбора, задачи о ранце, задач комбинаторной оптимизации. Это также основа так называемых языков логического программирования, таких как Prolog, Icon и Planner.
Подробнее об алгоритме
Помимо исходной проблемы и конечной цели, возврат с возвратом обычно имеет набор ограничений, которым программа также должна следовать, чтобы быть эффективной.
Самые простые (и «самые глупые») реализации отслеживания с возвратом часто используют очень мало «логики» или очень мало «понимают» проблему. Вместо того, чтобы быть эффективным решением, это, как правило, приводит к случайному угадыванию программой и часто оказывается не лучше, чем решение методом грубой силы.
Решение судоку
Теперь, когда вы знаете, что такое судоку и что такое отслеживание с возвратом, давайте рассмотрим ограничения и цель, которые потребуются нашему алгоритму для решения судоку, а затем мы рассмотрим простую задачу 3x3, как если бы мы были алгоритмом. Ниже приведены ограничения и цели нашего алгоритма поиска с возвратом.
Ограничения
Помните, что ограничения для проекта определяются путем проверки каждого отдельного кандидата. Кандидат в судоку считается действительным, если выполняются следующие ограничения.
- Каждая строка имеет уникальные номера от 1 до 9 или пустые места.
- Каждый столбец имеет уникальные номера от 1 до 9 или пустые места.
- Каждая подрешетка 1–9 имеет числа 1–9 или пустые места.
Цель и условия прекращения действия
Цель нашего алгоритма также является целью игры, а также очень похожа на наши ограничения. В судоку у нас только одна цель.
- Введите числа от 1 до 9 ровно один раз в каждую строку, столбец и область 3x3.
Большинство алгоритмов поиска с возвратом также имеют своего рода условие завершения, чтобы они не зацикливались бесконечно в поисках решения проблемы, у которой нет решения. В случае судоку у нас есть только два условия прекращения.
- Доска уже заполнена, то есть пустого пространства нет.
- Больше не осталось пустых мест для проверки алгоритмом, и текущий кандидат не достигает нашей цели.
Код
Вышеупомянутая ссылка ссылается на безделушку, содержащую код и пример решения Sudoku Solver в действии. Он показывает вам, когда алгоритм откатывает назад, когда кандидат больше не жизнеспособен.
Я надеюсь, что эта визуализация покажет вам, как работает возврат с возвратом в действии, а код предоставляет хороший пошаговый анализ с добавленными комментариями о том, как работает процесс с возвратом.
Я хотел бы поблагодарить https://www.101computing.net/ за их красивую визуализацию и базу для кода, приведенного выше. Я просто внес некоторые изменения, чтобы облегчить чтение и понимание происходящего.
Ресурсы и заключительные примечания
Итак, теперь, когда вы являетесь мастером решения судоку, к чему вам двигаться дальше? Если вы хотите проверить некоторые другие проблемы, которые вы можете решить, я бы порекомендовал следующие две, чтобы действительно укрепить ваши знания об обратном отслеживании.
- N-Queens: Более теоретический, но общий вопрос интервью. Я уже упоминал об этом ранее, но отличную статью по этой конкретной проблеме можно найти здесь.
- Решение лабиринта: еще один практичный и забавный пример, который также можно решить с помощью поиска с возвратом. Мой одноклассник написал об этом хорошую статью, которую можно найти здесь. Если вы хотите проверить алгоритм сейчас, вот отличная визуализация, которую я нашел.
Если вы хотите узнать больше об отслеживании с возвратом и его вариантах использования, вот несколько различных статей, которые помогут вам глубже понять.
Спасибо за прочтение. Я надеюсь, что теперь у вас есть более глубокое понимание того, как найти полезный случай для этого!
Если вы хотите проверить другие вещи, которые я сделал, зайдите на Github.
