Изучите алгоритм возврата

Question

Я хочу выучить алгоритм возврата.Может кто-нибудь научить меня этому?Я пытался учиться на некоторых сайтах, но это не сработало.Так может кто-нибудь, пожалуйста, научите меня.Спасибо!

Answer 1

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

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

Пример

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

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

Алгоритм возврата будет «умнее»: он поймет, что четвертая королева неправильно расположена, и «вернется» к рассмотрению других квадратов для него.

Answer 2

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