Жадібний алгоритм із прикладом: що таке, метод і підхід

Що таке жадібний алгоритм?

A Жадібний алгоритм рекурсивно ділить набір ресурсів на основі максимальної негайної доступності цього ресурсу на будь-якому етапі виконання.

Вирішення проблеми за допомогою жадібного підходу складається з двох етапів:

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

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

Щоб дотримуватися жадібного підходу, вам допоможуть практичні знання рекурсії та перемикання контексту. tracе код. Жадібну парадигму можна описати парою необхідних і достатніх тверджень.

Парадигму жадібності визначають дві умови.

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

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

Історія Greedy Algorithms

Ось важливі віхи в історії жадібних алгоритмів:

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

Жадібні стратегії та рішення

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

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

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

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

Важливими характеристиками жадібного алгоритму є:

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

Навіщо використовувати жадібний підхід?

Ось причини використання жадібного підходу:

• Жадібний підхід має компроміси, які роблять його добре придатним для оптимізації.
• Найбільш очевидною причиною є необхідність негайного пошуку можливих рішень. У задачі вибору дій, що обговорюється нижче, якщо до завершення поточної дії поміщається більше дій, їх можна запланувати в одному вікні.
• Ще одна причина полягає в тому, що він рекурсивно розділяє задачу на основі умови, без необхідності об'єднувати підрозв'язки.
• У задачі вибору діяльності рекурсивний крок ділення досягається шляхом одноразового сканування списку та розгляду лише відповідних дій.

Як вирішити проблему вибору активності

У прикладі планування діяльності кожна діяльність має час початку та завершення й індексується числом для довідки. Існує дві категорії діяльності:

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 динамічно виділяється за допомогою оператора new.
5. Запланований вказівник містить поточний жадібний результат.

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. Оператор розв'язання області видимості (::) пов'язує визначення функції з класом Scheduler.
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. Функція main викликає планувальник.
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 бали більше, ніж вибір локально жадібного розподілу.

Приклади Greedy Algorithms

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

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

Поширені запитання