Жадный алгоритм в задачах о покрытии/Задачи/lpt-rule-for-scheduling-p-is-2 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 8: | Строка 8: | ||
Докажите, что в случае p=2, | Докажите, что в случае p=2, | ||
| − | < | + | |
| − | M_{LPT}/OPT(x) < \frac{1}{3}\(4 — \frac1p\) | + | <m> |
| − | </ | + | M_{LPT}/OPT(x) < \frac{1}{3} \( 4 — \frac1p\) |
| + | </m> | ||
| + | |||
* OPT(x) — значение этого оптимального решения. | * OPT(x) — значение этого оптимального решения. | ||
* <m>M_{LPT}</m> — значение, найденное алгоритмом | * <m>M_{LPT}</m> — значение, найденное алгоритмом | ||
[[Категория:For-group-V]] | [[Категория:For-group-V]] | ||
Версия 13:16, 8 декабря 2017
Рассмотрим задачу Планирование Задач на Одинаковых Машинах
и применим к ней LPT[1]-эвристику:
- отсортировать задачи по убыванию длины
- для каждой задачи:
- применять жадный алгоритм загрузки: бросать задачу на самую малозагруженную машину
Докажите, что в случае p=2,
- OPT(x) — значение этого оптимального решения.
- — значение, найденное алгоритмом