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