Алгоритмические стратегии. Примеры задач выбора

Алгоритмические стратегии

Примеры задач выбора

Алгоритмические стратегии

• Метод грубой силы («исчерпывающий перебор»).
• Метод декомпозиции («разделяй и властвуй»).
• Метод уменьшения размера задачи («уменьшай и властвуй»).
• Метод преобразования («преобразуй и властвуй»).
• Пространственно-временной компромисс.
• Жадные методы.
• Динамическое программирование.
• Поиск с возвратом.
• Метод ветвей и границ.

Исчерпывающий перебор (метод грубой силы)

Найти на конечном множестве 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. Счастливые билетики.

Подсчитать число счастливых билетов, если номера билетов заданы к-значными десятичными числами. М – число вариантом, 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, N = 100 000 000 Получаем «комбинаторный взрыв»

Поиск с возвратом

• Пример. Маршрут шахматного коня.
• Дана шахматная доска n*n. Конь находится в верхнем левом углу доски. Нужно осуществить обход доски, посещая каждое поле ровно один раз.
• Алгоритм:
• С того поля, где конь находится, нужно перейти на любое поле, на котором он еще не был. Перейти к п.1.
• Если такого поля не существует, то вернуться назад на поле, с которого был сделан ход на данное. Перейти к п.1.

Метод проб и ошибок

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

«Жадные» алгоритмы

«Жадный» алгоритм делает на каждом шаге локально оптимальный выбор, - в надежде, что итоговое решение также окажется оптимальным. Пример. Задача о рюкзаке. Вор пробрался на склад, на котором хранятся n вещей. Вещь номер i стоит vi долларов и весит wi килограммов. Вор хочет украсть товара на максимальную сумму, причем максимальный вес, который он может унести в рюкзаке, равен W. Что он должен положить в рюкзак?

«Жадные» алгоритмы

Алгоритм: Сначала вор берет по максимуму самого дорогого товара; если весь этот товар кончился, а рюкзак не заполнен, вор берет следующий по цене товар, затем следующий и т.д. «Жадные» алгоритмы не всегда дают оптимальное решение.

«Жадные» алгоритмы

Пусть Вещь 1 весит 10 кг и стоит 60 $, 6 $/кг Вещь 2 весит 20 кг и стоит 100 $, 5 $/кг Вещь 3 весит 30 кг и стоит 120 $, 4 $/кг Вор может унести рюкзак весом 50 кг. «Жадный» алгоритм даст: Вещь 1 + Вещь 2 = 160 $ Это решение не оптимально, т.к. например: Вещь 1 + Вещь 3 = 180 $ Вещь 2 + Вещь 3 = 220 $ Если последовательность жадных выборов дает глобально оптимальное решение, то говорят, к задаче применим «принцип жадного выбора».

«Жадные» алгоритмы

• Пример. Задача о выборе заявок.
• Пусть даны n заявок на проведение занятий в одной и той же аудитории. i-е занятие должно проходить в промежутке времени [si, fi ]. Нужно набрать максимальное количество совместимых друг с другом заявок.
• Алгоритм:
• Упорядочим заявки в порядке времени возрастания времени окончания
• Первой возьмем первую заявку.
• Далее берем заявки по очереди и оставляем ту, начало которой позже окончания первой и т.д.
• Докажите, что алгоритм приведет к оптимальному решению.

Динамическое программирование

Подобно методу «разделяй и властвуй», динамическое программирование решает задачу, разбивая ее на подзадачи и объединяя их решения. Но динамическое программирование применимо тогда, когда подзадачи не являются независимыми. Пример. Список приглашенных. Вам поручили устроить веречинку на фирме, структура которой иерархична: отношение подчиненности задано деревом, корень которого – директор. У каждого сотрудника есть свой рейтинг. Директор распорядился, чтобы никто не оказался вместе со своим непосредственным начальником. Требуется составить список приглашенных с наибольшим суммарным рейтингом.