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

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

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

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

Продолжая теоретизирование, давайте опишем историю, связанную с подходом жадного поиска.

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

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

• Жадные алгоритмы были концептуализированы для многих алгоритмов обхода графа в 1950-х годах.
• Эсджер Джикстра концептуализировал алгоритм создания минимальных остовных деревьев. Он стремился сократить продолжительность маршрутов в столице Нидерландов Амстердаме.
• В том же десятилетии Прим и Краскал разработали стратегии оптимизации, основанные на минимизации затрат на пути по взвешенным маршрутам.
• В 70-х годах американские исследователи Кормен, Ривест и Стайн предложили рекурсивную подструктуру жадных решений в своей классической книге «Введение в алгоритмы».
• Парадигма жадного поиска была зарегистрирована как другой тип стратегии оптимизации в отчетах NIST в 2005 году.
• До сих пор протоколы, управляющие сетью, такие как OSPF и многие другие протоколы коммутации сетевых пакетов, используют жадную стратегию для минимизации времени, затрачиваемого в сети.

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

Логика в ее самой простой форме сводилась к «жадному» или «не жадному». Эти утверждения определялись подходом, принятым для продвижения на каждом этапе алгоритма.

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

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

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

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

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

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

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

• Жадный подход имеет несколько недостатков, которые могут сделать его пригодным для оптимизации.
• Одной из важных причин является немедленное достижение наиболее осуществимого решения. В задаче выбора действия (поясняется ниже), если до завершения текущего действия можно выполнить больше действий, эти действия можно выполнить за одно и то же время.
• Другая причина — рекурсивное разделение задачи на основе условия без необходимости объединять все решения.
• В задаче выбора действий шаг «рекурсивного деления» достигается путем однократного сканирования списка элементов и рассмотрения определенных действий.

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

В примере планирования действий для каждого действия есть время «начала» и «окончания». Каждое действие индексируется номером для справки. Есть две категории активности.

1. рассматриваемая деятельность: это действие, которое является эталоном, на основе которого анализируется способность выполнить более одного оставшегося действия.
2. оставшиеся мероприятия: активности по одному или нескольким индексам опережают рассматриваемую деятельность.

Общая продолжительность дает стоимость выполнения действия. То есть (окончание – начало) дает нам продолжительность как стоимость деятельности.

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

Archiтектура жадного подхода

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

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

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

ШАГ 4) Вернуть объединение рассматриваемых индексов. Это индексы активности, которые будут использоваться для максимизации пропускной способности.

Код Пояснение

#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. Определение класса из активности
2. Временные метки, определяющие продолжительность
3. Все временные метки инициализируются значением 0 в конструкторе по умолчанию.

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

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

1. Часть 1 определения класса планировщика.
2. Рассматриваемый индекс является отправной точкой для сканирования массив.
3. Индекс инициализации используется для назначения случайных временных меток.
4. Массив объектов активности динамически выделяется с помощью нового оператора.
5. Указатель расписания определяет текущее базовое местоположение для жадности.

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

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

1. Конструктор планировщика — часть 2 определения класса планировщика.
2. Рассматриваемый индекс определяет текущее начало текущего сканирования.
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);
 }
…
…

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

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

	public:
   		 Activity * activity_select(int);
};

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

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

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

1. Используя оператор разрешения области (::), предоставляется определение функции.
2. Рассматриваемый Индекс – это Индекс, называемый по значению. 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++;
    	}
…
...

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

1. Основная логика. Жадная степень ограничена количеством действий.
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. Создается новый планировщик.
3. Функция выбора активности, которая возвращает указатель типа активности, возвращается вызывающей стороне после завершения жадного квеста.

Вывод:

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

Большинство сетевых алгоритмов используют жадный подход. Вот список нескольких примеров жадных алгоритмов:

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

Резюме

Подводя итог, в статье определена жадная парадигма, показано, как жадная оптимизация и рекурсия могут помочь вам получить лучшее решение до определенного момента. Жадный алгоритм широко применяется для решения проблем на многих языках как Жадный алгоритм. Python, С, С#, PHP, Javaи т. д. Выбор активности в примере жадного алгоритма был описан как стратегическая задача, позволяющая достичь максимальной пропускной способности с помощью жадного подхода. В конце были объяснены недостатки использования жадного подхода.