Участник:Qtr - История изменений

Qtr: /* Декомпозиция */

2016-06-04T23:18:03Z

‎Декомпозиция

Qtr: /* Декомпозиция */

2016-06-04T22:46:41Z

‎Декомпозиция

Qtr: /* Декомпозиция */

2016-06-04T22:37:49Z

‎Декомпозиция

Qtr: /* Разбиение на блоки */

2016-06-04T22:37:17Z

‎Разбиение на блоки

Qtr в 22:29, 4 июня 2016

2016-06-04T22:29:33Z

Qtr: /* Декомпозиция */

2016-06-04T22:11:58Z

‎Декомпозиция

Qtr: /* Декомпозиция */

2016-06-04T22:08:39Z

‎Декомпозиция

Qtr: /* Идея алгоритма */

2016-06-04T22:06:10Z

‎Идея алгоритма

Qtr: /* Алгоритм */

2016-06-04T21:50:32Z

‎Алгоритм

Qtr: /* Декомпозиция */

2016-06-04T21:34:51Z

‎Декомпозиция

@@ Строка 75: / Строка 75: @@
     '''<tex>\langle</tex>int, int[]<tex>\rangle</tex>''' decompose('''Block''' b, '''int[]''' schedule):
       '''int''' e = b.end <font color = "darkgreen"> // e — время завершения работ блока B</font>
-      find  l: f[l](e) = <tex> \min  \{f[j](e) \mid j \in B, \overline\exists\ k: jk \in E \} </tex>
+      find l: f[l](e) = <tex> \min  \{f[j](e) \mid j \in B, \overline\exists\ k: jk \in E \} </tex>
       '''int''' ans = f[l](e)
       b.jobs.remove(l)

@@ Строка 77: / Строка 77: @@
       find  l: f[l](e) = <tex> \min  \{f[j](e) \mid j \in B, \overline\exists\ k: jk \in E \} </tex>
       '''int''' ans = f[l](e)
-      '''Block[]''' g = blocks(<tex> b \setminus l </tex>)
+     b.jobs.remove(l)
       '''for''' i = 2 '''to''' g.size
         schedule[g[i-1].end .. g[i].begin - 1] = l<font color = "darkgreen"> // Вставляем работу в расписание между блоками</font>

@@ Строка 79: / Строка 79: @@
       '''Block[]''' g = blocks(<tex> b \setminus l </tex>)
       '''for''' i = 2 '''to''' g.size
-        schedule[g[i-1].end .. g[i].begin - 1] = l<font color = "darkgreen">// Вставляем работу в расписание между блоками</font>
+        schedule[g[i-1].end .. g[i].begin - 1] = l<font color = "darkgreen"> // Вставляем работу в расписание между блоками</font>
-      schedule[b.start .. g[1].start - 1] = l <font color = "darkgreen">  // Нужно учесть пропуски перед первым и </font>
+      schedule[b.start .. g[1].start - 1] = l <font color = "darkgreen">   // Нужно учесть пропуски перед первым и </font>
-      schedule[g[g.size].end .. b.end - 1] = l <font color = "darkgreen"> // после последнего блоков соответственно</font>
+      schedule[g[g.size].end .. b.end - 1] = l <font color = "darkgreen">  // после последнего блоков соответственно</font>
       '''for''' b <tex>\in</tex> g
         ans = max(ans, decompose(b, schedule).first)

@@ Строка 57: / Строка 57: @@
       '''return''' b
-Если алгоритм <tex>\mathrm{Blocks}</tex> вызывается от пустых массивов, то считаем, что он возвращает пустое множество.
+Если значение <tex>n</tex> равно нулю, то считаем, что алгоритм <tex>\mathrm{Blocks}</tex> возвращает пустое множество.
 Определим время начала блока <tex> B_j </tex> как <tex>s_j = \min\limits_{i \in B_j} rm_i </tex>, а время конца — как <tex> e_j = s_j + \sum\limits_{i \in B_j} p_i </tex>.

@@ Строка 81: / Строка 81: @@
         schedule[g[i-1].end .. g[i].begin - 1] = l<font color = "darkgreen">// Вставляем работу в расписание между блоками</font>
       schedule[b.start .. g[1].start - 1] = l <font color = "darkgreen">  // Нужно учесть пропуски перед первым и </font>
-      schedule[g[g.size].end .. b.end - 1] = l <font color = "darkgreen"> // после последнего блока соответственно</font>
+      schedule[g[g.size].end .. b.end - 1] = l <font color = "darkgreen"> // после последнего блоков соответственно</font>
       '''for''' b <tex>\in</tex> g
         ans = max(ans, decompose(b, schedule).first)

@@ Строка 80: / Строка 80: @@
       '''for''' i = 2 '''to''' g.size
         schedule[g[i-1].end..g[i].begin - 1] = l <font color = "darkgreen">// Вставляем работу в расписание между блоками</font>
-      schedule[b.start to g[1].start - 1] = l <font color = "darkgreen"> // Нужно учесть пропуски перед первым и </font>
+      schedule[b.start to g[1].start - 1] = l <font color = "darkgreen"> //  Нужно учесть пропуски перед первым и </font>
       schedule[g[g.size].end .. b.end - 1] = l <font color = "darkgreen"> // после последнего блока соответственно</font>
       '''for''' b <tex>\in</tex> g

@@ Строка 11: / Строка 11: @@
 ===Идея алгоритма===
-Будем решать задачу рекурсивно. Разобьем множество работ на блоки, внутри которых работы могут выполняться непрерывно. После этого для каждого из блоков найдем работу, которую выгоднее всего выполнить последней, удалим работу из соответствующего блока и повторим разбиение на блоки для оставшихся работ. Пустые промежутки между подблоками, полученными из данного блока, заполним выбранной работой. Будем делать то же самое для каждого из получившихся подблоков. Как будет показано далее, данный алгоритм строит корректное и оптимальное расписание. Можно заметить, что если на каждом этапе будет получаться всего один блок, алгоритм выродится в [[Правило_Лаулера|алгоритм Лаулера]].
+Будем решать задачу рекурсивно. Разобьем множество работ на подмножества (блоки), внутри которых не будет перерыва между выполнением работ. После этого для каждого из блоков найдем работу, которую выгоднее всего выполнить последней, удалим работу из соответствующего блока и повторим разбиение на подблоки для оставшихся работ. Пустые промежутки между подблоками, полученными из данного блока, заполним выбранной работой. Повторим рекурсивно для каждого из полученных подблоков. Как будет показано далее, данный алгоритм строит корректное и оптимальное расписание. Можно заметить, что если на каждом этапе будет получаться всего один блок, алгоритм выродится в [[Правило_Лаулера|алгоритм Лаулера]].
 === Препроцессинг ===

@@ Строка 79: / Строка 79: @@
       '''Block[]''' g = blocks(<tex> b \setminus l </tex>)
       '''for''' i = 2 '''to''' g.size
-        '''for''' j =  g[i - 1].end '''to''' g[i].begin - 1
+        schedule[g[i-1].end..g[i].begin - 1] = l <font color = "darkgreen">// Вставляем работу в расписание между блоками</font>
-         schedule[j] = l <font color = "darkgreen"> // Вставляем работу в расписание между блоками</font>
+      schedule[b.start to g[1].start - 1] = l <font color = "darkgreen"> // Нужно учесть пропуски перед первым и </font>
-      schedule[b.begin to g[1].begin - 1] = l
+      schedule[g[g.size].end .. b.end - 1] = l <font color = "darkgreen"> // после последнего блока соответственно</font>
       '''for''' b <tex>\in</tex> g
         ans = max(ans, decompose(b, schedule).first)
@@ Строка 117: / Строка 116: @@
       '''Blocks[]''' b = blocks(jobs.p, rm)
       '''int''' ans = <tex> -\infty </tex>
-      '''for''' b[j] <tex>\in</tex> b
+      '''for''' block <tex>\in</tex> b
-        ans = max(ans, decompose(b[j],schedule).first)
+        ans = max(ans, decompose(block,schedule).first)
       '''return''' <tex>\langle</tex>ans, schedule<tex>\rangle</tex>