Жадный алгоритм планирования?

Question

Что такое жадкое решение проблемы с расписанием при запуске (например, 5 минут, 10 минут, а не время начала и окончания) проблемы, и у вас есть m процесс запуска их, а затем минимальное максимальное время?
Предположим, у меня есть девять рабочих мест (3,5,6,10,11,14,15,18,20 минут) и три процесса, то решение

1-й дескриптор процесса -> 20 + 14

2-й дескриптор процесса -> 18 + 11 +5

третьего дескриптора процесс -> 15 + 10 + 6 +-

minmimum время 34 минут

Answer 1

Учитывая, что проблема NP-трудная (see for example here), маловероятно, чтобы полином tim существует алгоритм, который дает точное решение во всех случаях.

Answer 2

Прежде всего, смотрите на странице Википедия: https://en.wikipedia.org/wiki/Greedy_algorithm

Из первой части статьи:

Жадный алгоритм является алгоритмом, который следует решать проблемы эвристики сделать локально оптимальный выбор на каждом этапе с надеждой найти глобальный оптимум. Во многих задачах, жадная стратегия в общем случае не получения оптимального решения ...

Есть 2 важных момента, чтобы выделить здесь:

1. Жадный алгоритм не обязательно собирается найти Оптимальное решение.

2. Существует множество различных жадных подходов к решению одной проблемы.

Используя вашу проблему в качестве примера, оба этих подхода являются жадными:

Жадный подход # 1: Поскольку каждый процесс становится доступным, назначьте самую длинную задачу процесса. Это может дать следующие результаты:

Процесс 1: 20 + 10 + 3 = 33

Процесс 2: 18 + 11 + 6 = 35

Способ 3: 15 + 14 + 5 = 34

Общее время: 35

Жадный подход # 2: Поскольку каждый процесс становится доступным, назначить самый короткий задача для процесса.Это дало бы следующие результаты:

Процесс 1: 3 + 10 + 15 = 28

Процесс 2: 5 + 11 + 18 = 34

Способ 3: 6 + 14 + 20 = 40

Общее время: 40

Оба эти подхода жадные алгоритмы. Одно большое предположение заключается в том, что проблема состоит в том, чтобы просто обрабатывать все задачи. Если проблема состоит в том, чтобы обрабатывать все задачи в кратчайшие сроки, то (как уже было сказано в комментариях) нет жадного алгоритма, который мог бы решить эту проблему.