Алгоритмы - построение и анализ (1021735), страница 246
Текст из файла (страница 246)
Для этого приведите пример неориентированного графа С, максимальное паросочетание М в котором не является паросочетанием максимальной мощности. (Имеется граф всего лишь с четырьмя вершинами, обладающий указанным свойством.) б) Рассмотрим неориентированный граф С = (К Е). Сформулируйте жадный алгоритм поиска максимального паросочетания в графе С, время работы которого было бы равно 0 (Е).
В этой задаче внимание сосредотачивается на поиске приближенного алгоритма с полиномиальным временем работы, позволяющего найти паросочетание максимальной мощности. Время работы самого быстрого из известных на сегодняшний день алгоритмов, предназначенных для поиска паросочетания максимальной мощности, превышает линейное (хотя и является полиномиальным); рассматриваемый же здесь приближенный алгоритм завершает свою работу строго в течение линейного времени. Вы должны будете показать, что жадный алгоритм поиска максимального паросочетания с линейным временем выполнения, разработанный в части б, для задачи о паросочетании максимальной мощности является 2-приближенным алгоритмом.
Глава 35. Приближенные алгоритмы 1185 в) Покажите, что размер паросочетания максимальной мощности в графе С представляет собой нижнюю границу размера произвольного вершинного покрытия в этом графе. г) Рассмотрим максимальное паросочетание М в графе С = (1г, Е). Пусть Т = (о е Р': неюторое ребро из М инцидентно о) . Что можно сказать о подграфе графа С, порожденном теми вершинами графа С, которые не принадлежат Т'7 д) На основании результатов части г обоснуйте вывод о том, что величина 2 1М~ равна размеру вершинного покрытия графа С. е) Воспользовавшись результатами решения частей в и д задачи, докажите, что сформулированный в части б жадный алгоритм является 2-приближенным алгоритмом для задачи о паросочетании максимальной мощности. 35-5.
Расписание работы параллельной вычислительной машины В задаче о расписании работы параллельной вычислительной машины (рога!1е1-шас!ппе-зследп!1п8 ргоЫеш) исходные данные представляют собой набор из и заданий .Уз, .Уз,..., У„, каждое из которых характеризуется временем обработки ры Для выполнения этих заданий в нашем распоряжении имеется т идентичных машин Мы Мз,..., Мт. Нужно составить расписание, в ютором для каждого задания Уь следует указать машину, на которой это задание будет выполняться, и выделенный ему интервал времени. Каждое задание должно непрерывно выполняться только на одной машине М; в течение времени ры и в это время на машине М; не может выполняться никакое другое задание. Обозначим через Сь время завершения (сошр!ейоп 11ше) задания,4, т.е.
момент времени, когда прекращается обработка задания .7ь. Для каждого расписания определяется его момент завершения (ша1сезрап), равный С = шахзс <„С . В задаче нужно найти расписание с минимальным моментом завершения. Например, предположим, что имеется две машины Мз и Мз и что нужно выполнить четыре задания Уы Уз, Уз,.74, для юторых рз = 2, рз = 12, рз = 4 и р4 — — 5. Можно предложить расписание, при котором на машине Мг сначала выполняется задание .Уы а затем — задание Уз, а на машине Мз сначала выполняется задание У4, а затем — задание,Уз.
В этом расписании Сг = 2, Сз = 14, Сз = 9, С4 = 5 и С =14. В оптимальном расписании на машине Мг выполняется задание,Уз, а на машине Мз— задания.7ы,7з и Х~. В этом расписании С~ = 2, Сз = 12, Сз = 6, С4 = 11 иС =12. Часть П. Избранные темы 1186 В данной задаче о расписании работы параллельной вычислительной машины обозначим через С„; время завершения оптимального расписания. а) Покажите, что оптимальное время завершения по величине не меньше самого большого времени обработки, т.е. что выполняется неравенство С' > шах рь.
14/с~п б) Покажите, что оптнмальное время завершения по величине не мень- ше средней загрузки машин, т.е. что справедливо неравенство 1 С" ) — ,'1 р,. 1~ь4в Предположим, что для составления расписания параллельных вычислительных машин нспользуется следующий жадный алгорнтм: как толью машина освобождается, на ней начинает выполняться очередное задание, еще не внесенное в расписание. в) Предложите псевдокод, реализующий этот жадный алгоритм. Чему равно время работы этого алгорнтма? г) Покажите, что для расписания, которое возвращается жадным алгоритмом, выполняется неравенство 1 Сыы, < — Г рь+ шах рь. т 1Ф<п Обоснуйте вывод, согласно которому этот алгоритм является 2-прнблнженным алгоритмом с полнномнальным временем выполнения.
Заключительные замечания Несмотря на то, что методы, которые не обязательно вычисляют точные решення, были известны несколыю тысяч лет назад (напрнмер, методы приближенного вычисления числа я), понятие приближенного алгоритма имеет намного более короткую историю. Заслуги по формализации концепцнн приближенного алгоритма с полнномнальным временем работы Хохбаум (НосЬЬашп) приписывает Гарею (Оагеу), Грэхему (ОгаЬаш) н Ульману ((Л!шап) [1091, а также Джонсону (1оЬпзоп) [1бб1.
Первый такой алгоритм (ему посвящена задача 35-5) часто приписывается Грэхему [1291. Глава 35. Приближенные алгоритмы 1187 Со времени публикации этой ранней работы были разработаны тысячи приближенных алгоритмов, позволяющих решать самые разнообразные задачи.
По этой теме имеется большое юличество литературы. Недавно вышедшие книги Осиэлло (Аияе11о) н др. [25), Хохбаума [149) и Вазирани (чахпаш) [305] полностью посвящены приближенным алгоритмам. Это же можно сказать об обзорах Шмойса (БЬшоуз) [277) и Клейна (К!еш) и Юнга (Уоипй) [18Ц. В нескольких других книгах, таких как книги Гарея и Джонсона [110], а также Пападимитриу (Рарайш1птои) и Штейглица (Бге!81йк) [237], также значительное внимание уделяется приближенным алгоритмам. В книге Лоулера (Ьаж!ег), Ленстры (Ьепзпа), Ринноя Кана (В!ппооу Кап) и Шмойса [197] подробно рассматриваются приближенные алгоритмы, предназначенные для задачи о юммивояжере. В книге Пападимитриу н Штейглица авторство алгоритма АРРКОХ ЧЕКТЕХ Сочен приписывается Ф.
Гаврилу (Р. Оачп1) и М. Яннакакису (М. Уаппайа!аз). Большое количество усилий было направлено на исследование задачи о вершинном покрытии (в книге Хохбаума [149] приведено 16 различных приближенных алгоритмов, предназначенных для решения этой задачи), однаю значение всех коэффициентов аппроксимации не меньше 2 — о (1).
Алгоритм АРРкох ТБР Толк был предложен в статье Розенкранца (Возеп1сгапгх), Стирнса (Б1еатпз) и Льюиса (Ьетч!з) [26 Ц. Кристофидис (СЬпзгоЫез) усовершенствовал этот алгоритм и предложил 3/2-приближенный алгоритм, позволяющий решить задачу о коммивояжере с неравенством треугольника.
Арора (Агота) [2Ц и Митчелл (МйсЬе!1) [223) показали, что если точки находятся на евклидовой плосюсти, то существует схема аппроксимации с полиномиальным временем работы. Теорема 35.3 доказана Сани (БаЬп!) и Гонзалезом (Оопга1ег) [264]. Анализ жадного эвристического подхода к задаче о покрытии множества построен по аналогии с доказательством более общего результата, опубликованном в статье Чватала (СЬчага!) [6 Ц; представленный здесь основной результат доказан Джонсоном [166] и Ловасом (Ьочазх) [206). Описание алгоритма АРРкох Бивзет Бом и его анализ с неюторыми изменениями взяты из статьи Ибарры (1Ьапа) и Кима (Кпп) [164], где приведены приближенные алгоритмы, предназначенные для решения задач о рюкзаке и о сумме подмножества.
Рандомизированный алгоритм решения задачи о МАХ-3-СЬ!Р выполнимости можно найти в неявном виде в работе Джонсона [166]. Автором алгоритма, предназначенного для решения задачи о взвешенном вершинном покрытии, является Хохбаум [148). Раздел 35.4 дает лишь поверхностное представление о тех возможностях, которые открываются благодаря использованию рандомизации и линейного программирования при разработке приближенных алгоритмов. Сочетание этих двух идей привело к появлению метода под названием "рандомизированное округление", в котором задача сначала формулируется как целочисленная задача линейного программирования.
После этого решается ослабленный вариант задачи, 1188 Часть ЧП. Избранные темы а переменные в этом решении интерпретируются как вероятности. Затем эти вероятности используются для решения исходной задачи. Впервые этот метод был предложен Рагаваном (Ка8Ьачап) и Томсоном (ТЬошрзоп) [2551, после чего он нашел широкое применение. (Для ознакомления с этой темой см. обзорную статью Мотвани (Моияал(), Наора (Хаог) и Рагавана [2271.) К другим заслуживающим внимания идеям в этой области, предложенным в последнее время, относится метод прямой двойственности (рпша1 биа1) (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
