1precpmtnrifmax — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Общий алгоритм)
(Время работы: добавил доказательство)
Строка 34: Строка 34:
  
 
== Время работы ==
 
== Время работы ==
Лемма: время работы алгоритма <tex> 1 \mid prec, pmtn, r_i \mid f_{max} </tex> <tex> O(n^2) </tex> операций.
+
{{Теорема
 +
|statement=
 +
Время работы алгоритма MakeSchedule() — <tex> O(n^2) </tex> операций.
 +
|proof=
 +
Обозначим за <tex> P(n) </tex> время, необходимое для выполнения алгоритма MakeSchedule() на n работах. Очевидно, для корректно определенной функции P в силу структуры алгоритма должно выполняться неравенство:
 +
 
 +
<tex> P(n) \ge сn + \sum\limits_{i = 1}^{k} P(n_i) </tex>
 +
 
 +
Здесь <tex> n_i </tex> - размер блока с номером <tex> i </tex>, построенного алгоритмом Blocks(). Заметим, что <tex> \sum\limits_{i = 1}^{k} n_i = n - 1</tex>.
 +
 
 +
Если P(n) = an^2, то имеем:
 +
 
 +
<tex> an^2 \ge cn + a \sum\limits_{i = 1}^{k} n_i^2 </tex>
 +
 
 +
Так как <tex> n^2 > (n - 1)^2 = (\sum\limits_{i = 1}^{k} n_i)^2 = \sum\limits_{i = 1}^{k} n_i^2 + 2\sum\limits_{\substack{i, j = 1\\ i \ne j}}^{k} n_i n_j </tex>, то можно переписать неравенство в следующем виде:
 +
 
 +
<tex> 2a \sum\limits_{\substack{i, j = 1\\ i \ne j}}^{k} n_i n_j \ge cn </tex>
 +
 
 +
Чтобы получить максимальную нижнюю оценку на <tex> a </tex>, оценим снизу <tex> \sum\limits_{i, j = 1}^{k} n_i n_j </tex>:
 +
 
 +
Так как <tex> \sum\limits_{\substack{i, j = 1\\ i \ne j}}^{k} n_i n_j \ge \sum\limits_{\substack{i, j = 1\\ i \ne j}}^{k} 1 \cdot n_j = \sum\limits_{j = 1}^{k} (k - 1) n_j = (k - 1) (n - 1) \ge \frac{nk}{4}</tex>
 +
 
 +
Значит, при <tex> a \ge \frac{c}{2} \frac{n}{\frac{nk}{4}} = \frac{2c}{k} </tex> требуемое неравенство будет выполняться.
 +
 
 +
}}

Версия 20:54, 3 июня 2012

Постановка задачи

Задача [math] 1 \mid prec, pmtn, r_i \mid f_{max} [/math] является обобщением [math]1 \mid prec \mid f_{max}[/math], но здесь у работ также есть времена появления, раньше которых их делать запрещено, и их можно прерывать.

Алгоритм

Работу будем обозначать просто ее номером ([math] i [/math]), при этом, номера работ могут меняться в зависимости от того, по какому параметру они отсортированы. Время появления работы — [math] r_i [/math], время, требуемое для ее выполнения — [math] p_i [/math]. Множество ребер графа обозначается как [math] E [/math].

Modify

Для начала, модифицируем времена появления работ. Если работа [math] j [/math] зависит от [math] i [/math], то, очевидно, она не может быть начата раньше, чем закончится выполнение </tex> i </tex>, поэтому нужно заменить [math] r_j [/math] на [math] \max(r_j, r_i + p_i) [/math]. Алгоритм, делающий это, представлен ниже (работы рассматриваются в порядке топологической сортировки):

Modify()
1    for i [math] \in \{ 1 \ldots n \} [/math]
2      for j: ij [math] \in E [/math]
3        [math] r_j \leftarrow \max(r_j, r_i + p_i) [/math] 

После выполнения этого алгоритма для любых двух работ [math] i, j [/math], таких, что [math] j [/math] зависит от [math] i [/math], выполняется [math] r_j \gt r_i [/math], поэтому, при рассмотрении работ в порядке неубывания времен их появления, они также будут топологически отсортированы.

Blocks

Здесь и далее считается, что работы отсортированы в порядке неубывания модифицированных [math] r_i [/math].

Decompose

Идея следующая: допустим, у нас есть блок работ, который можно выполнить без прерываний. Найдем работу [math]i[/math], которую выгодно выполнить последней. Разобъем оставшееся множество работ на блоки, решим задачу для этих блоков рекурсивно и вставим [math] i [/math] в промежутки между этими блоками, до них и после них, начиная с [math] r_i [/math].

Общий алгоритм

Выполним Modify(), после чего разобъем все множество работ на блоки и для каждого блока запустим Decompose():

MakeSchedule()
1    Modify()
2    B = Blocks([math] \{1 \ldots n \} [/math])
3    ans = - [math] \infty [/math]
4    for ([math] B_i \in [/math] B):
5      ans = [math] \max [/math] (ans, Decompose([math] B_i [/math]))
6    return ans

Время работы

Теорема:
Время работы алгоритма MakeSchedule() — [math] O(n^2) [/math] операций.
Доказательство:
[math]\triangleright[/math]

Обозначим за [math] P(n) [/math] время, необходимое для выполнения алгоритма MakeSchedule() на n работах. Очевидно, для корректно определенной функции P в силу структуры алгоритма должно выполняться неравенство:

[math] P(n) \ge сn + \sum\limits_{i = 1}^{k} P(n_i) [/math]

Здесь [math] n_i [/math] - размер блока с номером [math] i [/math], построенного алгоритмом Blocks(). Заметим, что [math] \sum\limits_{i = 1}^{k} n_i = n - 1[/math].

Если P(n) = an^2, то имеем:

[math] an^2 \ge cn + a \sum\limits_{i = 1}^{k} n_i^2 [/math]

Так как [math] n^2 \gt (n - 1)^2 = (\sum\limits_{i = 1}^{k} n_i)^2 = \sum\limits_{i = 1}^{k} n_i^2 + 2\sum\limits_{\substack{i, j = 1\\ i \ne j}}^{k} n_i n_j [/math], то можно переписать неравенство в следующем виде:

[math] 2a \sum\limits_{\substack{i, j = 1\\ i \ne j}}^{k} n_i n_j \ge cn [/math]

Чтобы получить максимальную нижнюю оценку на [math] a [/math], оценим снизу [math] \sum\limits_{i, j = 1}^{k} n_i n_j [/math]:

Так как [math] \sum\limits_{\substack{i, j = 1\\ i \ne j}}^{k} n_i n_j \ge \sum\limits_{\substack{i, j = 1\\ i \ne j}}^{k} 1 \cdot n_j = \sum\limits_{j = 1}^{k} (k - 1) n_j = (k - 1) (n - 1) \ge \frac{nk}{4}[/math]

Значит, при [math] a \ge \frac{c}{2} \frac{n}{\frac{nk}{4}} = \frac{2c}{k} [/math] требуемое неравенство будет выполняться.
[math]\triangleleft[/math]