Планирование в жадных алгоритмах

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

Постановка задачи: Имея N событий с указанием времени их начала и окончания, найдите расписание, включающее как можно больше событий. Невозможно выбрать событие частично. Рассмотрим следующие события:

• В этом случае максимальное количество событий равно двум. В качестве выбранных событий B и D используются следующие:

• Для решения задачи можно придумать несколько жадных алгоритмов.

Алгоритмы, которые работают с каждым случаем:

Алгоритм 1 :

• Первая идея состоит в том, чтобы выбрать как можно более короткие события. В примере этот алгоритм выбирает следующие события:

• Однако выбор коротких событий не всегда является правильной стратегией. Например, алгоритм не работает в следующем случае:

• Если выбрано короткое событие, можно выбрать только одно событие. Однако можно было бы выбрать оба длинных события.

Алгоритм 2 :

• Другая идея состоит в том, чтобы всегда выбирать следующее возможное событие, которое начинается как можно раньше. Этот алгоритм выбирает следующие события:

• Тем не менее, приведен встречный пример для этого алгоритма. В этом случае алгоритм выбирает только одно событие:

• Если выбрано первое событие, другие события выбрать невозможно. Однако можно было бы выбрать два других события.

Алгоритм 3 :

• Третья идея состоит в том, чтобы всегда выбирать следующее возможное событие, которое заканчивается как можно раньше. Этот алгоритм выбирает следующие события:

• Оказывается, этот алгоритм всегда дает оптимальное решение.
• Причина этого в том, что всегда оптимальным выбором будет сначала выбрать событие, которое заканчивается как можно раньше.
• После этого оптимальным выбором является выбор следующего события с использованием той же стратегии и т. д., пока любое другое событие не может быть выбрано.
• Один из способов работы алгоритма — рассмотреть, что произойдет, если сначала выбрать событие, которое заканчивается позже, чем событие, которое заканчивается как можно раньше.
• Теперь, имея не более равного количества вариантов выбора следующего события.
• Следовательно, выбор события, которое заканчивается позже, никогда не даст лучшего решения, и жадный алгоритм верен.