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