Жадный алгоритм с примерами: жадный метод & Подход

Содержание:

Anonim

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

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

Решение задачи на основе жадного подхода состоит из двух этапов.

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

Эти этапы параллельно рассматриваются в этом руководстве по жадному алгоритму в ходе деления массива.

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

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

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

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

В этом руководстве по жадному алгоритму вы узнаете:

  • История жадных алгоритмов
  • Жадные стратегии и решения
  • Характеристики жадного подхода
  • Зачем использовать жадный подход?
  • Как решить проблему выбора деятельности
  • Архитектура жадного подхода
  • Недостатки жадных алгоритмов

История жадных алгоритмов

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

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

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

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

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

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

Характеристики жадного подхода

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

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

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

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

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

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

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

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

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

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

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

ШАГ 1)

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

ШАГ 2)

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

ШАГ 3)

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

ШАГ 4)

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

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

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

#include#include#include#define MAX_ACTIVITIES 12

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

  1. Включенные файлы / классы заголовков
  2. Максимальное количество действий, предоставляемых пользователем.
using namespace std;class TIME{public:int hours;public: TIME(){hours = 0;}};

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

  1. Пространство имен для потоковых операций.
  2. Определение класса для ВРЕМЕНИ
  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. Массив объектов деятельности выделяется динамически с помощью оператора new.
  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. Функция выбора активности, которая возвращает указатель типа activity, возвращается вызывающей стороне после завершения жадного квеста.

Выход:

START:7 END 7START:9 END 10START:5 END 6START:10 END 10START:9 END 10Schedule start:5finish6activity:3Schedule start:9finish10activity:5

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

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

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

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

Ниже приводится описание недостатков жадного метода:

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

Однако, если алгоритм выбрал неоптимальный путь или принял стратегию завоевания. затем за 25 последует 40, и общее снижение затрат составит 65, что оценивается на 24 пункта выше как неоптимальное решение.

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

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

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

Резюме:

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