Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 266
Текст из файла (страница 266)
Покажите, что коэффициент аппроксимации этого эвристического подхода равен Н(гз), где д — максимальный размер любого множества Яь 35.4. Наросочетание максимальной мощности Вспомним, что в неориентированном графе С паросочетанием называется такое множество ребер, в котором никакие два ребра не инцидентны одной и той же вершине. Из раздела 26.3 мы узнали, как найти максимальное паросочетание в двудольном графе.
В настоящей задаче будет выполняться поиск паросочетаннй в неориентированных графах общего вида (те. в графах, которые необязательно являются двудольными). а Максимальным наросочетанием (шахппа! шазс)ппя) называется паросочетание, которое ие является собственным подмножеством никакого другого паросочетания. Покажите, что максимальное паросочетание необязательно совпадает с паросочетанием максимальной мощности. Для этого приведите пример неориентированного графа С, максимальное паросочетание М в котором не является паросочетанием максимальной мощности. (Указание: имеется граф всего лишь с четырьмя вершинами, обладающий указанным свойством.) 6.
Рассмотрим иеориентированный граф С = (У,Е). Сформулируйте жадный алгоритм поиска максимального паросочетания в графе С, время работы которого было бы равно 0(Е). В этой задаче внимание сосредоточивается на поиске приближенного алгоритма с полиномиальным временем работы, позволяющего найти паросочетание максимальной мощности. Время работы самого быстрого из известных на сегодняшний день алгоритмов, предназначенных для поиска ларосочетания максимальной мощности, превышает линейное (хотя и является полиномиальным); рассматриваемый же здесь приближенный алгоритм завершает свою работу строго в течение линейного времени. Вы должны будете показать, что жадный алгоритм Глава 35.
УУрггбяяженьие алгоритмы поиска максимального паросочетания с линейным временем выполнения, разработанный в п. (б), для задачи о паросочетанин максимальной мощности является 2-приближенным алгоритмом. в. Покажите, что размер паросочетания максимальной мощности в графе С представляет собой нижнюю границу размера произвольного вершинного покрытия в этом графе. * Рассмотрим максимальное паросочетание М в графе С = ((г, Е). Пусть Т = (с е 1г: некоторое ребро в М ннцидентно оу . Что можно сказать о подграфе графа С, порожденном теми вершинами графа С, которые не принадлежат Ту д.
На основании результатов п. (г) сделайте вывод о том, что величина 2 ~М! равна размеру вершинного покрытия графа С. е. Воспользовавшись результатами решения пп. (в) и (д) задачи, докажите, что сформулированный в п. (б) жадный алгоритм является 2-приближенным алгоритмом дпя задачи о паросочетании максимальной мощности. 35.5. Раснисаниеработы наричлельной вычислительной машины В задаче о Раснисании Работы нараллельной вычислительной машины (рага1!е1-шасЫпе-зсйебп!шй ргоЫеш) исходные данные представляют собой набор из и заданий .Уз„)з,...,,У„, каждое из которых характеризуется временем обработки рь. Для выполнения этих заданий в нашем распоряжении имеется т идентичных машин МыМз,..., М .
Любое задание может выполняться на любой машине. Требуется составить раснисание, в котором для каждого задания Уь следует указать машину, на которой это задание будет выполняться, и выделенный ему интервал времени. Каждое задание .Уь должно непрерывно выполняться только на одной машине М, а течение времени ры и в это время на машине М; не может выполняться никакое другое задание. Обозначим через Сь время завершения (сошр!ейоп йше) задания Уь, т.е. момент времени, когда завершается обработка задания,Уь. Для каждого расписания определяется его момент завершения (Ша1СЕЗрал), раВНЫй С = ШаХЗ< сч СГ В ЗадаЧЕ НужНО НайтИ раСПИСаНИЕ С МИ- нимапьным моментом завершения.
Например, предположим, что имеется две машины, Мз и Мз, и что нужно выполнить четыре задания, Уы Уз,,Уз,.У4, для которых рз = 2„рз = 12, рз = 4 и р4 = 5. Можно предложить расписание, при котором на машине Мг сначала выполняется задание,Ум а затем — задание,Уз, а на машине Мз сначала выполняется задание,74, а затем — задание Уз. В этом расписании Сг = 2, Сз = 14, Сз = 9, С4 = 5 и С = 14. В оптимальном расписании на машине Мг выполняется задание .Уз, а на машине Мз — задания,Уы,Уз и,)4. В этом расписании С~ = 2, Сз = 12, Сз = б, С4 = 11 и С, = 12.
В данной задаче о расписании работы параллельной вычислительной машины обозначим время завершения оптимального расписания через С' 1190 Часть Г11 Избранные тены зь Покажите, что оптимальное время завершения по величине не меньше самого большого времени обработки, т.е. что выполняется неравенство С' > 1пах Рь. 1</с<н б. Покажите, что оптимальное время завершения по величине не меньше средней загрузки машин, т.е.
что справедливо неравенство Предположим, что для составления расписания параллельных вычислительных машин используется следующий жадный алгоритм: как толью машина освобождается, на ней начинает выполняться очередное задание, еще не внесенное в расписание. ж Предложите псевдокод, реализующий этот жадный алгоритм. Чему равно время работы этого алгоритма? * Покажите, что для расписания, которое возвращается жадным алгоритмом, выполняется неравенство 1 ч С, < — э рь+ шах рь пз 1<ьб 1<1<а Сделайте вывод, согласно которому этот алгоритм является 2-приближенным алгоритмом с полиномиальным временем работы.
35.б. Приближенное вычисление наибольшего вставного дерева Пусть С = (К Е) представляет собой неориентированный граф с различными весами ш(п, о) каждого ребра (и, о) Е Е. Пусть для каждой вершины зз е Ъ' величина гпах(п) = агяшах<„„~ и (ш(и, зз)) указывает ребро максимального веса, инцидентное этой вершине. Обозначим через Яо = (шах(о): о е 'ь") множество ребер с максимальным весом, инцидентных каждой вершине, и пусть Тсз представляет собой остовное дерево графа С с максимальным весом, т.е. остовное дерево с наибольшим общим весом. Для любого подмножества ребер Е' С Е определим ш(Е') = ~;~„„~ ш ш(и, о).
зь Приведите пример графа как минимум с четырьмя вершинами, для которого Ясз = То. б. Приведите пример графа как минимум с четырьмя вершинами, для которого Ясз ~ Тсз. в. Докажите, что Яо С Тс для любого графа С. д Докажите, что ш(Ясз) > ш(Тгз)12 для любого графа С. Глава 35. Приближенные алюритиы д. Разработайте алгоритм со временем работы 0(И + Е) для 2-приближенного вычисления наибольшего остовного дерева. 35. 7.
Приближенный алгоритм решения 0-1 задачи о рюкзаке Вспомним задачу о рюкзаке из раздела 16.2. Имеется и предметов, причем з'-й предмет стоит о, долларов и весит ло; килограммов. У нас есть рюкзак, вмещающий ие более И' килограммов. Добавим дополнительные предположения о том, что каждый вес ил не превышает Иг и что предметы проиндексированы в невозрастающем порядке их стоимости: о1 > оз » .
ои. В 0-1-задаче о рюкзаке требуется найти подмножество предметов, общий вес которого не превышает И', а суммарная стоимость максимальна. Непрерывная задача о рюкзаке подобна 0-1-задаче, но в ней позволено брать части предметов, а не руководствоваться принципом "все или ничего". Если мы берем долю х; предмета з, где 0 < х, ( 1, то мы добавляем х;и, к весу рюкзака и получаем стоимость х,оо Наша цель — разработать полиномиальный 2-приближенный алгоритм для решения 0-1 задачи о рюкзаке. Чтобы разработать алгоритм с полиномиальным временем работы, рассмотрим ограниченные экземпляры 0-1-задачи о рюкзаке. Для заданного экземпляра задачи о рюкзаке 1 мы образуем ограниченные экземпляры 1, где 5' = 1, 2,..., п, путем удаления предметов 1, 2,..., у — 1 и требования, чтобы решение включало предмет 5' (весь предмет 5 как в непрерывной задаче, так и в 0-1-задаче о рюкзаке).
В экземпляре Х1 не удаляются никакие предметы. Обозначим для экземпляра 1. через Р, оптимальное решение 0-1-задачи, а через ф — оптимальное решение непрерывной задачи. а. Докажите, что оптимальное решение экземпляра 1 0-1-задачи о рюкзаке является одним из ХРг, Рз,..., Р„). б. Докажите, что можно найти оптимальное решение ле. непрерывной задачи для экземпляра Х путем включения предмета 5 с последующим применением жадного алгоритма, в котором на каждом шагу мы берем максимально возможное количество невыбранного предмета из множества (5 + 1,5 + 2,..., и) с максимальной удельной стоимостью гч/зоы е. Докажите, что всегда можно построить оптимальное решение Я непрерывной задачи для экземпляра 1, которое включает не более одного разделенного на части предмета. То есть для всех предметов за исключением, возможно, одного мы либо полностью кладем этот предмет в рюкзак, либо полностью от него отказываемся. * Для заданного оптимального решения Я экземпляра 1; непрерывной задачи постройте решение лг из фз путем удаления разделенных на части предметов из ф.
Пусть о(Я) обозначает общую стоимость предметов в решении Я. Докажите, что о(Я ) > оЯ)/2 > о(Р )/2. !!9! Часть Ргк е!эаранные тены д. Разработайте алгоритм с полиномиальным временем работы, который возвращает решение с наибольшей стоимостью из множества [Вп Вз,..., В„], и докажите, что ваш алгоритм представляет собой полиномиальный 2-приближенный алгоритм для 0-1-задачи о рюкзаке. Заключительные замечания Несмотря на то что методы, которые необязательно вычисляют точные решения, были известны тысячи лет назад (например, методы приближенного вычисления числа к), понятие приближенного алгоритма имеет намного более короткую историю. Заслуги по формализации концепции приближенного алгоритма с полиномиальным временем работы Хохбаум (НосЬЬашп) [17Ц приписывает Гарею (багеу), Грэхему (бгаЬаш) и Ульману (()Пшап) [127], а также Джонсону (1оЬпвоп) [189].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
