Алгоритмы с возвращением, их реализация с помощью рекурсий и динамических структур презентация

Алгоритмы с возвращением, их реализация с помощью рекурсий и динамических структур

Во многих задачах из разных областей ставятся вопросы типа: «Сколько существует способов…», «Подсчитайте количество элементов удовлетворяющих условию …», «Перечислите все возможные варианты», «Есть ли способ…» и т.д. Во многих задачах из разных областей ставятся вопросы типа: «Сколько существует способов…», «Подсчитайте количество элементов удовлетворяющих условию …», «Перечислите все возможные варианты», «Есть ли способ…» и т.д. Для того чтобы ответить на них обычно необходимо провести поиск в некотором множестве всех возможных вариантов, среди которых находятся решения данной задачи. Существуют два общих метода организации исчерпывающего поиска: перебор с возвратом и его логическое дополнение — метод решета.

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

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

Алгоритм поиска с возвращением Рассмотрим общий случай, когда решение задачи имеет вид вектора (а1, a2, …), длина которого (в общем случае) не определена, но ограничена сверху некоторым числом r, а каждое ai является элементом некоторого конечного линейно упорядоченного множества Ai. Таким образом, при исчерпывающем поиске в качестве возможных решений мы рассматриваем элементы множества A1×A2×…×Ai для любого i≤r, и среди них выбираем те, которые удовлетворяют ограничениям, определяющим решение задачи.

В качестве начального частичного решения берется пустой вектор () и на основе имеющихся ограничений выясняется, какие элементы из A1 являются кандидатами для их рассмотрения в качестве a1 В качестве начального частичного решения берется пустой вектор () и на основе имеющихся ограничений выясняется, какие элементы из A1 являются кандидатами для их рассмотрения в качестве a1 (множество таких элементов обозначим S1). В качестве a1 выбирается наименьший элемент множества S1, что приводит к частичному решению (a1). В общем случае ограничения, описывающие решения, говорят о том, из какого подмножества Sk множества Ak выбираются кандидаты для расширения частичного решения от (a1, a2,…, ak-1) до (a1, a2,…, ak).

Если частичное решение (a1, a2,…, ak-1) не предоставляет других возможностей для выбора нового ak Если частичное решение (a1, a2,…, ak-1) не предоставляет других возможностей для выбора нового ak (т.е. у частичного решения (a1, a2,…, ak-1) нет кандидатов для расширения), то происходит возврат и осуществляется выбор нового элемента ak-1 из Sk-1. Если новый элемент ak-1 выбрать нельзя, т.е. к данному моменту множество Sk-1 уже пусто, то происходит еще один возврат и делается попытка выбрать новый элемент ak-2 и т.д. Общую схему алгоритма, осуществляющего поиск с возвращением для нахождения всех решений, можно представить в следующем виде:

k:=1; k:=1; Вычислить S1 {Например, в качестве S1 взять A1}; While k>0 do Begin While не пусто Sk do Begin В качестве ak взять наименьший элемент из Sk, удалив его из Sk If (a1, a2,…, ak) является решением Then Вывести это решение If k<r then Begin k:=k+1; Вычислить Sk End; End; k:=k-1; {Возврат} End;

Более коротко общую процедуру поиска с возвращением можно записать в рекурсивной форме: Procedure ПОИСК (X: вектор; i:integer); Begin If X является решением Then вывести его; If i<=r Then Вычислить Si For all afrom Si do ПОИСК(XX, i+1) {XX получается из X добавлением элемента a} End; Вызов ПОИСК((), 1) находит все решения, причем все возвраты скрыты в механизме, регулирующем рекурсию.

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

Решение расстановки ферзей можно искать в виде вектора (a1, a2,…, a8), Решение расстановки ферзей можно искать в виде вектора (a1, a2,…, a8), где ai — номер вертикали (столбца), на которой стоит ферзь, находящийся в i-й горизонтали (строке), т.е. A1=A2=A3=…=A7=A8={1,2,3,4,5,6,7,8}. Каждое частичное решение — это расстановка N ферзей (где 1≤N≤8) в первых N горизонталях таким образом, чтобы эти ферзи не атаковали друг друга. Для первой строки множество возможных вариантов S1 совпадает со множеством всех вариантов А1. Но уже после установки первого ферзя, оно будет существенно отличаться от исходного (мы должны исключить из множества Si все клетки, которые находятся «под боем» уже поставленных i-1 ферзей).

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

Если все ферзи расставлены, то очередное решение выводится на экран и счетчик решений k увеличивается на 1. Если все ферзи расставлены, то очередное решение выводится на экран и счетчик решений k увеличивается на 1. В противном случае мы находим первую незанятую клетку в строке x, копируем матрицу a в b (чтобы не портить ее), и вызываем процедуру Fill_F, которая ставит ферзя на выбранное место и помечает все клетки, которые оказываются у него «под боем», а затем вызываем процедуру Set_F, уже для следующей строки x+1 и измененной матрицы b.

Домашнее задание 1. Составить опорный конспект лекции по теме «Алгоритмы с возвращением, их реализация с помощью рекурсий и динамических структур» на основе презентации. 2. Комбинаторика для программистов. Липский В. М.: «Мир», 1988, стр. 102-108.