|
|
(не показано 11 промежуточных версий 3 участников) |
Строка 22: |
Строка 22: |
| Так как [[Сортировка|сортировка]] весов занимает <tex>O(n \log n)</tex> время, то асимптотика времени работы алгорита равна <tex>O(n + n \log n)</tex>. | | Так как [[Сортировка|сортировка]] весов занимает <tex>O(n \log n)</tex> время, то асимптотика времени работы алгорита равна <tex>O(n + n \log n)</tex>. |
| | | |
− | ===Вариант 3===
| |
− | <tex> 1 \mid r_i,p_i = 1 \mid \sum f_i</tex>
| |
− |
| |
− | <tex>f_{i}</tex> {{---}} монотонная функция времени окончания работы <tex>C_{i}</tex> для работ <tex>i = 1, 2, \ldots , n</tex>.
| |
− |
| |
− |
| |
− | Нам нужно распределить <tex>n</tex> работ в разное время. Если мы назначим время <tex>t</tex> для работы <tex>i</tex> то цена будет <tex>f_i(t + 1)</tex>. Функция <tex>f_i</tex> монотонно неубывающая, тогда работы в расписании надо располагать как можно раньше для получения верного решения. <tex>n</tex> временных интервалов <tex>t_i</tex> для <tex>n</tex> работ могут быть получены с помощью следующего алгоритма, где предполагается что работы отсортированы так:
| |
− |
| |
− | <tex> r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n</tex>
| |
− |
| |
− | '''Псевдокод'''
| |
− |
| |
− | <tex>t_1 \leftarrow r_1 </tex>
| |
− | '''for''' <tex> i \leftarrow 2</tex> '''to''' <tex>n</tex> '''do'''
| |
− | <tex> t_i \leftarrow </tex> max<tex>(r_i, \ t_{i-1} - 1)</tex>
| |
− |
| |
− | Этот алгоритм работает за <tex>O(n \log n +n)</tex>
| |
| ==Основная задача== | | ==Основная задача== |
| ===Описание алгоритма=== | | ===Описание алгоритма=== |
Строка 83: |
Строка 66: |
| | | |
| ====Реализация 2==== | | ====Реализация 2==== |
− | Перед началом алгоритма [[Сортировка|отсортируем]] работы по порядку неубывания времени появления и добавляем их в очередь <tex>Q</tex>.
| + | * <tex>\mathtt{Q}</tex> {{---}} обычная [[Очередь | очередь]], в которой работы изначально располагаются в отсортированном по <tex>r_i</tex> порядке, |
| + | * <tex>\mathtt{P}</tex> {{---}} [[Приоритетные очереди | приоритетная очередь]] по максимуму. |
| | | |
− | insert - функция добавления элемента в очередь с приоритетами <tex>P</tex>. | + | <tex> \mathtt{time} \leftarrow 1</tex> |
| + | <tex> \mathtt{answer} \leftarrow 0</tex> |
| + | '''while''' <tex>\mathtt{Q} \neq \varnothing </tex> '''and''' <tex>\mathtt{P} \neq \varnothing </tex> |
| + | '''if''' <tex>\mathtt{Q} \neq \varnothing </tex> |
| + | <tex> j \leftarrow \mathtt{Q.head()}</tex> |
| + | '''if''' <tex>\mathtt{time} < r_j</tex> |
| + | <tex>\mathtt{time} \leftarrow r_j</tex> |
| + | '''while''' <tex> \mathtt{time} \geqslant r_j</tex> |
| + | <tex>\mathtt{P.insert}(w_j)</tex> |
| + | <tex>\mathtt{Q.pop()}</tex> |
| + | '''if''' <tex>\mathtt{Q} = \varnothing </tex> |
| + | '''break''' |
| + | '''else''' |
| + | <tex> j \leftarrow \mathtt{Q.head()}</tex> |
| + | <tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot \mathtt{P.extractMax()} </tex> |
| + | <tex> \mathtt{time}\texttt{++}</tex> |
| | | |
− | pop - функция извлечения элемента из очереди <tex>Q</tex>.
| + | Данная реализация имеет идею, аналогичную предыдущей: сначала обрабатывать работу с максимальным весом среди всех доступных. |
− | | + | В начале работы сортируются по <tex>r_i</tex>, из очереди <tex>\mathtt{Q}</tex> достаётся каждая работа, причём ровно один раз, аналогично для очереди <tex>\mathtt{P}</tex>, поэтому итоговая асимптотика времени работы алгоритма составляет <tex>O(n \log n)</tex>. |
− | <tex> S \leftarrow \{1 \ldots n\}</tex>
| |
− | <tex> \mathtt{time} \leftarrow r_i</tex>
| |
− | <tex> \mathtt{answer} \leftarrow 0</tex>
| |
− | <tex> j \leftarrow 1</tex>
| |
− | '''while''' <tex> S \neq \varnothing </tex>
| |
− | '''while''' <tex>r_i \leqslant \mathtt{time}</tex>
| |
− | P.insert(<tex>w_i</tex>)
| |
− | Q.pop()
| |
− | <tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \ \cdot </tex> P.extractMax()
| |
− | <tex> \mathtt{time++}</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> времени.
| |
| | | |
| ==См. также== | | ==См. также== |
[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=\dfrac{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}^nw_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].
Основная задача
Описание алгоритма
Пусть [math]time[/math] — текущий момент времени.
Для каждого очередного значения [math]time[/math], которое изменяется от [math]0[/math] до времени окончания последней работы, будем:
- Выбирать работу [math]j[/math] из множества невыполненных работ, у которой [math]r_{i} \leqslant time[/math], а значение [math]w_{i}[/math] максимально.
- Если мы смогли найти работу [math]j[/math], то выполняем её в момент времени [math]time[/math] и удаляем из множества невыполненных работ.
- Увеличиваем [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{Q}[/math] — обычная очередь, в которой работы изначально располагаются в отсортированном по [math]r_i[/math] порядке,
- [math]\mathtt{P}[/math] — приоритетная очередь по максимуму.
[math] \mathtt{time} \leftarrow 1[/math]
[math] \mathtt{answer} \leftarrow 0[/math]
while [math]\mathtt{Q} \neq \varnothing [/math] and [math]\mathtt{P} \neq \varnothing [/math]
if [math]\mathtt{Q} \neq \varnothing [/math]
[math] j \leftarrow \mathtt{Q.head()}[/math]
if [math]\mathtt{time} \lt r_j[/math]
[math]\mathtt{time} \leftarrow r_j[/math]
while [math] \mathtt{time} \geqslant r_j[/math]
[math]\mathtt{P.insert}(w_j)[/math]
[math]\mathtt{Q.pop()}[/math]
if [math]\mathtt{Q} = \varnothing [/math]
break
else
[math] j \leftarrow \mathtt{Q.head()}[/math]
[math] \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot \mathtt{P.extractMax()} [/math]
[math] \mathtt{time}\texttt{++}[/math]
Данная реализация имеет идею, аналогичную предыдущей: сначала обрабатывать работу с максимальным весом среди всех доступных.
В начале работы сортируются по [math]r_i[/math], из очереди [math]\mathtt{Q}[/math] достаётся каждая работа, причём ровно один раз, аналогично для очереди [math]\mathtt{P}[/math], поэтому итоговая асимптотика времени работы алгоритма составляет [math]O(n \log n)[/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
- Лазарев А.А., Мусатова Е.Г., Кварацхелия А.Г., Гафаров Е.Р. Пособие по теории расписаний.