14.04.1963 г.
Поиск с возвратом — это метод решения задач, который использует последовательный перебор возможных вариантов. Формальные грамматики позволяют определять, например, синтаксически правильные алгебраические выражения. В заключение рассматривается тесная связь между рекурсией и математической индукцией. Будет показано, как использовать математическую индукцию для анализа свойств алгоритмов. Существуют программы систематического перебора вариантов решения задачи. Если какой-либо из вариантов заводит алгоритм в тупик, выполняется возврат назад и замена гипотезы на другую. Эта стратегия отката с последующим выполнением новой последовательности шагов называется поиском с возвратом (backtracking).
Рассмотрим комбинацию поиска с возвратом и рекурсии при решении следующей задачи. Поиск с возвратом — это стратегия последовательного перебора вариантов решения, предусматривающая возврат назад, если алгоритм зашел в тупик.
Задача о восьми ферзях
Разместите восемь ферзей на шахматной доске так, чтобы ни один из них не был атакован другим. Шахматная доска разбита на 64 клетки, образующие восемь горизонталей и восемь вертикалей. Наиболее сильной шахматной фигурой является ферзь, поскольку он может атаковать любую клетку горизонтали, вертикали и диагоналей, на пересечении которых он стоит.
В задаче о восьми ферзях предлагается разместить их на шахматной доске так, чтобы ни один из них не был атакован другим. Одна из стратегий решения этой задачи сводится к перебору вариантов решения. Однако существует 4426165368 способов разместить восемь ферзей на шахматной доске. Перебрать все эти варианты практически невозможно.
Иначе говоря, на каждой горизонтали и вертикали может стоять только один ферзь. Таким образом, остается 840320 вариантов, которые подлежат проверке. Задача становится намного проще. Разместите ферзей по одному на каждой вертикали. Допустим, что, следуя стратегии перебора вариантов, мы разместили по одному ферзю. На каждой вертикали, начиная с первой клетки первой вертикали. Рассматривая вторую вертикаль, мы обязаны исключить из нее первую клетку, поскольку на первой горизонтали уже стоит другой ферзь, а также вторую клетку, поскольку ферзь атакует диагональ. В итоге второго ферзя следует поместить в третью клетку второй вертикали.
Вновь проанализировав шестую вертикаль, мы убеждаемся, что поставить на нее ферзя по-прежнему невозможно. Исчерпав все возможные варианты расположения ферзя на пятой вертикали, мы должны вернуться к четвертой вертикали. Следующая свободная клетка на четвертой вертикали расположена на седьмой горизонтали. Затем нужно снова рассмотреть пятую вертикаль и поставить ферзя на вторую горизонталь. Как применить рекурсию для решения этой задачи?
Рассмотрим алгоритм, который размещает ферзя на вертикали, при условии, что на предыдущих вертикалях остальные ферзи расставлены правильно. Во-первых, если текущая вертикаль оказалась последней, задача решена. Это — базовая задача. В противном случае после размещения ферзя на текущей вертикали нужно перейти к следующей. Иными словами, нужно решить ту же самую задачу с меньшим количеством вертикалей. Это — шаг рекурсии. Таким образом, процедура решения задачи начинается с восьми вертикалей, а затем на каждом шаге рекурсии количество вертикалей уменьшается на единицу. Базовая задача возникает, когда все вертикали оказываются использованными. На первый взгляд, это решение удовлетворяет критериям применения рекурсии. Однако мы до сих пор не знаем, как правильно поставить ферзя на текущую вертикаль. Если ферзь поставлен правильно, можно переходить к следующей вертикали. Если поставить ферзя на текущую вертикаль невозможно, нужно выполнить откат. Решение задачи достигается с помощью комбинации поиска с возвратом и рекурсии.
Однако такая реализация слишком неэкономно использует память. Помимо всего прочего, из 64 клеток реально используются лишь 8.
Уважаемые читатели! За содержание данной статьи Администрация сайта "Информер событий" ответственности не несет!
