Жадный алгоритм на примере: что такое, метод и подход

Что такое жадный алгоритм?

A Жадный алгоритм Рекурсивно разделяет набор ресурсов на основе максимальной непосредственной доступности этого ресурса на любом этапе выполнения.

Решение задачи с помощью жадного подхода состоит из двух этапов:

1. Сканирование списка предметов
2. Оптимизация

Оба этапа выполняются параллельно, поскольку входной массив постепенно делится.

Для использования жадного подхода вам пригодится знание рекурсии и переключения контекста. trace код. Жадную парадигму можно описать парой необходимых и достаточных утверждений.

Два условия определяют жадную парадигму.

• Каждый этап принятия решения должен направлять проблему к наиболее приемлемому варианту.
• Структура задачи должна остановиться через конечное число «жадных» шагов.

Разобравшись в теории, давайте рассмотрим историю возникновения подхода, основанного на жадном поиске.

История Жадности Algorithms

Вот важные вехи в истории жадных алгоритмов:

• Жадные алгоритмы впервые были разработаны для алгоритмов обхода графов в 1950-х годах.
• Эдсгер Дейкстра разработал алгоритм поиска кратчайшего пути для сокращения маршрутов в столице Нидерландов, Амстердаме.
• В том же десятилетии Прим и Крускал разработали стратегии оптимизации, которые минимизируют стоимость путей вдоль взвешенных маршрутов для построения минимальных остовных деревьев.
• В 70-х годах американские исследователи Кормен, Лейзерсон, Ривест и Стейн в своей классической работе описали рекурсивную субструктуризацию жадных решений. Introduction to Algorithms учебник.
• Парадигма жадного поиска была описана в записях NIST в 2005 году как отдельная стратегия оптимизации.
• И по сей день веб-протоколы, такие как OSPF (Open Shortest Path First) и многие протоколы пакетной коммутации, используют жадную стратегию для минимизации времени передачи данных в сети.

Жадные стратегии и решения

Логика сводится к бинарному выбору на каждом этапе — «жадный» или «нежадный» — в зависимости от направления, в котором алгоритм будет двигаться дальше.

Например, алгоритм Дейкстры идентифицирует хосты в интернете, вычисляя функцию стоимости на каждом шаге. Значение, возвращаемое функцией стоимости, определяет, будет ли следующий путь «жадным» или «нежадным».

Короче говоря, алгоритм перестаёт быть жадным в тот момент, когда он делает шаг, который не является локально оптимальным, и жадные задачи останавливаются, когда дальнейшие жадные шаги становятся невозможными.

Характеристики жадного алгоритма

Важными характеристиками жадного алгоритма являются:

• Упорядоченный список ресурсов содержит информацию о стоимости или ценности, которая количественно определяет ограничения, накладываемые на систему.
• Алгоритм выбирает максимальное количество ресурсов в течение времени, на которое распространяется ограничение.
• Например, в задаче планирования деятельности затраты на ресурсы измеряются в часах, а виды деятельности должны выполняться в последовательном порядке.

Зачем использовать жадный подход?

Вот причины использования жадного подхода:

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

Как решить задачу выбора вида деятельности

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

1. Рассматриваемая деятельность: Эталонный вид деятельности, от которого отталкивается оценка возможности включения в программу остальных видов деятельности.
2. Оставшиеся мероприятия: активности по одному или нескольким индексам опережают рассматриваемую деятельность.

Стоимость выполнения действия определяется его продолжительностью, которая рассчитывается как (конец – начало).

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

ArchiТехнология жадного подхода

Шаг 1) Просмотрите список затрат на деятельность, начиная с индекса 0, поскольку он является рассматриваемым индексом.

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

Шаг 3) Если больше нет запланированных мероприятий, текущее оставшееся мероприятие становится следующим рассматриваемым мероприятием. Повторите шаги 1 и 2 с новым рассматриваемым мероприятием. Если мероприятий больше нет, перейдите к шагу 4.

Шаг 4) Возвращает объединение рассматриваемых индексов — это индексы активности, которые максимизируют пропускную способность.

ArchiТехнология жадного подхода

Code объяснение

#include<iostream>
#include<stdio.h>
#include<stdlib.h>

#define MAX_ACTIVITIES 12

Расшифровка кода:

1. Включенные заголовочные файлы/классы
2. Максимальное количество действий, которые может настроить пользователь.

using namespace std;

class TIME
{
    public:
    int hours;

    public: TIME()
    {
   	 hours = 0;
    }
};

Расшифровка кода:

1. Объявляет стандартное пространство имен для потоковых операций.
2. Определение класса для TIME
3. Временная метка часа.
4. Конструктор TIME по умолчанию
5. Часы переменные.

class Activity
{
    public:
    int index;
    TIME start;
    TIME finish;

    public: Activity()
    {
   	 start = finish = TIME();
    }
};

Расшифровка кода:

1. Определение класса для Activity.
2. Временные метки, которые в совокупности определяют продолжительность.
3. В конструкторе по умолчанию все метки времени инициализируются значением 0.

class Scheduler
{
    public:
    int considered_index,init_index;
    Activity *current_activities = new    Activity[MAX_ACTIVITIES];
    Activity *scheduled;

Расшифровка кода:

1. Часть 1 определения класса планировщика.
2. considered_index — это начальная точка для сканирования массива.
3. Параметр init_index используется для присвоения случайных временных меток во время настройки.
4. С помощью нового оператора динамически выделяется массив объектов Activity.
5. Указатель scheduled хранит текущий результат жадного алгоритма.

Scheduler()
{
   	 considered_index = 0;
   	 scheduled = NULL;
...
...

Расшифровка кода:

1. Конструктор планировщика — часть 2 определения класса.
2. considered_index обозначает начало текущего сканирования.
3. В начале алгоритм жадного выбора не определен.

for(init_index = 0; init_index < MAX_ACTIVITIES; init_index++)
 {
   		 current_activities[init_index].start.hours =
   			 rand() % 12;

   		 current_activities[init_index].finish.hours =
   			 current_activities[init_index].start.hours +
   				 (rand() % 2);

   		 printf("\nSTART:%d END %d\n",
   		 current_activities[init_index].start.hours
   		 ,current_activities[init_index].finish.hours);
 }
&#8230;
&#8230;

Расшифровка кода:

1. Цикл for инициализирует время начала и окончания каждого запланированного действия.
2. Инициализирует время начала.
3. Устанавливает время окончания равным или более раннему часу начала.
4. Отладочная инструкция выводит на экран выделенное время.

	public:
   		 Activity * activity_select(int);
};

Расшифровка кода:

1. Часть 4 — заключительная часть определения класса Scheduler.
2. Функция activity_select() принимает начальный индекс в качестве базового и разделяет жадный поиск на подзадачи.

Activity * Scheduler :: activity_select(int considered_index)
{
    this->considered_index = considered_index;
    int greedy_extent = this->considered_index + 1;
…
…

1. Оператор разрешения области видимости (::) связывает определение функции с классом планировщика.
2. Параметр considered_index передается по значению, а greedy_extent инициализируется индексом, следующим непосредственно за ним.

Activity * Scheduler :: activity_select(int considered_index)
{
    	while( (greedy_extent < MAX_ACTIVITIES ) &&
   	 ((this->current_activities[greedy_extent]).start.hours <
   		 (this->current_activities[considered_index]).finish.hours ))
    	{
   	 printf("\nSchedule start:%d \nfinish%d\n activity:%d\n",
   	 (this->current_activities[greedy_extent]).start.hours,
   	 (this->current_activities[greedy_extent]).finish.hours,
   	 greedy_extent + 1);
   	 greedy_extent++;
    	}
&#8230;
...

Расшифровка кода:

1. Основная логика — жадный алгоритм ограничен значением MAX_ACTIVITIES.
2. Время начала текущей деятельности сверяется со временем окончания рассматриваемой деятельности.
3. Пока выполняется условие, выводится необязательное отладочное сообщение.
4. Затем алгоритм жадного поиска переходит к следующему индексу в массиве активности.

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

   	 return activity_select(greedy_extent);
    }
    else
    {
   	 return NULL;
    }
}

Расшифровка кода:

1. Условное выражение проверяет, были ли охвачены все виды деятельности.
2. В противном случае алгоритм перезапускает жадный поиск с текущего индекса — рекурсивный шаг, который жадно разделяет задачу.
3. Если да, то контроль возвращается к вызывающей стороне, и у нее не остается возможности проявлять жадность.

int main()
{
    Scheduler *activity_sched = new Scheduler();
    activity_sched->scheduled = activity_sched->activity_select(
   				activity_sched->considered_index);
    return 0;
}

Расшифровка кода:

1. Основная функция вызывает планировщик задач.
2. Создается новый объект Scheduler.
3. Функция activity_select() возвращает указатель на Activity вызывающей стороне после завершения жадного поиска.

Выход:

START:7 END 7

START:9 END 10

START:5 END 6

START:10 END 10

START:9 END 10

Schedule start:5
finish6
 activity:3

Schedule start:9
finish10
 activity:5

Ограничения жадной техники

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

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

Главный недостаток жадных алгоритмов заключается в том, что они делают выбор, не зная, что ждет их в текущем жадном состоянии.

Приведенная ниже диаграмма иллюстрирует этот недостаток жадного метода.

В представленном здесь в виде дерева алгоритме с жадным алгоритмом сканирования (чем выше значение, тем выше жадность) алгоритм со значением 40 выбрал бы следующий элемент — 29, затем остановился бы на 12, итого — 41.

Напротив, стратегия «разделяй и властвуй» предполагает, что после 25 получится 40, что в сумме составит 65, а это на 24 пункта больше, чем при локальном выборе.

Примеры жадности Algorithms

Большинство сетевых алгоритмов основаны на жадном подходе. Примерами распространенных жадных алгоритмов являются:

• Алгоритм построения минимального остовного дерева Прима
• Задача коммивояжера (приблизительная)
• Раскраска карты графика
• Алгоритм построения минимального остовного дерева Крускала
• Алгоритм кратчайшего пути Дейкстры
• Графовое покрытие вершин
• Проблема с рюкзаком
• Планирование последовательности выполнения задач с учетом сроков.

Часто задаваемые вопросы (FAQ)