177523

Алгоритм 1.

Для построения приближенного алгоритма будем использовать жадный алгоритм. Для этого, по аналогии с задачей о рюкзаке, отсортируем список предметов в порядке убывания их размеров, и будем последовательно дополнять предметы к пустому множеству в соответствии с упорядочением. Если очередной предмет при добавлении к множеству приводит к тому, что суммарный объем предметов, входящих в сгенерированное множество превышает L, то отбрасываем его и переходим к рассмотрению следующего предмета упорядоченного списка. Описанный процесс продолжаем до тех пор, пока суммарный размер предметов множества не станет равным L или будет исчерпан упорядоченный список объектов.

Пример 2 . 4 . Объемы предметов ai приведены в таблице 2.2. Пре-

дельная сумма объемов предметов множества равна L=55. Необходимо найти такой набор предметов, сумма размеров которых была бы наиболее близка к L.

Таблица 2.2

Так как емкость множества 55, то мы сможем добавить в него в соответствии с нашим алгоритмом 3 предмета с объемами: 27, 22 и 1. Общий объем сгенерированного множества – 50. Это решение не является оптимальным, так как существует лучшее решение, которое дают предметы с объемами 22, 14, 11, 7 и 1. В этом случае объем – 55, т. е. данное решение является оптимальным.

Алгоритм 2.

Рассмотрим еще один алгоритм, который также является жадным при каждом из своих проходов.

1. На первом проходе этот алгоритм начинает с пустого множества и добавляет в него элементы из упорядоченного по убыванию объемов списка предметов. Если очередной предмет при добавлении к множеству приводит к тому, что суммарный объем предметов, входящих в сгенерированное множество превышает L, то отбрасываем его и переходим к рассмотрению следующего предмета упорядоченного списка. Описанный процесс продолжаем до тех пор, пока суммарный размер предметов множества не станет равным L или будет исчерпан упорядоченный список объектов.

42

2.На втором проходе алгоритм начинает свою работу со всевозможных одноэлементных множеств и добавляет к ним, аналогично первому проходу, элементы из упорядоченного по объемам списка предметов.

3.На третьем проходе алгоритм аналогичным образом исследует все трехэлементные множества и т. д.

Количество проходов алгоритма ограничено временем, отведенным на работу алгоритма. Если время позволяет, то на n +1 проходе, где n – количество предметов, алгоритм построит оптимальное решение (если оно не будет построено ранее, например, на некотором проходе сумма элементов сгенерированного множества совпадет с L).

Пример 2.5. Для приведенного в таблице 2.2 примера (упорядоченность: 27, 22, 14, 11,7,1) уже на втором проходе будет построено оптимальное решение задачи (Таблица 2.3).

43

2.5. Приближенный жадный алгоритм для задачи о раскраске графа

Требуется определить минимальное количество цветов с, в которые можно раскрасить вершины графа так, чтобы концы каждого ребра графа были окрашены в разные цвета.

Для данной задачи доказано, что число красок, даваемое лучшим приближенным полиномиальным алгоритмом, более чем вдвое превышает оптимальное. Рассмотрим простой алгоритм последовательной раскраски произвольного графа с N вершинами.

Алгоритм

Последовательно рассматриваем все вершины исходного графа, чтобы определить каким цветом их покрасить. Предположим, что мы хотим определить каким цветом должна быть покрашена вершина i.

1.Полагаем первоначально номер цвета для этой вершины c =1.

2.Пока в графе существуют вершины, смежные с вершиной i и покрашенные цветом c, увеличиваем номер цвета окраски вершины i на единицу: c : = c +1.

3.Окрашиваем вершину с номером i в цвет с.

Несложно увидеть, что максимально возможное число красок, используемое для раскраски графа данным алгоритмом, равно степени графа, увеличенной на 1 (степень графа – максимум из степеней его вершин).

Пример 2 . 6 . Решить задачу раскраски графа, приведенного на рис. 2.3.

3

3

2

2

2

4

1 1

2

Рис. 2.3

44

Раскраска вершин проводилась в соответствии с приведенным алгоритмом. Вершины графа просматривались в порядке возрастания их номеров. Как видно из рис. 2.3 минимальное число потребовавшихся красок равно 3.

2.6. Приближенные алгоритмы с гарантированной оценкой точности.

Рассмотрим задачу минимизации целевого функционала F(x) на множестве X . Обозначим

F* = min{F(x) | x X }

Предположим, что F* > 0 . Пусть приближенный алгоритм H отыски-

гарантированной оценкой точности решения, получаемого при помощи алгоритма H , будем понимать верхнюю оценку величины ∆H при лю-

бом наборе входных данных задачи.

В дальнейшем обозначения F* , F H , ∆H используются при рассмот-

рении конкретных задач и конкретных приближенных алгоритмов. Смысл этих обозначений не изменяется.

Рассмотрим NP - трудную в сильном смысле задачуP // ∑ wiCi . Задача

состоит в отыскании расписания, минимизирующего взвешенную сумму моментов завершения обслуживания n требований в системе из m параллельных идентичных приборов. Для каждого требования j задана длительность обслуживания p j и вес (относительная важность) w j . Расписание

однозначно определяется разбиением множества требований на подмножества N1, N2 ,K, Nm , где требования множества N1 обслуживаются прибором

1, и указанием порядка обслуживания требований в каждом подмножестве. При помощи перестановочного приема нетрудно показать, что достаточно ограничиться рассмотрением расписаний, при которых требования каждого подмножества упорядочены по правилуSWPT , т.е. по неубыванию значений p j w j . Таким образом, расписание однозначно определяется разбие-

нием множества требований на m подмножеств.

45

Опишем приближенный алгоритм A решения задачи P // ∑wiCi , кото-

ния P1, P2 ,K, Pm можно хранить в виде кучи или поискового 2 - 3 дерева.

46

Доказательство. Воспользуемся индукцией по числу r различных значений p j w j . При r =1 справедливость утверждения следует из лем-

мы 2.3. Пусть теорема верна при всех r ≤ k −1, k ≥ 2 . Пусть имеется k различных значений p j w j и p1 w1 =K= pq wq > pq+1 wq+1 .

Положим γ = wq+1 p1 ( pq+1w1) и рассмотрим вспомогательную задачу, в

которой веса обозначены w j и для первых q требований w j =γw j , j =1,K, q . Очевидно, что во вспомогательной задаче количество различ-

47

этого неравенства X q Y q +γδ( X )δ(Y ) , получаем

( X q +δ( X ))(Y +γδ(Y )) > ( X q +γδ( X ))(Y q +δ(Y )) .

Однако

X q +δ( X ) = X , Y q +δ(Y ) = Y ,

2.7. Задача об упаковке в контейнеры

Рассмотрим NP-трудную в сильном смысле задачу об упаковке в контейнеры, которая в терминах теории расписаний может быть сформули-

рована следующим образом. В условиях задачи P d j = d C j ≤ d j предпо-

лагается, что количество приборов равно числу требований m = n , общий директивный срок не меньше максимальной длительности обслуживания требований d ≥ max p j , и требуется отыскать минимальное число прибо-

j

ров и соответствующее расписание, при котором все требования будут обслужены к директивному сроку d .

Приведем описание четырех приближенных алгоритмов решения задачи об упаковке в контейнеры. В алгоритмах рассматривается некоторая перестановка π требований, требования последовательно выбираются из этой перестановки и назначаются на приборы в соответствии с некоторыми правилами. Резервом времени прибора l , обозначаемым Rl ,

называется разница между d и суммарной длительностью обслуживания требований, назначенных на прибор l .

В алгоритмах B1 и B2 перестановка π является произвольной. На шаге k алгоритма B1 или B2 выбирается требование, расположенное на месте k в перестановке π . В алгоритме B1 это требование назначается на прибор с наименьшим номером среди приборов с достаточным резервом

48

времени для завершения этого требования в срок. В алгоритме B2 это

требование назначается на прибор с наименьшим достаточным резервом времени.

Алгоритмы B3 и B4 отличаются от алгоритмов B1 и B2 соответственно

лишь тем, что требования в перестановке π расположены в порядке LPT (невозрастания значений p j ).

Алгоритм Bi может быть реализован за время O(n logmi ) , где mi -

количество приборов, найденное алгоритмом. Каждый из приборов обслуживает хотя бы одно требование. Очевидно, что mi ≤ n , i =1,2,3,4 .

Докажем ряд вспомогательных утверждений для алгоритмов B1 и B2 . Введем в рассмотрение функцию ψ(x) , x [0,1] .

точно показать, что ∑j ψ( pi ) ≤ 710 . Возможны следующие варианты:

i=2

49

1)p2 ( 13 , 12], p3 (0, 16] ,

2)p2 ( 16 , 13], p3 (0, 16] ,

3)p2 , p3 ( 16 , 13], p4 (0, 16],

4)p2 (0, 16].