Алгоритм перебор с возвратом

Алгоритм перебор с возвратом


Во многих задачах из различных областей знания ставятся вопросы-задания типа: “Сколько существует способов …”, “Подсчитайте количество элементов …”, “Перечислите все возможные варианты …”, “Есть ли способ …”, “Существует ли объект…” и т. п. Ответы на них, как правило, требуют исчерпывающего поиска в некотором множестве M всех возможных вариантов, среди которых находятся решения конкретной задачи. Существуют два общих метода организации исчерпывающего поиска: перебор с возвратом (backtracking ) и его естественное логическое дополнение — метод решета.

Решение задачи методом перебора с возвратом строится конструктивно последовательным расширением частичного решения. Если на конкретном шаге такое расширение провести не удается, то происходит возврат к более короткому частичному решению, и попытки его расширить продолжаются. Для ускорения перебора с возвратом вычисления всегда стараются организовать так, чтобы была возможность отметать как можно раньше и как можно больше заведомо неподходящих вариантов M . Незначительные модификации метода перебора с возвратом, связанные с представлением данных или особенностями реализации, имеют и иные названия: метод ветвей и границ ( branch and bound ), поиск в глубину ( depth first search ), метод проб и ошибок и т. д. Перебор с возвратом практически одновременно и независимо был изобретен многими исследователями еще до его формального описания. Он находит применение при решении различных комбинаторных задач в области искусственного интеллекта.

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

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

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

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

study.sfu-kras.ru

Новые книги

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

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

Книга предназначена для начинающих программистов.

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

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

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

Перебор с возвратом

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

3.1 Использование рекурсии для записи алгоритма

Приведенная нами в подразделе 2.1 схема алгоритма довольно проста, однако она обычно неприемлема для реализации. Действительно, вложенные друг в друга циклы – очень жесткая структура и если нам надо решать задачу для 100 ферзей, то нам придется писать 100 вложенных друг в друга циклов. Более того, для каждого n нам придётся писать свой вариант алгоритма, отличающийся количеством вложенных циклов. Поэтому вариант с вложенными циклами обычно бывает неприемлемым для реализации перебора с возвратом. В книге [2] приведён алгоритм перебора с возвратом основанный на интерпретации перебора как последовательности переходов вперед-назад. Мы сейчас приведем схему алгоритма перебора с возвратом, построенную на принципах структурного программирования (т.е. без переходов) с использованием рекурсии.

Посмотрим на текст алгоритма. Сам текст алгоритма рекурсивен! Текст для n=k состоит из текста для n=k-1, помещённого в цикл. Таким образом, алгоритм легко переписать в рекурсивном виде. Снача ла мы приведём рекурсивный вариант алгоритма полного перебора.

Теперь – рекурсивный вариант алгоритма перебора с возвратом.

Чем отличаются данные алгоритмы ? Тем, что в первом проверка позиции происходит на самом позднем («глубоком») этапе перебора, а во втором на каждом этапе перебора происходит частичная проверка. (Если же все частичные проверки завершились успешно, получившуюся позицию уже можно не проверять.) Таким образом, перебор с возвратом исключает из перебора большое количество вариантов по сравнению с полным перебором.

3.2 Примеры решения задач при помощи перебора с возвратом

Первая задача – очень известная задача о раскраске карты (математики предпочитают обычно говорить о раскраске вершин графа).

Задача 3 Раскраска карты. Имеется географическая карта, на которой расположено n стран. Каждую страну надо раскрасить в один из k цветов так, чтобы соседние страны были раскрашены в разные цвета.

Географическую карту будем задавать в виде матрицы C размером n ґ n. Элемент Ci,j равен 1, если страны i и j – соседние и равен 0 иначе.

Пространство перебора состоит из наборов (x 1 . xn), xi О <1, . k>. Условие совместимости m-го элемента с предыдущими: если Ci,m=1 (1 Ј i 7
3 8
8 1 0
2 7 4 4
4 5 2 6 5 Требуется вычислить наименьшую сумму чисел на пути от верхней точки треугольника до основания. При этом:

  • каждый шаг шаг на пути может осуществляться вниз и влево или вниз и вправо,
  • число строк в треугольнике больше 1 и меньше 100,
  • треугольник составлен из целых чисел от 0 до 99.
  • Решение. При решении задачи полным перебором число вариантов равно 2 n-1 , где n – число строк в треугольнике. Это, конечно же, неприемлимо. Но как сократить перебор ? Трудно придумать условие, по которому мы могли бы отсекать частично построенные варианты.

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

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

    Пусть ai,j означает j-ое число в i-ой строке, si,j – наименьшую сумму чисел от вершины до числа ai,j. Для si,j выполняются следующие соотношения:

    Теперь написать программу нетрудно. Перебор в такой программе будет совсем небольшим (только выбор минимального из двух чисел для каждого числа в треугольнике и выбор минимального из n для путей из вершины к разным точкам основания).

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

    Задача 7 Бал. Во время бала в зале, имеющем форму M-угольника A 1 A 2 . AM, этикетом предписано размещаться N придворным дамам вдоль стен и в углах так, чтобы у всех стен стояло равное число дам. Если дама находится в углу, то она считается стоящей у обеих стен этого угла. Вдоль стены может размещаться любое количество дам, а в углу не больше одной. Найти требуемое расположение дам.

    Решение. Первый приходящий в голову способ решения для данной задачи – перебор. Однако легко догадаться, что по-существу важно получить какую-либо расстановку дам с суммарным количеством дам, стоящих вдоль стен, кратным количеству стен. Распредилить же потом их поровну не составит труда. А суммарное количество дам, стоящих вдоль стен, (при фиксированных количестве стен и дам) зависит только от того, сколько дам стоит в углах. Оно минимально, если в каждом углу стоит по даме и максимально, если вообще ни в одном углу не стоят дамы. Точнее (обозначим это число через s): N Ј s Ј N+M. Нам требуется так подобрать s, чтобы оно было кратно M. Среди чисел от N до N+M хотя бы одно такое число обязательно найдётся. Это N+M — (N mod M). В углах будет стоять M-(N mod M) дам. Остаётся только выбрать углы и распределить оставшихся дам по сторонам.

    3.3 Возврат

    В программе, решающей задачу о ферзях нет операторов, выполняющих возврат только потому, что при «движении вперёд» мы не производили почти никаких изменений. Изменялись только значение переменной m – оно будет восстановлено автоматически при возврате из рекурсивной процедуры и элемент массива ферзь – его нет необходимости восстанавливать, так как при новом выборе мы сразу же запишем в него новое значение.

    Однако, если при «движении вперёд» производятся ещё какие-нибудь изменения, их необходимо отменять при возврате.

    В задаче о раскраске карты есть такие изменения – это пересчёт количества использованных красок – операторы: кол_красок := кол_красок+1; и восстановление – кол_красок := кол_красок-1;

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

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

    wm-help.net

    Алгоритм перебора с возвратом

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

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

    Ответы на поставленные вопросы, как правило, требуют проведения исчерпывающего поиска в некотором множестве всех возможных вариантов, среди которых находятся решения конкретной задачи. Существуют два общих метода организации исчерпывающего поиска: перебор с возвратом ( backtracking ) и его естественное логическое дополнение — метод решета.

    Решение задачи методом перебора с возвратом строится конструктивно последовательным расширением частичного решения. Если на конкретном шаге такое расширение провести не удается, то происходит возврат к более короткому частичному решению, и попытки его расширить продолжаются. Для ускорения перебора с возвратом вычисления всегда стараются организовать так, чтобы была возможность отказаться как можно раньше от как можно большего числа заведомо неподходящих вариантов. Незначительные модификации метода перебора с возвратом, связанные с представлением данных или особенностями реализации, имеют и иные названия: метод ветвей и границ ( branch and bound ), поиск в глубину (depth first search ), метод проб и ошибок и т. д. Перебор с возвратом практически одновременно и независимо был изобретен многими исследователями еще до его формального описания. Он находит применение при решении различных комбинаторных задач в области искусственного интеллекта .

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

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

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

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

    Вычислительная схема перебора с возвратом

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

    Пусть M0, M1, . Mn-1 — n конечных линейно упорядоченных множеств и G — совокупность ограничений (условий), ставящих в соответствие векторам вида , булево значение < истина,ложь > . Векторы v=(v0,v1. vk) T , для которых G(v) = истина, назовем частичными решениями. Пусть, далее, существует конкретное правило P , в соответствии с которым некоторые из частичных решений могут объявляться полными решениями. Тогда возможна постановка следующих поисковых задач.

  • Найти все полные решения или установить отсутствие таковых.
  • Найти хотя бы одно полное решение или установить его отсутствие.
  • Общий метод решения приведенных задач состоит в последовательном покомпонентном наращивании вектора v слева направо, начиная с v0, и последующих проверках его ограничениями G и правилом P .

    В общем случае этот метод приводит к алгоритмам с экспоненциальной временной сложностью, а применяется он в основном к классу так называемых Np -полных задач ( задача коммивояжера , задача о рюкзаке и т. д.). Задачи этого класса эквивалентны друг другу в том смысле, что все они разрешимы недетерминированными алгоритмами полиномиальной сложности. Для них известно, что либо все они разрешимы , либо ни одна из них не разрешима детерминированными алгоритмами полиномиальной сложности. Иными словами, если хотя бы для одной из этих задач не существует детерминированного алгоритма, имеющего в худшем случае полиномиальную трудоемкость, то такие алгоритмы не должны существовать и для остальных задач этого класса. Наоборот, если хотя бы для одной из этих задач удалось найти детерминированный алгоритм , имеющий в худшем случае полиномиальную трудоемкость, то подобные алгоритмы существовали бы и для остальных задач этого класса и, более того, их можно было бы построить.

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

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

    Пример 1. Задача о расстановке ферзей на шахматной доске.

    Составьте рекурсивную функцию , находящую возможную расстановку n ферзей на шахматной доске размером nxn так, чтобы они не били друг друга ( n – натуральное число ).

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

    Алгоритм «Все расстановки»

    Шаг 1. Полагаем ( D — множество решений, j — текущий столбец для очередного ферзя).

    Шаг 2. Пытаемся в столбце j продвинуть вниз по вертикали или новый (если столбец j пустой), или уже имеющийся там ферзь на ближайшую допустимую строку. Если это сделать не удалось, то переходим к шагу 4.

    Шаг 3. Увеличиваем j на 1, то есть переходим к следующему столбцу. Если j 0, то выполняем шаг 2. Иначе вычисления прекращаем. Решения задачи находятся в множестве D , которое, может быть и пустым.

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

    Проведем параметризацию задачи. Введем четыре вспомогательных вектора: pos , ho, dd и du c длинами n, n, 2n-1 и 2n-1 соответственно. Использовать их будем следующим образом ( рис. 36.1):

  • hoi=1 , если на горизонтали с номером i (i=0,1. n-1) имеется ферзь, и hoi=0 — в противном случае;
  • dus=1 , если на диагонали с номером s (s=0,1. 2n-2) , идущей слева направо и снизу вверх, имеется ферзь, и dus=0 — в противном случае;
  • dds=1 , если на диагонали с номером s (s=0,1. 2n-1) , идущей слева направо и сверху вниз, имеется ферзь, и dds+1=0 — в противном случае;
  • pos j=i , если в позиции (i,j) (i,j=0,1. n-1) стоит ферзь.
  • Использование этих соглашений позволяет получить такие утверждения:

  • В позицию (i,j) можно поставить ферзь, если hoi+dui+j+ddn+i-j=0 .
  • Поставить ферзь в позицию (i,j) равносильно присваиваниям: hoi=1, dui+j=1, ddn+i-j=1 .
  • Убрать ферзь из позиции (i,j) равносильно присваиваниям: hoi=0, dui+j=0, ddn+i-j=0 .

Данное описание алгоритма является моделью решения общей задачи о нахождении всех вариантов расстановок. Рекурсия здесь осуществляется по не совсем стандартной схеме. В каждом рекурсивном вызове глубины j делается попытка поместить ферзь в некоторую позицию i столбца j (i,j=0,1. n-1) , а сам вызов соответствует переходу от работы с текущим столбцом к работе со следующим столбцом. При этом в начале вычислений и при переходах к любому последующему рекурсивному вызову параметр i меняется от нуля и далее с шагом, равным единице, пытаясь принять значение наименьшего номера поля, допустимого для установки ферзя. При переходах к любому предыдущему рекурсивному вызову параметр i продолжает изменяться от своего текущего на данном уровне значения с шагом, равным единице, также пытаясь принять значение наименьшего номера поля, допустимого для установки ферзя. Если в текущем столбце ферзь установить уже не удается, то создавшуюся ситуацию назовем тупиком. Попадание в тупик приводит к завершению текущего рекурсивного вызова, то есть к возврату к предыдущему столбцу и продолжению работы с ним. Иных случаев завершения рекурсивных вызовов не существует. Поэтому базой рекурсии мы должны считать совокупность всех тупиков. Заметим, что в данном случае элементы базы заранее до вычислений неизвестны.

После установки ферзя в одну из строк i последнего столбца i=n-1 формируется одно из решений задачи – при поиске одного варианта расстановки на этом этапе следует завершить выполнение алгоритма. При поиске всех расстановок вычисления прекращаются, когда мы попадаем в тупик при работе со столбцом 0. Полученные решения задачи, если они есть, возвращаются в виде столбцов матрицы otv , начиная от первого и далее.

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

На доске размера nxm (m=n,n-1. 0) требуется установить m ферзей так, чтобы они не били друг друга. При этом имеются некоторые клетки доски, на которые ферзь заведомо ставить нельзя. Множество этих «запретных» клеток обозначим через

Исходная задача есть . Проведем ее декомпозицию . Представим доску в виде двух частей: нулевого столбца (A) и оставшейся части (B) . Соответственно этому разбиению будем решать задачи и . Каждое из n возможных решений i (ферзь установлен в строке i=0,1. n-1 ) первой задачи однозначно определяет множество запретных клеток для второй задачи. При этом в попадают те клетки B , которые в «объединенной» доске бьет ферзь, установленный в строке i доски A . Пусть i зафиксировано и найдено множество d(i) решений второй задачи для доски B . Тогда расположение ферзя в строке i доски A и любое из полученных решений на B в совокупности дают различные решения otv(i) исходной задачи . Для получения всех решений этой задачи остается лишь взять объединение по i множеств otv(i) .

При анализе трудоемкости алгоритма получаем, что глубина рекурсии равна n 2 — при каждом рекурсивном вызове по j (j=0,1. n-1) происходит n рекурсивных вызовов по i (i=0,1. n-1) .

Пример 2. Задача о количестве расстановок ферзей на шахматной доске.

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

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

Пример 3. Задача об основных расстановках.

Для формулировки следующей задачи введем понятие. Среди всех расстановок n ферзей на доске nxn выделим отдельные непересекающиеся классы Hs (s=0,1. q) расстановок так, что все элементы данного класса можно получить из любого его представителя какими-либо элементарными преобразованиями типа:

  • поворот доски в ее плоскости вокруг центра на 90 , 180 и 270 ;
  • преобразования симметрии относительно диагоналей;
  • преобразования симметрии относительно прямых, проходящих через центр доски по границам клеток.
  • Взяв по одному представителю из каждого класса Hs (s=0,1. q) , получим некоторое множество, называемое основными расстановками. Составить рекурсивную функцию , находящую какое-либо множество основных расстановок n ферзей на шахматной доске размера nxn .

    Эта задача решается с помощью рекурсивных функций практически аналогично задаче из Примера 1. Отличия здесь такие. Рекурсивная функция последовательно формирует каждую из возможных расстановок ферзей на доске, но не все из них запоминаются в матрице ответа otv . Очередная полученная расстановка подвергается проверке — включать или не включать ее в матрицу otv . Делается это следующим образом. Из вектора pos описанными выше элементарными преобразованиями формируются еще семь расстановок (некоторые из них могут оказаться совпадающими). Если ни одна из них не входит в текущую матрицу ответов otv , то otv дополняется новым решением и так далее. Следовательно, по завершении вычислений otv будет содержать некоторое множество основных расстановок.

    Ключевые термины

    Возвратная рекурсия – это соединение метода перебора с возвратом и рекурсии.

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

    Исчерпывающий поиск – это процесс нахождения в некотором множестве всех возможных вариантов, среди которых имеется решение конкретной задачи.

    Метод решета – это один из методов организации исчерпывающего поиска, при котором из множества возможных вариантов исключаются все элементы, не являющиеся решениями.

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

    Перебор с возвратом (backtracking) – это один из методов организации исчерпывающего поиска, который строится конструктивно последовательным расширением частичного решения.

    Полное решение – это набор вариантов, образующий хотя бы одно решение в целом.

    Частичное решение – это неполный набор вариантов, который входит в одно или несколько полных решений.

    www.intuit.ru

    Алгоритмическая рекурсия — это по определению алгоритм, построенный по стратегии Разделяй-и-Властвуй (Divide-and-Conquer), в котором для хранения подзадач использована LIFO структура данных, т.е., попросту выражаясь, стек.

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

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

    Наличие обратного хода (backtracking) — отличительная черта именно рекурсивных алгоритмов. Т.е. в рекурсии всегда есть обратный ход. Вот, собственно, «при чем здесь рекурсия».

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

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

    В рекурсивном алгоритме расстановки N ферзей на шахматной доске подзадачей является задача расстановки оставшихся m ферзей ( m ), когда первые N — m ферзей уже как-то расставлены. Обратный ход в этом алгоритме используется тогда, когда мы вдруг выяснили, что подзадача не имеет решения — мы возвращаем этот результат на предыдущий уровень рекурсии в процессе обратного хода и тем самым говорим ему, что надо попробовать какой-то другой вариант расстановки N — m первых ферзей. А также, если вам поручено найти все возможные расстановки (а не какую-то одну), обратный ход рекурсии будет использоваться для тех же целей независимо от того, успешно или нет решена подзадача.

    ru.stackoverflow.com

    Основы программирования на C++, PASCAL

    Основы программирования

    Программирование на JAVA

    Программирование на C++

    Программирование на Pascal

    Задачи по программированию

    Путь движения по лабиринту будет отмечаться символами +.

    Например, приведенный выше рисунок (в середине) соответствует следующему заполнению матрицы LAB:

    Исходные данные — профиль лабиринта (исходная матрица LAB без крестиков); результат — все возможные траектории выхода из центральной точки лабиринта (для каждого пути выводится матрица LAB с траекторией, отмеченной крестиками).

    Алгоритм перебора с возвратом еще называют методом проб.

    Суть его в следующем:

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

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

    3. Если очередная клетка, в которую сделан шаг, оказалась на краю лабиринта (на выходе), то на печать выводится найденный путь.

    Программу будем строить методом последовательной детализации. Первый этап детализации:

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

    Запишем сначала общую схему процедуры без детализации:

    Для вывода найденных траекторий составляется процедура PRINTLAB.

    В окончательном виде программа будет выглядеть так:

    Еще один пример красивой программы с использованием рекурсивного определения процедуры (вспомните ханойскую башню!).

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

    kufas.ru

Популярное:

  • Приказ об аттестационной комиссии в колледже Приказ об аттестационной комиссии в колледже МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИХабаровского края от 20 октября 2014 года N 60 О создании аттестационной комиссии для проведения аттестации педагогических работников в целях установления […]
  • Госпошлина за удостоверение по аттестации Как уплачивается госпошлина за аттестацию в Ростехнадзоре Если ваша деятельность связана с опасным оборудованием и от лиц (работников предприятия) зависит промышленная безопасность, вам придется воспользоваться услугами […]
  • Опека и попечительство гражданское право шпаргалка Гражданское право, Гатин А.М., 2009 Гражданское право, Гатин А.М., 2009. Предлагаемое учебное пособие составлено в соответствии с требованиями и программой Государственного образовательного стандарта, утвержденного Министерством […]
  • Можно ли оформить доверенность на ипотеку Доверенность на продажу квартиры: виды и способы оформления Доверенность на продажу недвижимости представляет собой документ, в котором собственник (доверитель) передаёт свои полномочия на продажу недвижимости третьему (доверенному) […]
  • Расчитать стаж он Калькулятор подсчета страхового стажа Сегодня 24 июля 2018 г., 19:44 Посчитать стаж работы для больничного листа поможет онлайн калькулятор. Пособие по временной нетрудоспособности, а также пособие по беременности и родам рассчитывается […]
  • Как оформить карточку для получения пенсии Пенсия на карту Сбербанка Пенсионный Фонд перечисляет пенсию на лицевой счет сберкнижки на основании заявления пенсионера. Получать ее через кассу Сбербанка намного удобнее, в отличие от многочасового ожидания в очереди на почте. Поэтому […]
  • Когда пишется мягкий знак после шипящих правило Азбучные истины Интерактивный диктант Учебник ГРАМОТЫ: пунктуация Имена и названия. Интерактивный тренажер Полезные ссылки Летнее чтение Запоминалки Цитаты о языке Скороговорки Пословицы и поговорки Учебник ГРАМОТЫ: орфография Выберите […]
  • Проверка налогов инн яндекс ФССП - проверка задолженности На исполнении Федеральной службы судебных приставов (ФССП) России находятся десятки миллионов исполнительных производств в отношении физических лиц. Вовремя не уплаченные штрафы ГИБДД или налоги очень частая […]