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

Зміст:

Anonim

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

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

Для вирішення проблеми, заснованої на жадібному підході, існує два етапи

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

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

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

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

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

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

У цьому підручнику з жадібних алгоритмів ви дізнаєтесь:

  • Історія жадібних алгоритмів
  • Жадібні стратегії та рішення
  • Характеристика жадібного підходу
  • Навіщо використовувати жадібний підхід?
  • Як вирішити проблему вибору діяльності
  • Архітектура жадібного підходу
  • Недоліки жадібних алгоритмів

Історія жадібних алгоритмів

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

  • Жадібні алгоритми були концептуалізовані для багатьох алгоритмів графіка графіка в 1950-х.
  • Есджер Джікстра розробив концептуальний алгоритм для створення мінімальних охоплюючих дерев. Він мав на меті скоротити діапазон маршрутів у столиці Нідерландів Амстердамі.
  • У тому ж десятилітті Прим і Крускал досягли стратегій оптимізації, які базувались на мінімізації витрат на шляху вздовж зважених маршрутів.
  • У 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. Визначення класу для 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 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 пункти вище як неоптимальне рішення.

Приклади жадібних алгоритмів

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

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

Короткий зміст:

Підводячи підсумок, стаття визначила жадібну парадигму, показала, як жадібна оптимізація та рекурсія можуть допомогти вам отримати найкраще рішення до певного моменту. Алгоритм Жадібний широко застосовується для розв’язання проблем багатьма мовами, як жадібний алгоритм Python, C, C #, PHP, Java та ін підхід. Врешті-решт, були пояснені недоліки використання жадібного підходу.