Редактирование: Pintreepi1Lmax

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 4: Строка 4:
 
|definition=Рассмотрим задачу на нахождение расписания:
 
|definition=Рассмотрим задачу на нахождение расписания:
 
# У нас есть несколько станков, работающих параллельно. У станков могут быть разные скорости выполнения работ.
 
# У нас есть несколько станков, работающих параллельно. У станков могут быть разные скорости выполнения работ.
# Есть несколько заданий, каждое из которых имеет определенный порядок, который указан в направленном из корней в лист [[Классификация задач#intree|intree-дерева]], которое имеет несколько корней и один лист.
+
# Есть несколько заданий, каждое из которых имеет определенный порядок, который указан в направленном из корней в лист [[Классификация задач#Характеристики работ|intree-дерева]].
 
# Любая работа на любом станке выполняется единицу времени.
 
# Любая работа на любом станке выполняется единицу времени.
 
Требуется минимизировать максимальное опоздание <tex>L_{max} = \max\limits_i \{C_i - d_i\}</tex>.
 
Требуется минимизировать максимальное опоздание <tex>L_{max} = \max\limits_i \{C_i - d_i\}</tex>.
Строка 13: Строка 13:
 
=== Идея ===
 
=== Идея ===
  
Все работы хранятся в качестве вершин [[Классификация задач#intree|intree-дерева]], состоящем из <tex>n</tex> вершин. В intree-дереве у одной вершины может быть два и более родителей.
+
Все работы хранятся в качестве вершин [[Классификация задач#Характеристики работ|intree-дерева]], состоящем из <tex>n</tex> вершин, нескольких корней и одного листа. В intree-дереве у одной вершины может быть два и более родителей.
Решение задачи состоит из двух шагов:
+
Решение задачи состоит из двух шагов: на первом шаге мы меняем сроки выполнения работ в соответствии с их очередностью.
 
 
# Меняем делайны работ в соответствии с их очередностью: для всех <tex>i, j</tex> таких, что существует ребро из <tex>i</tex> в <tex>j</tex> будем менять <tex>{d_i}</tex> на <tex>\min ({d_i}, {d_j} - 1) </tex>.
 
# Работы расставляются в неубывающем порядке их дедлайнов.
 
  
 +
# Для всех <tex>i, j</tex> таких, что существует ребро из <tex>i</tex> в <tex>j</tex> будем менять <tex>{d_i}</tex> на <tex>\min ({d_i}, {d_j} - 1) </tex>.
 +
# Работы расставляются в неубывающем порядке сроков.
 
=== Псевдокод ===
 
=== Псевдокод ===
 
==== Первый шаг ====
 
==== Первый шаг ====
На первом шаге мы релаксируем дедлайны всех работ, кроме листовой, в соответствии с предыдущим пунктом.
+
Алгоритм изменения сроков:
* В массиве <tex>\mathtt d</tex> хранятся дедлайны работ.
+
i = 0
* В массиве <tex>\mathtt {parents}</tex> {{---}} массив предков <tex>i</tex>-й работы.
+
deque = <tex>\varnothing</tex>
* В переменной <tex>\mathtt i</tex> хранится номер листа (он один, см. условие задачи).
+
'''for''' k = 1 .. n
'''Deque<int>''' deque = <tex>\varnothing</tex>
+
    '''if''' k.parent == <tex>\varnothing</tex>
  deque.push(i)
+
        i = k  <font color=green> // такая вершина только одна (intree-дерево) </font>  
  '''while''' '''not''' deque.isEmpty
+
  deque.push(i) <font color=green> // пустой дек </font>
     '''int''' j = deque.removeFirst()
+
  '''while''' '''not''' deque.isEmpty()
     '''for''' k '''in''' parents[j]
+
     i = deque.removeFirst()
         d[k] = min(d[k], d[j] - 1)
+
     '''for''' j '''in''' i.parents
         deque.addLast(k)
+
         j.deadline = min(j.deadline, i.deadline - 1)
 +
         stack.add_last(j)
  
 
==== Второй шаг ====
 
==== Второй шаг ====
На втором этапе алгоритма работы сортируются в неубывающем порядке их дедлайнов. Предполагается, что работы будут занумерованы так, что <tex>d_{i} \leqslant d_{j}</tex>, если <tex>i \leqslant j</tex>.
+
На втором этапе алгоритма работы сортируются в неубывающем порядке их дедлайнов. Предполагается, что работы занумерованы в соответствии с предыдущим пунктом, т.е. <tex>d_{i} \leqslant d_{j}</tex>, если <tex>i \leqslant j</tex>.
* В переменной <tex>\mathtt F</tex> хранится время, когда какой-либо станок освободится.
+
* В переменной <tex>\mathtt F</tex> хранится время, когда станок освободится.
 
* В массиве <tex>\mathtt r</tex> хранится информация о максимальном времени завершении обработки родителя.
 
* В массиве <tex>\mathtt r</tex> хранится информация о максимальном времени завершении обработки родителя.
 
* Массив <tex>\mathtt q</tex> хранит информацию о количестве работ, готовых к исполнению (находящихся в очереди) в момент времени <tex>t</tex>.
 
* Массив <tex>\mathtt q</tex> хранит информацию о количестве работ, готовых к исполнению (находящихся в очереди) в момент времени <tex>t</tex>.
 
* Массив <tex>\mathtt x</tex> хранит информацию о начале выполнения работы <tex>i</tex>.
 
* Массив <tex>\mathtt x</tex> хранит информацию о начале выполнения работы <tex>i</tex>.
* В массиве <tex>\mathtt {child}</tex> хранится индекс ребенка <tex>i</tex>-й работы.
 
  
 
  F = 0
 
  F = 0
  '''for''' '''int''' i = 1 .. n
+
  '''for''' i = 1 .. n
 
     r[i] = 0
 
     r[i] = 0
  '''for''' '''int''' t = 0 .. n
+
  '''for''' t = 0 .. n
 
     q[t] = 0
 
     q[t] = 0
  '''for''' '''int''' i = 1 .. n
+
  '''for''' i = 1 .. n
     '''int''' t = max(r[i], F)
+
     t = max(r[i], F)
 
     x[i] = t
 
     x[i] = t
 
     q[t] = q[t] + 1
 
     q[t] = q[t] + 1
 
     '''if''' q[t] == m
 
     '''if''' q[t] == m
 
       F = t + 1
 
       F = t + 1
     '''int''' j = child[i]
+
     j = i.child()
 
     r[j] = max(r[j], t + 1)
 
     r[j] = max(r[j], t + 1)
 
В результате ответ можно получить, зная конечный массив <tex>\mathtt x</tex> и делайны работ: <tex>L_{max} = \max\limits_i (\mathtt x[i] + 1 - d_{i}</tex>), так как все работы выполняются единицу времени, следовательно, <tex>C_{i} = \mathtt x[i] + 1</tex>. Можно заметить, что при вычислении ответа неважно, какие дедлайны использовать, начальные или релаксированные, потому что для любого <tex>k</tex> и его предка <tex>i</tex> либо производится релаксация и выполняется равенство <tex> d_{k} = d_{i} - 1</tex>, а значит, после релаксации максимум не изменится, поскольку при замене дедлайна на меньший максимум увеличится, а новое значение <tex>L_{k}</tex> будет равно <tex>L_{i}</tex>, либо мы не делали релаксацию, и значение <tex>d_{k}</tex>, и, следовательно, <tex>L_{k}</tex> не поменяются.
 
  
 
=== Доказательство корректности ===
 
=== Доказательство корректности ===
Строка 100: Строка 97:
  
 
==== Асимптотика ====
 
==== Асимптотика ====
# На первом шаге мы посещаем каждую вершину не более двух раз (первый {{---}} когда ищем вершину без родителя, второй {{---}} когда релаксируем дедлайны) за <tex>O(n)</tex> времени.
+
# На перов шаге мы посещаем каждую вершину ровно два раза (первый {{---}} когда ищем вершину без родителя, второй {{---}} когда релаксируем дедлайны) за <tex>O(n)</tex> времени.
# Делаем сортировку вершин за <tex>O(n \log n)</tex>, а затем обходим все вершины по разу и считаем время начала выполнения каждой работы, в сумме за <tex>O(n)</tex>.
+
# Делаем сортировку вершин за <tex>O(n \log n)</tex>, а затем для каждой вершины считаем время за линейное время.
 
Итоговая сложность {{---}} <tex>O(n \log n)</tex>
 
Итоговая сложность {{---}} <tex>O(n \log n)</tex>
  

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)