Жадный алгоритм в задачах о покрытии/Задачи/lpt-rule-for-scheduling-p-is-2 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «<!-- cabook-ex-02-06-p98 --> Рассмотрим задачу Планирование Задач на Одинаковых Машинах и примени…») |
StasFomin (обсуждение | вклад) |
||
Строка 9: | Строка 9: | ||
Докажите, что в случае p=2, | Докажите, что в случае p=2, | ||
<latex> | <latex> | ||
− | M_{LPT}/OPT(x) < \ | + | M_{LPT}/OPT(x) < \frac{1}{3}\(4 — \frac1p\) |
</latex> | </latex> | ||
* OPT(x) — значение этого оптимального решения. | * OPT(x) — значение этого оптимального решения. |
Версия 13:14, 8 декабря 2017
Рассмотрим задачу Планирование Задач на Одинаковых Машинах
и применим к ней LPT[1]-эвристику:
- отсортировать задачи по убыванию длины
- для каждой задачи:
- применять жадный алгоритм загрузки: бросать задачу на самую малозагруженную машину
Докажите, что в случае p=2,
- OPT(x) — значение этого оптимального решения.
- — значение, найденное алгоритмом