🗊Презентация Построение и анализ эффективных алгоритмов

ПОСТРОЕНИЕ И АНАЛИЗ ЭФФЕКТИВНЫХ АЛГОРИТМОВ Глава 7, стр. 162

Типы рекурсивных алгоритмов Обычно рекурсивный алгоритм целесообразно разрабатывать при наличии одного из следующих условий: При необходимости обработки данных, имеющих рекурсивную структуру. Если алгоритм, обрабатывающий набор некоторых данных, можно построить, разбивая эти данные на части и получая из этих частичных решений решение на всей совокупности данных. Данный прием получил название "разделяй и властвуй". Если задача поставлена так, что ее решением является выбор какого-то варианта из некоторого множества возможных решений. Решение задачи определяется после некоторого конечного числа шагов так, что выбирая на каждом шаге вариант решения, мы удаляем часть информации из всей подлежащей обработке информации и пытаемся решить задачу на меньшем объеме данных. Поиск решения завершается в двух случаях: либо когда кончатся данные, либо когда находится решение на текущем наборе данных. В частности, таким методом обычно решаются NP-полные задачи. Если имеется рекурсивная схема некоторой функции. Существуют некоторые функции, которые легко можно определить рекурсивно, но которые нельзя определить в терминах обычных алгебраических выражений. Примером такой функции является функция Аккермана.

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

Пример. Вычисление факториала Формула факториала: n! =n*(n – 1)*(n – 2)*...*1 управляющий параметр - текущее значение числа n. Тривиальный случай представляет собой 0! = 1 декомпозиция общего случая n! = n*(n – 1)!

Пример. Поиск минимального Дано множество S, содержащее n целых чисел (n > 2). Найти минимальный элемент в этом множестве. Для простоты будем считать, что n есть степень числа 2. Применяя метод "разделяй и властвуй" разобьем множество S на два подмножества из n=2 элементов в каждом. Тогда достаточно найти минимальный элемент в каждом из полученных подмножеств и выбрать минимальное число из этих двух полученных: int MinEl(Vector S, int i, int n) // i - начальный элемент; n - число элементов { int ndiv2; ndiv2=n/2; if (n==2) then return min(S[i],S[i+1]) else return min( MinEl(S,i,ndiv2), MinEl(S,i+ndiv2,ndiv2) ); } Этот метод деления заданного множества на две равные части широко применяется для сокращения числа попарных сравнений.

Пример. Ханойские башни Легенда гласит, что в Великом храме города Бенарес, под собором, отмечающим середину мира, находится бронзовый диск, на котором укреплены 3 алмазных стержня, высотой в один локоть и толщиной с пчелу. Давным-давно, в самом начале времён, монахи этого монастыря провинились перед богом Брахмой. Разгневанный Брахма воздвиг три высоких стержня и на один из них возложил 64 диска, сделанных из чистого золота. Причём так, что каждый меньший диск лежит на большем. Как только все 64 диска будут переложены со стержня, на который Брахма сложил их при создании мира, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир. Количество перекладываний в зависимости от количества колец вычисляется по формуле Число перемещений дисков, которые должны совершить монахи, равно  18 446 744 073 709 551 615. Если бы монахи, работая день и ночь, делали каждую секунду одно перемещение диска, их работа продолжалась бы почти 585 миллиардов лет.

Алгоритм решения задачи Ханойские башни Назовем стержни левым (left), средним (middle) и правым (right). Задача состоит в переносе m дисков с левого стержня на правый. Задача может быть решена одним перемещением только для одного (m = 1) диска. Построим рекурсивное решение задачи, состоящее из трех этапов: перенести башню, состоящую из m – 1 диска, с левого стержня на средний; перенести один оставшийся диск с левого стержня на правый; перенести башню, состоящую из m – 1 диска, со среднего стержня на правый.

Алгоритм решения задачи Ханойские башни Обозначим тот стержень, с которого следует снять диски, через si, на который надеть – через sk, а вспомогательный стержень через sw. Оформим алгоритм решения задачи о переносе башни из n дисков с s1 на sk в виде процедуры move с четырьмя параметрами: n, si, sw, sk; алгоритм для n = 1 выделим в отдельную процедуру step, которая перемещает один диск со стержня si на sk.

Результат работы

Бинарные деревья Дерево – это граф, имеющий следующую структуру: Начальный узел (вершина) дерева называется корнем дерева Каждая вершина имеет не более двух потомков. Вершины дерева соединены направленными дугами, которые называют ветвями дерева. Листьями дерева называют вершины, в которые входит одна ветвь и не выходит ни одной ветви.

Рекурсивный алгоритм обхода бинарного дерева Прямой (корень – левое поддерево - правое поддерево); Обратный (левое поддерево – правое поддерево – корень) ; Симметричный  (левое – корень – правое)

Методы отсечения Самый прямолинейный подход при поиске решений методом полного перебора состоит в попытке перепробовать все различные ходы, пока не удастся получить решение. Многие из прикладных задач имеют чрезвычайно большие пространства состояний, поэтому методы полного перебора всех вариантов практически неработоспособны из-за временных ограничений. Один из способов ускорения поиска решения состоит в использовании оценочных функций для упорядочивания перебора вариантов. Оценочная функция должна обеспечивать возможность упорядочивания вершин — кандидатов на обработку — с тем, чтобы выделить ту вершину, которая с наибольшей вероятностью находится на лучшем пути к цели. Оценочные функции строятся на основе различных соображений и связаны с конкретной прикладной областью. Например: «Крестики-нолики», «Пятнашки»

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

Устранение рекурсии В общем случае к каждому алгоритму надо подходить индивидуально, моделируя те действия, которые выполняет рекурсивная программа, полученная в результате трансляции. Это означает, что в нерекурсивном эквиваленте рекурсивного алгоритма необходимо описать “магазин”, каждый элемент которого содержит: данные, являющиеся исходной информацией для рекурсивной процедуры; внутренние (локальные ) данные рекурсивной процедуры, если они есть. Каждое обращение к рекурсивной процедуре в нерекурсивной программе соответствует занесению информации в магазин. Каждый выход из рекурсии соответствует стиранию информации из магазина. Общая структура нерекурсивной программы соответствует циклу типа "while, который выполняется при условии, что магазин не пуст.

Динамическое программирование Рекурсивная техника полезна, если задачу можно разбить на подзадачи, каждая из которых решается за разумное время, т.е. суммарный размер задач будет небольшим. Из формулы оценки временной сложности вытекает, что если сумма размеров подзадач задачи размера n равна an для некоторой постоянной a > 1, то рекурсивный алгоритм, вероятно, имеет полиномиальную временную сложность. Но если разбиение задачи размера n сводит ее к n задачам размера n-1, то рекурсивный алгоритм, вероятно, имеет экспоненциальную сложность. В этом случае часто можно получить более эффективные алгоритмы с помощью специальной техники, называемой динамическим программированием. Суть динамического программирования основана на временном хранении в специальном массиве текущих решений на задачах предшествующих размеров.

Числа Фибоначчи

Жадные алгоритмы Жадный алгоритм (greedy algorithm) – это метод решения оптимизационных задач, основанный на том, что процесс решения задачи можно разбить на шаги, на каждом из которых принимается решение. Решение, принимаемое на каждом шаге, должно быть оптимальным только на текущем шаге, и должно приниматься вне зависимости от решений на других шагах. На каждом шаге «жадный» алгоритм выбирает локально оптимальное в том или ином смысле решение. Пример. Допустим, есть денежные купюры достоинством 10, 50, 100 и 500 рублей и нужно набрать 860 рублей.

Дискретная задача о рюкзаке Постановка задачи. В рюкзак загружаются предметы n различных типов (количество предметов каждого типа не ограничено). Максимальный вес рюкзака W. Каждый предмет типа i имеет вес wi и стоимость vi (i=1,2, ..., n). Требуется определить максимальную стоимость груза, вес которого не превышает W. Для решения задачи жадным алгоритмом, необходимо отсортировать вещи по их удельной ценности (то есть отношению ценности предмета к его весу), и поместить в рюкзак предметы с наибольшей удельной ценностью

При выборе правильного метода решения задачи необходимо ответить на вопросы: Насколько хорошо Вы понимаете проблему? Что представляют собой входные данные? Что должен представлять собой результат? Можно ли решить пример задачи на ограниченном малом объёме входных данных вручную? Каков реальный типовой размер задачи на практике (N=?). Какие условия и ограничения накладываются на время решения задачи? Что приемлемо: прямое решение простым алгоритмом или разработка специального эффективного алгоритма в течение какого-то времени. Определение класса к которому можно отнести задачу (комбинаторная, задача принятия решений, на графах и др.). Можно ли построить простой алгоритм или эвристику? Если ДА, то будет ли такой алгоритм корректным и какова его вычислительная сложность T(N)? Существует ли типовой алгоритм решения задачи данного класса? Существует ли какой-либо упрощенный вариант задачи, который можно решить сразу, если игнорировать некоторые входные параметры и ограничения задачи, допуская упрощенное представление форматов данных? Можно ли обобщить алгоритм решения упрощенного варианта задачи на всю задачу? Какой из стандартных методов разработки эффективных алгоритмов наиболее соответствует задаче?

Наиболее часто используются следующие методы: «Разделяй и властвуй» - метод декомпозиции, метод сведения задачи к подзадачам, метод частных целей. Динамическое программирование. «Жадный» алгоритм. Метод отсечений (программирование «с отходом назад», программирование с отслеживанием). Метод локального поиска (подъема). Метод эвристики. Метод рекурсии.