1632
правки
Изменения
м
rollbackEdits.php mass rollback
<tex dpi ="200"> 1 \mid r_i,p_i =Постановка задачи==1 \mid \sum w_i C_i</tex> Рассмотрим задачу:{{Задача<ol>|definition=<li>Дано <tex>n</tex> работ и один станок.</li><li>Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>.Требуется выполнить все работы, чтобы значение <tex>\sum w_{i} C_{i}</tex> было минимальным, где <tex>C_{i}</tex> {{---}} время окончания работы.}} ==Более простые варианты исходной задачи== Перед решением основной задачи рассмотрим более простые. ===Вариант 1===<tex> 1 \mid p_i = 1\mid \sum C_i</tex> Этот случай простейший. Ответом будет <tex>\sum\limits_{k = 1}^n k</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы. Воспользовавшись формулой суммы первых <tex>n</litex>членов арифметической прогрессии алгоритм <tex>S_n=\dfrac{a_1+a_n}2 \cdot n</tex> будет работает за <tex>O(1)</tex>, но если нужно вывести и само расписание, время работы будет <tex>O(n)</tex>. ===Вариант 2===<tex> 1 \mid p_i = 1\mid \sum w_i C_i</oltex>Требуется выполнить все Для верного выполнения просто выставим работыпо порядку невозрастания весов, чтобы значение тогда ответом будет <tex>\sum w_\limits_{i= 1} c_^nw_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>time</tex> {{---}} текущий момент времени.<br/>
Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:
<ol>
<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \le leqslant time</tex>, а значение <tex>w_{i}</tex> максимально.</li>
<li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li>
<li> Увеличиваем <tex>time</tex> на один.</li>
</ol>
===Доказательство корректности алгоритма===
{{Теорема
|statement=
Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/>
При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на
<ul><tex>(t_{1} - r_{2})w_{2} + (t_{2} - r_{1})w_{1} - ((t_{1} - r_{1})w_{1} + (t_{2} - r_{2})w_{2}) = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})</tex></ul>
Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/>
Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.
}}
===Псевдокод=== ====Реализация 1==== <tex> S \leftarrow \{1 \dots ldots n\}</tex> <tex> \mathtt{time } \leftarrow 0</tex> <tex> \mathtt{answer } \leftarrow 0</tex> '''while ''' <tex> S \neq \varnothing </tex> <tex> j \leftarrow null </tex> '''if''' <tex> i \in S</tex> '''and''' <tex> r_{i : (} \leqslant \mathtt{time}</tex> '''and''' <tex>w_i \geqslant \max \limits_{i j \in S, r_{ij = 1 \ldots n} w_j</tex> <tex> j \leq time} w_{leftarrow i})</tex> '''if ''' <tex>j \neq null </tex>
<tex> S \leftarrow S \setminus j</tex>
<tex> \mathtt{Answer } \leftarrow \mathtt{Answer } + \mathtt{time} \cdot w_{j}</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====* <tex>\mathtt{Q}</tex> {{---}} обычная [[Очередь | очередь]], в которой работы изначально располагаются в отсортированном по <tex>r_i</tex> порядке,* <tex>\mathtt{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()}w_</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> Данная реализация имеет идею, аналогичную предыдущей: сначала обрабатывать работу с максимальным весом среди всех доступных.В начале работы сортируются по <tex>r_i</tex>, из очереди <tex>\mathtt{Q}</tex> достаётся каждая работа, причём ровно один раз, аналогично для очереди <tex>\mathtt{P}</tex>, поэтому итоговая асимптотика времени работы алгоритма составляет <tex>O(n \log n)</tex>. ==См. также==* [[Классификация задач]]* [[1outtreesumwc|<tex>1 \mid outtree \mid \sum w_i C_i</tex>]]* [[1ridipi1|<tex>1 | r_{i}, d_{i}, p_{i}=1 | -</tex>]]
==Сложность алгоритмаИсточники информации==Множество <tex>S</tex> станет пустым не позже* P. Brucker. Scheduling Algorithms (2006), 5th edition, чем через <tex>n + \max r_{i}</tex> шагов цикластр. 19-20* P. Определить максимум в множестве можно за время <tex>OBrucker. Scheduling Algorithms (\log n2006)</tex>, используя 5th edition, например, очередь с приоритетамистр. 38-39* P. Brucker. Значит общее время работы алгоритма <tex>OScheduling Algorithms ((n + \max r_{i}2006)\log n)</tex>, 5th edition, стр. 84-85* Лазарев А.А., Мусатова Е.Г., Кварацхелия А.Г., Гафаров Е.Р. Пособие по теории расписаний.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
