greedyalgs (1238885)

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

Текст из файла

ЖАДНЫЕ АЛГОРИТМЫИдеи и применимость жадных алгоритмов. Графы и представленияграфов. Матроиды и алгоритм Радо-ЭдмондсаСоставляем число из разрядов•Простая задача: из десятичных разрядов числа нужно составить наибольшеевозможное число•Например для цифр 1, 3, 9, 3, 4 и 2 ответом будет 943321•Что насчёт цифр 6, 8, 7, 3, 8, 6?•Задумайтесь на секунду: как именно вы получили ответ? Почему вы уверены,что он правилен?Жадные алгоритмы•Составляя число из разрядов, вы, вероятно, прибегали к следующемужадному алгоритму:1.2.Выбираем наибольший из имеющихся разрядов и ставим его первымЕсли разряды ещё остались, переходим к шагу 1.•Это главные ингредиенты жадного алгоритма: безопасный шаг выбораследующего элемента и подобие в структуре оставшейся подзадачи•Каждый раз безопасный шаг соответствует локально оптимальному выборуРазмен монет•Иногда жадный шаг не является оптимальным•Разменять сумму монетами с номиналами 1 , 2 , … , выбрав наименьшеечисло монет•Пример: разменять 6 рублей монетами с номиналами 4, 3 и 1•Жадное решение: взять 4, потом 1, потом опять 1•Оптимальное решение: взять 3 и 3•В этом случае говорят, что локально-оптимальный шаг не являетсябезопасным шагом и нужно пользоваться другими методамиОбсуждение•В принципе для размена жадный алгоритм даёт какое-то решение.

Неоптимальное, но вообще-то далёкое от наихудшего•Может ли быть такое, что, для определённого набора монет, жадныйалгоритм даст оптимальное решение?Перевод в двоичную систему•Перевод в двоичную систему является частным случаем задачи разменамонет. Только теперь вы должны оптимальным способом разменять число «монетами» с номиналами 1, 2, 4, 8, 16, …•Например 25 = 16 + 8 + 1 = 8 + 8 + 4 + 4 + 2 + 1•Алгоритм для оптимального размена прост: берём в качестве следующегоразряда ÷ 2 и переходим к Τ2•25 → 12 → 6 → 3 → 1•1, 0, 0, 1, 1 → 11001•Является ли это жадным алгоритмом? Какой тут безопасный шаг? Есть ли тутподобие подзадач?Обсуждение•Интересно, что жадный алгоритм будет работать оптимально для разменалюбой суммы монетами с номиналами 10, 5, 2 и 1•Есть ли у вас гипотеза в чём принципиальная разница между множествамимонет для которых жадный алгоритм работает оптимально и не оптимально?•Не оптимально: {4, 3, 1}, {10, 7, 2, 1}•Оптимально: {4, 2, 1}, {10, 5, 2, 1}Обсуждение•Интересно, что жадный алгоритм будет работать оптимально для разменалюбой суммы монетами с номиналами 10, 5, 2 и 1•Есть ли у вас гипотеза в чём принципиальная разница между множествамимонет для которых жадный алгоритм работает оптимально и не оптимально?•Не оптимально: {4, 3, 1}, {10, 7, 2, 1}, {9, 4, 1}, {25, 15, 1}•Оптимально: {4, 2, 1}, {10, 5, 2, 1}, {9, 5, 1}, {25, 15, 10, 5, 1}•Добавленные примеры показывают, что эта задача гораздо сложнее, чемкажется.

Отложим её пока чтоProblem EV: степени четверки•Напишите функцию, которая оптимально раскладывает число n поограниченному количеству степеней четверки 40 , 41 , и т. д. до 4включительно•Каждая степень считается одной монетой.Например 27 = 1*16 + 2*4 + 3*1 использует 6 монет.В то же время 27 = 1*16 + 1*4 + 7*1 использует 9 монетunsigned powers_four(unsigned n, unsigned m);•Функция должна возвращать минимальное количество монетunsigned res = powers_of_four(13, 1);assert(res == 4); // 3*4 + 1*1Problem EG: египетские дроби•Египетской дробью называется дробь, имеющая в числителе 1•Каждое число может быть разложено на египетские дроби жаднымалгоритмом, который выбирает наибольшую дробь на каждом шаге39• Например:50•=121+411+ +341700Напишите функцию, которая берёт числитель и знаменатель и возвращаетвыделенный в динамической памяти массив знаменателей и его размерstruct denom_array_t { unsigned *arr; unsigned sz; };struct denom_array_tegyptian_fractions(unsigned num, unsigned den);Выбор подмножества интервалов•Необходимо выбрать максимальное подмножество непересекающихсяинтервалов на прямой (показано красным)•Известно, что для этого есть жадный алгоритмНеочевидные жадные шаги•Структура жадного алгоритма не всегда очевидна•Какие жадные шаги можно сделать для выбора множества интервалов?•Выбирать первый слева?•Выбирать самый короткий?•Выбирать самый длинный?Контрпримеры•Первый слева•Самый короткий•Самый длинный (см.

контрпример первому слева)•Первый справа (см. контрпример первому слева)•У вас есть ещё идеи?Правильный жадный шаг•Нужно первым брать тот, который первым заканчивается•Этот шаг является безопасным и локально оптимальным: если мы возьмёминой интервал, то он не пересечёт меньшего числа интервалов•Получающаяся подазадача после этого шага подобна исходнойProblem IC: расписание аудитории•Для конкретной аудитории есть ряд заявок с временем начала окончания•Необходимо вернуть максимальное количество допустимых заявокstruct intvl_t { int number; int start; int fin; };int schedulemax(struct intvl_t *reqs, int nreqs) {// TODO: ваш код здесь}•Это та самая задача выбора подмножества интервалов, котораярассматривалась вышеProblem RU: ларьки под общую крышу•На прямой расположены отрезки , которые полностью или даже сизбытком покрывают интервал , •Ваша задача обратна проблеме IC: теперь вам нужно выбрать наименьшеемножество отрезков так, чтобы они всё ещё покрывали интервалint covermin(int L, int R, struct intvl_t *intervs, int ncovs) {// TODO: ваш код здесь}Problem JA: распределение работы•У вас есть totaltime дней и n заказов, каждый из которых займёт один день.

Укаждого заказа есть номер, стоимость и дедлайн. Каждый заказ можноначинать в любой день до делайна, одновременно можно делать только одинJobIdABCDEDeadline21213Profit4025301520CAEstruct order_t { int number; int cost; int deadline; };struct answer_t { int norders; int *numbers; };struct answer_tbetforjobs(struct order_t * orders, int n, int totaltime);•Вы должны выбрать наилучшее по суммарной стоимости число заказовProblem PC: покрытие точек отрезками•У вас есть n точек с целыми координатами на прямой.

Их необходимо покрытьотрезками длины unitlen, используя минимальное количество отрезков (вашзапас отрезков в этой задаче неограничен, но все они одинаковые)•Нужно вернуть количество использованных отрезковint coverpoints(int *pts, int n, int unitlen) {// TODO: ваш код здесь}Problem FP: организация утренника•Вам нужно организовать детский утренник на которых пришло nkids детей.У каждого ребёнка есть номер id и возраст age•Вы хотели бы получить минимальное количество групп, но при этом возрастдетей в каждой группе не должен отличаться больше, чем на 2 годаstruct kid_t { int id; int age; };struct kidgroup_t { int nkid; int ngroup; };struct answer_t { int ngroups; struct kidgroup_t *mapping; };struct answer_tfunparty(struct kid_t *kids, int nkids) {// TODO: ваш код здесь}•Сможете ли вы свести эту задачу к Problem PC?Графы•Графом (V, E) называется множество вершин V, соединённых множеством рёбер E•Можно думать о вершинах как о городах,а о рёбрах как о дорогах•Или о вершинах как о числах, а о рёбрах,как о парах чисел•Или о вершинах как о котиках, а о рёбрахкак о признаке совместного появлениядвух котиков на одной фотке•У вершин и рёбер могут быть дополнительные признаки, например здесь укаждого ребра показан его весПредставления графов•Самое простое предcтавление графа это просто список его рёбер•Такое представление хорошо для сброса в человеко-читаемый файл нонепрактично для операций над графом4013031134236Представления графов•Граф может быть представлен двумерным массивом который называетсяматрицей смежности•Если у рёбер есть веса, то в матрице смежности легко ставить веса вместоединиц40130311342360301300400061460Остовные деревья•Деревом в теории графов называется ненаправленный ациклический граф•Ниже изображён граф со взвешенными рёбрами и некоторые его остовные деревьяОбсуждение•Как можно понять, что некий неориентированный граф является деревом?Обсуждение•Как можно понять, что некий неориентированный граф является деревом?•Самый простой способ это поиск в ширину, использующий массив родителей•Изначально для всех вершин устанавливаем = −1•Берём любую вершину и для всех её соседей устанавливаем = •Рекурсивно вызываем ту же функцию для каждого из соседей отмечая кактекущего родителя•Как только найдётся сосед не совпадающий с её текущим родителем иимеющий родителя, не совпадающего с , цикл найден и это не деревоProblem GL – петля в графе•40012Вам задан неориентированный граф как количество вершин и потом списокрёбер с весами13333146•Выдайте на выход 1 если цикл любой длины есть и 0 если его нет•В данном случае петля естьОбсуждение•Каждый раз, когда мы проверяем таикм образом цикличность, мы строимдерево, которой, при успешном построении будет остовным•Как найти минимальное остовное дерево?•Удивительно, но для этого есть жадный алгоритм, целых дваЖадные алгоритмы на графах•Самый известный из жадных алгоритмов на графах это поиск минимальногоостовного дерева во взвешенном графе (алгоритм Краскала)•Жадный шаг: берётся ребро с минимальным весом и добавляется в остовноедерево, если при этом не создаёт там цикла•На рисунке выбраны рёбра с весами 1, 2 и 3.

Далее ребро с весом 4 добавитьнельзя, так как образуется циклЖадные алгоритмы на графах•Самый известный из жадных алгоритмов на графах это поиск минимальногоостовного дерева во взвешенном графе (алгоритм Краскала)•Жадный шаг: берётся ребро с минимальным весом и добавляется в остовноедерево, если при этом не создаёт там цикла•Поэтому берётся ребро с весом 5, после чего остовное дерево готовоДомашняя работа HWG•Считайте со стандартного ввода имя файла, в котором граф задан как списокрёбер.

Например граф с прошлого слайда50123•14343 0 4 14 1 2 52 2 4 67Реализуйте на языке C алгоритм Краскала для поиска минимальногоостовного дерева. Напечатайте в stdout вес найденного дерева, в данномслучае результат это 11Жадные алгоритмы: скрытая структура•Обратим внимание на интересное свойство ациклических подграфов•Если в одном ациклическом подграфе меньше рёбер, чем в другом, то вбольшем всегда можно найти ребро, чтобы добавить в меньший, сохранивего ацикличностьЖадные алгоритмы: скрытая структура•Обратим внимание на интересное свойство ациклических подграфов•Если в одном ациклическом подграфе меньше рёбер, чем в другом, то вбольшем всегда можно найти ребро, чтобы добавить в меньший, сохранивего ацикличность.

Иногда даже не одноМатроиды•Матроидом I называется система множеств, в которой1.Пустое множество принадлежит I2.Если множество принадлежит I, то все его подмножества принадлежат I3.Если одно из принадлежащих I множеств больше другого по мощности, вбольшем всегда найдётся такой элемент, который можно добавить вменьшее так, чтобы меньшее множество с добавленным элементом тожепринадлежало I•Все множества, входящие матроид состоят из элементов носителя матроида•Базой матроида называется максимальное по включение множество в нёмАлгоритм Радо-Эдмондса•Пусть дан матроид I, c носителем X, в котором каждому элементу сопоставлен вес , а каждое входящее в матроид множество имеет весравный сумме весов своих элементов•Алгоритм Радо-Эдмондса ищет в матроиде базу минимального веса, делаякаждый раз жадный шаг, выбирая следующий элемент с наименьшим весом0 = ∅ = −1 + , где = min ∈ ∖ −1 | −1 + ∈ •Любой жадный алгоритм на конкретном матроиде, например алгоритмКраскала, это всего лишь специализация этого общего алгоритмаВернёмся к проблеме JA•У Кормена есть замечательный анализ проблемы JA (см.

ранее)JobIdABCDEDeadline21213Profit10027251925•Назовём выполнимыми множества работ, которые можно сделать безпросрочки дедлайна. Например {B, A, E} или {D, C} выполнимы•Тогда можно проверить, что условия матроида выполняются для системвыполнимых множеств•Тот жадный алгоритм, которым вы решали эту задачу, это тот же алгоритм,который ищет остовные деревья в графе (фантастика)Вернёмся к монетам•Выполним следующие операции:1.Разменяем жадным алгоритмом и посмотрим сколько получилось монет2.Рассмотрим все частичные размены не более чем по столько монет•Например для 6 монет и разменного множества {4, 3, 1}•Имеем частичные размены не более чем по 3 монеты:{4, 1, 1}, {3, 3, 1}, {3, 1, 1},{1, 1, 1},{4, 1}, {3, 1}, {3, 3}, {1, 1}, {4}, {3}, {1}•Они не образуют матроид ([aug] нарушается для {4, 1, 1} и {3, 3})•Значит жадный алгоритм для этого разменного множества не работаетВернёмся к монетам•Выполним следующие операции:1.Разменяем жадным алгоритмом и посмотрим сколько получилось монет2.Рассмотрим все частичные размены не более чем по столько монет•Например для 6 монет и разменного множества {4, 2, 1}•Имеем частичные размены не более чем по 3 монеты:{4, 2, 1}, {2, 2, 1}, {4, 1, 1}, {2, 1, 1}, {1, 1, 1},{4, 1}, {2, 1}, {2, 2}, {1, 1}, {4}, {2}, {1}•Они образуют матроид•Значит жадный алгоритм для этого разменного множества работаетБольше о матроидах•На самом деле матроилды это удивительные комбинаторные объекты•Они имеют странную связь с графами, в частности с планарными графами•У них масса обобщений, разной степени обобщённости•Через матроиды устанавливаются криптоморфизмы между различнымидискретными структурами•Подробнее можно почитать в (для математически настроенной частиаудитории)Литература•С11 ISO/IEC – "Information technology –Programming languages – C", 2011• Thomas H.

Cormen – Introduction toAlgorithms, 2009• Gordon, McNulty – Matroids, A GeometricIntroduction, 1993• Klappenecker – Theory of Greedy Algorithms• Новиков, Поздняков «Жадные алгоритмы»• Алексеев, Таланов , «Графы и алгоритмы»,онлайн-курс, Intuit.

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций