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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 13: Строка 13:
 
<tex> 1 \mid p_i = 1\mid \sum C_i</tex>
 
<tex> 1 \mid p_i = 1\mid \sum C_i</tex>
  
Этот случай простейший. Ответом будет <tex>\sum\limits_{k = 1}^n(k)</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы. Воспользовавшись формулой суммы первых <tex>n</tex> членов арифметической прогрессии алгоритм <tex>S_n=\frac{a_1+a_n}2 \cdot n</tex> будет работает за <tex>O(1)</tex>.
+
Этот случай простейший. Ответом будет <tex>\sum\limits_{k = 1}^n(k)</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы. Воспользовавшись формулой суммы первых <tex>n</tex> членов арифметической прогрессии алгоритм <tex>S_n=\frac{a_1+a_n}2 \cdot n</tex> будет работает за <tex>O(1)</tex>, но если нужно вывести и само расписание время работы будет <tex>O(n)</tex>.
  
 
===Вариант 2===
 
===Вариант 2===
 
<tex> 1 \mid p_i = 1\mid \sum w_i C_i</tex>
 
<tex> 1 \mid p_i = 1\mid \sum w_i C_i</tex>
  
Для верного выполнения просто выставим работы по порядку невозрастания весов, тогда ответом будет <tex> \sum\limits_{i = 1}^n(w_i C_i)</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы (которое в нашем случае <tex>C_{i-1}+1</tex>) домноженное на вес этой работы. Вес работ [[Сортировка|отсортировали]] за <tex>O(n \log n)</tex>. Алгоритм работает за <tex>O(n + n \log n)</tex>  
+
Для верного выполнения просто выставим работы по порядку невозрастания весов, тогда ответом будет <tex> \sum\limits_{i = 1}^n(w_i C_i)</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы (которое в нашем случае <tex>C_{i-1}+1</tex>) домноженное на вес этой работы. То есть решаем жадным алгоритмом: на каждом шаге получаем оптимальное решение и в результате верный ответ. Вес работ [[Сортировка|отсортировали]] за <tex>O(n \log n)</tex>. Алгоритм работает за <tex>O(n + n \log n)</tex>  
  
 
===Вариант 3===
 
===Вариант 3===
Строка 77: Строка 77:
 
         <tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{j}</tex>
 
         <tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{j}</tex>
 
       <tex> \mathtt{time++}</tex>
 
       <tex> \mathtt{time++}</tex>
 +
 +
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max\limits_{i = 1 \ldots n} r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, [[:Категория:Приоритетные_очереди|очередь с приоритетами]]. Значит общее время работы алгоритма <tex>O((n + \max\limits_{i = 1 \ldots n} r_{i})\log n)</tex>
  
 
====Реализация 2====
 
====Реализация 2====
Эта реализация использует [[Двоичная_куча|двоичную кучу]] <tex>\mathtt{Heap}</tex> в которой операции вставки и извлечения выполняются за <tex>O(\log n)</tex>, а операция поиска максимального элемента за <tex>O(1)</tex>
+
Перед началом алгоритма [[Сортировка|отсортируем]]работы по порядку неубывания веса.
  <tex> S \leftarrow \{1 \ldots n\}</tex>
+
   <tex> \mathtt{time} \leftarrow r_1</tex>
   <tex> \mathtt{time} \leftarrow 0</tex>
 
 
   <tex> \mathtt{answer} \leftarrow 0</tex>
 
   <tex> \mathtt{answer} \leftarrow 0</tex>
 
   '''for''' <tex>i \leftarrow 1 </tex> '''to''' <tex>n</tex> '''do'''
 
   '''for''' <tex>i \leftarrow 1 </tex> '''to''' <tex>n</tex> '''do'''
      Heap.insert(<tex>w_i</tex>)
+
       '''if''' <tex> r_{i} \leqslant \mathtt{time}</tex>
  '''while''' <tex> S \neq \varnothing </tex>
+
         <tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{i}</tex>
      <tex> j \leftarrow null </tex>
+
       '''else'''
       '''if''' <tex> i \in S</tex> '''and''' <tex> r_{i} \leqslant \mathtt{time}</tex> '''and''' <tex>w_i \geqslant </tex> Heap.Max()
+
        <tex> \mathtt{time} \leftarrow r_i</tex>
        <tex> j \leftarrow i </tex>
+
        <tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{i}</tex>
      '''if''' <tex>j \neq null </tex>
 
        <tex> S \leftarrow S \setminus j</tex>
 
        Heap.extractMax()
 
         <tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{j}</tex>
 
       <tex> \mathtt{time++}</tex>
 
 
 
===Сложность алгоритмов===
 
====Алгоритм 1====
 
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max\limits_{i = 1 \ldots n} r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, [[:Категория:Приоритетные_очереди|очередь с приоритетами]]. Значит общее время работы алгоритма <tex>O((n + \max\limits_{i = 1 \ldots n} r_{i})\log n)</tex>
 
  
====Алгоритм 2====
+
В начале алгоритма сортируем работы <tex>O(n \log n)</tex> времени. Затем мы тратим <tex>O(n)</tex> на получение ответа. Тогда суммарное время работы алгоритма составит <tex>O(n \log n + n )</tex> что есть <tex>O(n (\log n + 1))</tex> времени.
В начале алгоритма мы добавляем все элементы <tex>w_i</tex> в двоичную кучу тратя на это <tex>O(n \log n)</tex> времени. Затем мы тратим <tex>O(n \log n)</tex> на получение ответа. Тогда суммарное время работы алгоритма составит <tex>O(n \log n + n \log n)</tex> что есть <tex>O(n \log n)</tex> времени.
 
  
 
==См. также==
 
==См. также==

Версия 22:37, 3 июня 2015

[math] 1 \mid r_i,p_i = 1 \mid \sum w_i C_i[/math]


Задача:
Дано [math]n[/math] работ и один станок. Для каждой работы известно её время появления [math]r_{i}[/math] и вес [math]w_{i}[/math]. Время выполнения всех работ [math]p_i[/math] равно [math]1[/math]. Требуется выполнить все работы, чтобы значение [math]\sum w_{i} C_{i}[/math] было минимальным, где [math]C_{i}[/math] — время окончания работы.


Более простые варианты исходной задачи

Перед решением основной задачи рассмотрим более простые.

Вариант 1

[math] 1 \mid p_i = 1\mid \sum C_i[/math]

Этот случай простейший. Ответом будет [math]\sum\limits_{k = 1}^n(k)[/math], так как мы [math]n[/math] раз сложим время окончания выполнения одной работы. Воспользовавшись формулой суммы первых [math]n[/math] членов арифметической прогрессии алгоритм [math]S_n=\frac{a_1+a_n}2 \cdot n[/math] будет работает за [math]O(1)[/math], но если нужно вывести и само расписание время работы будет [math]O(n)[/math].

Вариант 2

[math] 1 \mid p_i = 1\mid \sum w_i C_i[/math]

Для верного выполнения просто выставим работы по порядку невозрастания весов, тогда ответом будет [math] \sum\limits_{i = 1}^n(w_i C_i)[/math], так как мы [math]n[/math] раз сложим время окончания выполнения одной работы (которое в нашем случае [math]C_{i-1}+1[/math]) домноженное на вес этой работы. То есть решаем жадным алгоритмом: на каждом шаге получаем оптимальное решение и в результате верный ответ. Вес работ отсортировали за [math]O(n \log n)[/math]. Алгоритм работает за [math]O(n + n \log n)[/math]

Вариант 3

[math] 1 \mid r_i,p_i = 1 \mid \sum f_i[/math]

[math]f_{i}[/math] — монотонная функция времени окончания работы [math]C_{i}[/math] для работ [math]i = 1, 2, \ldots , n[/math].


Нам нужно распределить [math]n[/math] работ в разное время. Если мы назначим время [math]t[/math] для работы [math]i[/math] то цена будет [math]f_i(t + 1)[/math]. Функция [math]f_i[/math] монотонно неубывающая, тогда работы в расписании надо располагать как можно раньше для получения верного решения. [math]n[/math] временных интервалов [math]t_i[/math] для [math]n[/math] работ могут быть получены с помощью следующего алгоритма, где предполагается что работы отсортированы так:

[math] r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n[/math]

Псевдокод

  [math]t_1 \leftarrow r_1 [/math]
  for  [math] i \leftarrow 2[/math] to [math]n[/math] do
     [math] t_i \leftarrow [/math] max[math](r_i, \ t_{i-1} - 1)[/math]

Этот алгоритм работает за [math]O(n \log n +n)[/math]

Основная задача

Описание алгоритма

Пусть [math]time[/math] — текущий момент времени.
Для каждого очередного значения [math]time[/math], которое изменяется от [math]0[/math] до времени окончания последней работы, будем:

  1. Выбирать работу [math]j[/math] из множества невыполненных работ, у которой [math]r_{i} \leqslant time[/math], а значение [math]w_{i}[/math] максимально.
  2. Если мы смогли найти работу [math]j[/math], то выполняем её в момент времени [math]time[/math] и удаляем из множества невыполненных работ.
  3. Увеличиваем [math]time[/math] на один.

Доказательство корректности алгоритма

Теорема:
Расписание, построенное данным алгоритмом, является корректным и оптимальным.
Доказательство:
[math]\triangleright[/math]

Доказательство будем вести от противного.
Рассмотрим расписание [math]S_{1}[/math], полученное после выполнения нашего алгоритма, и оптимальное расписание [math]S_{2}[/math].
Возьмём первый момент времени [math]t_{1}[/math], когда расписания различаются. Пусть в этот момент времени в [math]S_{1}[/math], будет выполняться работа с весом [math]w_{1}[/math], а в [math]S_{2}[/math] — работа с весом [math]w_{2}[/math].
Это первый момент, в котором расписания отличаются, значит в [math]S_{2}[/math] работа с весом [math]w_{1}[/math] выполнится в момент времени [math]t_{2} \gt t_{1}[/math].
Поменяем местами работы с весами [math]w_{1}[/math] и [math]w_{2}[/math] в [math]S_{2}[/math] и полуим расписание [math]S_{3}[/math]. Это возможно, потому что время появления этих работ не меньше [math]t_{1}[/math].
При такой перестановке ответы на задачу для [math]S_{2}[/math] и [math]S_{3}[/math] будут отличаться на

    [math]t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})[/math]

Первая скобка отрицательная: [math]t_{1} \lt t_{2}[/math]. Вторая скобка тоже отрицательная из того, что в [math]S_{1}[/math] работа с весом [math]w_1[/math] выполняется раньше, значит её вес должен быть больше [math]w_2[/math].

Итого имеем, что ответ для [math]S_{2}[/math] больше, чем ответ для [math]S_{3}[/math]. Следовательно расписание [math]S_2[/math] неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание [math]S_{1}[/math] отличается от оптимального. Следовательно мы доказали, что оно оптимальное.
[math]\triangleleft[/math]

Псевдокод

Реализация 1

  [math] S \leftarrow \{1 \ldots n\}[/math]
  [math] \mathtt{time} \leftarrow 0[/math]
  [math] \mathtt{answer} \leftarrow 0[/math]
  while [math] S \neq \varnothing [/math]
     [math] j \leftarrow null [/math]
     if [math] i \in S[/math] and [math] r_{i} \leqslant \mathtt{time}[/math] and [math]w_i \geqslant \max\limits_{j \in S, j = 1 \ldots n} w_j[/math]
        [math] j \leftarrow i [/math]
     if [math]j \neq null [/math]
        [math] S \leftarrow S \setminus j[/math]
        [math] \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{j}[/math]
     [math] \mathtt{time++}[/math]

Множество [math]S[/math] станет пустым не позже, чем через [math]n + \max\limits_{i = 1 \ldots n} r_{i}[/math] шагов цикла. Определить максимум в множестве можно за время [math]O(\log n)[/math], используя , например, очередь с приоритетами. Значит общее время работы алгоритма [math]O((n + \max\limits_{i = 1 \ldots n} r_{i})\log n)[/math]

Реализация 2

Перед началом алгоритма отсортируемработы по порядку неубывания веса.

  [math] \mathtt{time} \leftarrow r_1[/math]
  [math] \mathtt{answer} \leftarrow 0[/math]
  for [math]i \leftarrow 1 [/math] to [math]n[/math] do
     if  [math] r_{i} \leqslant \mathtt{time}[/math]
        [math] \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{i}[/math]
     else
        [math] \mathtt{time} \leftarrow r_i[/math]
        [math] \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_{i}[/math]

В начале алгоритма сортируем работы [math]O(n \log n)[/math] времени. Затем мы тратим [math]O(n)[/math] на получение ответа. Тогда суммарное время работы алгоритма составит [math]O(n \log n + n )[/math] что есть [math]O(n (\log n + 1))[/math] времени.

См. также

Источники информации

  • P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19-20
  • P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 38-39
  • P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 84-85
  • Лазарев А.А., Мусатова Е.Г., Кварацхелия А.Г., Гафаров Е.Р. Пособие по теории расписаний.