Алгоритмические стратегии
Алгоритмические стратегии
Метод грубой силы (Исчерпывающий перебор)
Найти на конечном множестве X элемент x, удовлетворяющий совокупности условий K(x). Алгоритм: 1. Взять из множества X еще не рассмотренный элемент и проверить совокупность условие K(x). 2. Если какое-либо условие не выполнено, то перейти к п.1. 3. Если выполнены все условия, то x является решением. Если возможно несколько решений и требуется найти все их, то вернуться к п.1, пока не будут перебраны все элементы из множества X.
Метод грубой силы
Пример 1. Последовательный поиск элемента A в массиве A1, A2, …, An. В наихудшем случае (элемента в массиве нет или он находится на последнем месте) необходимо выполнить n сравнений T(n) = c*n, с – время одного сравнения. В среднем Tср(n) ~ c*n/2. В лучшем случае достаточно произвести только одно сравнение, когда элемент находится в начале массива.
Метод грубой силы
Пример 2. Сортировка выбором. Пример 3. Сортировка обменом (пузырьковая сортировка). Пример 4. Поиск подстроки. Дана символьная строка длиной n, называющаяся текстом, и строка длиной m (m<n), именуемая шаблоном, требуется найти в тексте подстроку, соответствующую шаблону. Алгоритм: совмещаем шаблон с началом текста и сравниваем их посимвольно. Если какие-то символы не совпали, сдвигаем шаблон на одну позицию вправо по тексту и повторяем сравнения. Сложность поиска Θ(n*m) в худшем случае.
Метод грубой силы
Пример 5. Поиск пары ближайших точек. Алгоритм: Вычисляем расстояние между каждой парой точек и находим пару с наименьшим расстоянием. Чтобы избежать повторного вычисления расстояния между одними и теми же точками, рассматриваем только точки (Pi, Pj), для которых i < j. Сложность такого алгоритма Ο(n²). Пример 6. Поиск выпуклой оболочки. Выпуклая оболочка множества точек S представляет собой наименьшее выпуклое множество, содержащее S. Алгоритм: Отрезок, соединяющий две точки множества принадлежит границе тогда и только тогда, когда все прочие точки лежат по одну сторону от прямой, проходящей через эти две точки. Сложность алгоритма Ο(n³).
Метод грубой силы
Пример 7. Счастливые билетики. Подсчитать число счастливых билетов, если номера билетов заданы к-значными десятичными числами. М – число вариантов, N – число счастливых билетов. k = 2, N = 10, M = 100 k = 4, N = 670, M = 10 000 k = 6, N = 55252, M = 1 000 000 k = 8, N = 4816030, M = 100 000 000 Получаем «комбинаторный взрыв», т.е. катастрофический рост числа
Метод грубой силы
Пример 8. Задача о рюкзаке. Дано n предметов весом w1,…,wn и ценой v1,…,vn, а также рюкзак, выдерживающий вес W. Требуется найти подмножество предметов, которое можно разместить в рюкзаке, и которое имеет при этом максимальную стоимость. Общее количество подмножеств n-элементного множества равно 2ⁿ, исчерпывающий перебор приводит к алгоритму со временем работы Ω(2ⁿ). Эта задача относится к NP-сложным задачам, для которых не доказано существуют или нет алгоритмы, решающие их за полиномиальное время.
Метод грубой силы
Пример 9. Задача о назначениях. Имеется n работников, которые должны выполнить n заданий, по одному заданию каждый. Стоимость выполнения i-ым работником j-го задания известна и равна C(i,j) – матрица стоимости. Надо распределить задания между работниками таким образом, чтобы они были выполнены с наименьшей стоимостью. Поскольку в этой задаче в общем случае количество рассматриваемых перестановок равно n!, исчерпывающий перебор непрактичен для всех, кроме очень небольших, значений n.
Метод декомпозиции
Пример 1. Сортировка слиянием. Алгоритм: Делим массив на две половины, рекурсивно сортируем каждую половину и сливаем два отсортированных массива в один отсортированный массив. Сложность такой сортировки Ο(n*log2n). Основной недостаток сортировки слиянием – необходимость дополнительной памяти, количество которой линейно пропорционально размеру входных данных. Сортировка слиянием возможна и без привлечения дополнительной памяти, но такая экономия памяти существенно ее усложняет, так что эта версия сортировки слиянием представляет сугубо теоретический интерес.
Метод декомпозиции
Пример 2. Быстрая сортировка. Алгоритм: Делим массив на две половины опорным элементом и переносим все элементы меньше опорного влево от него, а все элементы больше опорного вправо от него. Далее рекурсивно сортируем каждую половину массива. Сложность такой сортировки Ο(n*log2n) в среднем случае. Пример 3. Обходы бинарного дерева. Прямой порядок – сначала посещается корень дерева, а затем левое и правое поддерево. Симметричный порядок – корень посещается после левого поддерева, но перед посещением правого. Обратный порядок – корень посещается после левого и правого поддеревьев (в указанном порядке).
Метод декомпозиции
Пример 4. Поиск пары ближайших точек. Сложность алгоритма Ο(n*log2n) . Пример 5. Поиск выпуклой оболочки. Сложность алгоритма Ο(n²) – в наихудшем случае и Ο(n*log2n) – в среднем случае.
Метод уменьшения размера задачи
Уменьшение на постоянную величину. Уменьшение на постоянный множитель. Уменьшение переменного размера. Пример 1. Сортировка вставкой. Уменьшение размера задачи на единицу. Пример 2. Задача Иосифа. Уменьшение размера задачи на постоянный множитель. Иосиф предложил, чтобы все встали в круг и по очереди каждый убивал своего соседа (т.е. каждого второго), пока не останется один человек, который должен совершить самоубийство.
Метод уменьшения размера задачи
Пример 3. Поиск и вставка в бинарное дерево поиска. Уменьшение задачи переменного размера .
Метод преобразования
Пример 1. Сбалансированные деревья поиска. Пример 2. Пирамиды и пирамидальная сортировка.
Пространственно-временной компромисс
Пример 1. Хеширование. Пример 2. В-деревья.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
