Алчен алгоритъм с пример: какво е, метод и подход

по: Сара Чен Сара Чен
Hours Обновено

⚡ Умно обобщение

Дизайнът на алчния алгоритъм изгражда оптимално решение, като прави най-добрия локален избор на всяка стъпка, използвайки рекурсия, подредени ресурси и условие за спиране, за да реши ефективно проблемите с планирането, обхващащото дърво, най-краткия път и оптимизацията на мрежата.

  • 📘 Определение: Алчният алгоритъм рекурсивно избира локално оптималния избор на всяка стъпка, целяйки глобално приемливо решение.
  • 📜 История: Дейкстра, Прим и Крускал оформят парадигмата през 1950-те години на миналия век, а по-късно CLRS я формализира като отделна дизайнерска техника.
  • 🧭 Две условия: Всяка стъпка трябва да насочва проблема към най-доброто му решение, а процесът трябва да спира в краен брой алчни стъпки.
  • 📅 Избор на дейност: Класически примерни графици без припокриванеping дейности чрез сравняване на разглежданите и оставащите начални и крайни времена.
  • ⚠️ Ограничения: Алчността се проваля, когато локалните избори не могат да гарантират глобален оптимум, както при сортирането или общия проблем на търговския пътник.
  • 🌐 Често срещани примери: Дейкстра, Прим, Крускал, кодирането на Хъфман, дробната раница и последователността на задачите с крайни срокове използват алчна стратегия.
Прочетете повече

Алчен алгоритъм с пример: какво е, метод и подход

Какво е алчен алгоритъм?

A Алчен алгоритъм рекурсивно разделя набор от ресурси въз основа на максималната непосредствена наличност на този ресурс на всеки етап от изпълнението.

Решаването на проблем с алчния подход се състои от два етапа:

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

И двата етапа протичат паралелно, тъй като входният масив се разделя прогресивно.

За да следвате алчния подход, познанията за рекурсия и превключване на контекста ще ви помогнат. trace кода. Алчната парадигма може да бъде описана с двойка необходими и достатъчни твърдения.

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

  • Всеки поетапен избор трябва да насочва проблема към най-добре приетото му решение.
  • Структурата на проблема трябва да спре в краен брой алчни стъпки.

След като теорията е налице, нека разгледаме историята зад подхода на алчното търсене.

История на Greedy Algorithms

Ето важните етапи в историята на алчните алгоритми:

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

Алчни стратегии и решения

Логиката се свежда до двоичен избор на всеки етап – „алчен“ или „неалчен“ – въз основа на посоката, която алгоритъмът поема, за да напредне.

Например, алгоритъмът на Дейкстра идентифицира хостове в интернет, като оценява функция на разходите на всяка стъпка. Стойността, която функцията на разходите връща, определя дали следващият път е „алчен“ или „неалчен“.

Накратко, един алгоритъм спира да бъде алчен в момента, в който предприеме стъпка, която не е локално оптимална, а алчните проблеми спират, когато не е възможна по-нататъшна алчна стъпка.

Характеристики на алчния алгоритъм

Важните характеристики на Greedy алгоритъм са:

  • Подреденият списък с ресурси носи атрибути на стойност или цена, които количествено определят ограниченията на системата.
  • Алгоритъмът използва максималното количество ресурси в рамките на времето, за което се прилага ограничението.
  • Например, при задача за планиране на дейности, разходите за ресурси се измерват в часове, а дейностите трябва да се изпълняват последователно.

Характеристики на алчния алгоритъм

Защо да използваме алчния подход?

Ето причините за използването на алчния подход:

  • Алчният подход има компромиси, които го правят подходящ за оптимизация.
  • Най-очевидната причина е незабавното създаване на осъществимо решение. В проблема за избор на дейност, обсъден по-долу, ако се поберат още дейности, преди текущата дейност да приключи, те могат да бъдат планирани в един и същ прозорец.
  • Друга причина е, че разделя проблема рекурсивно въз основа на условие, без да е необходимо да се обединяват подрешения.
  • В задачата за избор на дейност, стъпката на рекурсивно деление се постига чрез еднократно сканиране на списъка и разглеждане само на допустимите дейности.

Как да решим проблема с избора на дейност

В примера за планиране на дейности, всяка дейност има начален и краен час и е индексирана с число за справка. Има две категории дейности:

  1. Разглеждана дейност: референтната дейност, от която се измерва способността за включване на още оставащи дейности.
  2. Оставащи дейности: дейности с един или повече индекси пред разглежданата дейност.

Цената за извършване на дадена дейност е нейната продължителност, изчислена като (край – начало).

Алчният обхват е просто броят на оставащите дейности, които могат да бъдат изпълнени в рамките на времето на разглежданата дейност.

СВЪРЗАНИ СТАТИИ

Archiструктура на алчния подход

Стъпка 1) Прегледайте списъка с разходи за дейности, започвайки с индекс 0 като разглеждан индекс.

Стъпка 2) Когато до края на разглежданата дейност могат да приключат още дейности, потърсете останалите дейности.

Стъпка 3) Ако не могат да се планират повече дейности, текущата оставаща дейност става следващата разглеждана дейност. Повторете стъпка 1 и стъпка 2 с новата разглеждана дейност. Ако не останат дейности, преминете към стъпка 4.

Стъпка 4) Върнете обединението на разглежданите индекси — това са индексите на активност, които максимизират пропускателната способност.

Archiструктура на алчния подход

Archiструктура на алчния подход

Code Обяснение

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

#define MAX_ACTIVITIES 12

Archiструктура на алчния подход

Обяснение на кода:

  1. Включени заглавни файлове/класове
  2. Максималният брой дейности, които потребителят може да конфигурира.
using namespace std;

class TIME
{
    public:
    int hours;

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

Archiструктура на алчния подход

Обяснение на кода:

  1. Декларира стандартното пространство от имена за стрийминг операции.
  2. Дефиниция на клас за TIME
  3. Часов печат.
  4. Конструктор по подразбиране на TIME
  5. Променливите часове.
class Activity
{
    public:
    int index;
    TIME start;
    TIME finish;

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

Archiструктура на алчния подход

Обяснение на кода:

  1. Дефиниция на клас за Дейност.
  2. Времеви марки, които заедно определят продължителност.
  3. Всички времеви отметки се инициализират на 0 в конструктора по подразбиране.
class Scheduler
{
    public:
    int considered_index,init_index;
    Activity *current_activities = new    Activity[MAX_ACTIVITIES];
    Activity *scheduled;

Archiструктура на алчния подход

Обяснение на кода:

  1. Част 1 от дефиницията на класа на планировчика.
  2. considered_index е началната точка за сканиране на масива.
  3. init_index се използва за задаване на произволни времеви отметки по време на настройката.
  4. Масив от обекти Activity се разпределя динамично с оператора new.
  5. Планираният указател съдържа текущия алчен резултат.
Scheduler()
{
   	 considered_index = 0;
   	 scheduled = NULL;
...
...

Archiструктура на алчния подход

Обяснение на кода:

  1. Конструкторът на Scheduler — част 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;

Archiструктура на алчния подход

Обяснение на кода:

  1. Цикълът for инициализира началния и крайния час на всяка планирана дейност.
  2. Инициализира началното време.
  3. Инициализира крайния час да бъде същият или след началния час.
  4. Дебъг оператор отпечатва разпределените продължителности.
	public:
   		 Activity * activity_select(int);
};

Archiструктура на алчния подход

Обяснение на кода:

  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;
&#8230;
&#8230;

Archiструктура на алчния подход

  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;
...

Archiструктура на алчния подход

Обяснение на кода:

  1. Основната логика — алчният обхват е ограничен до MAX_ACTIVITIES.
  2. Началният час на текущата дейност се сравнява с крайния час на разглежданата дейност.
  3. Докато условието е изпълнено, се отпечатва опционален дебъг оператор.
  4. След това алчният екстент преминава към следващия индекс в масива от дейности.
...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

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

Archiструктура на алчния подход

Обяснение на кода:

  1. Условието проверява дали всички дейности са обхванати.
  2. Ако не, алгоритъмът рестартира алчното търсене от текущия индекс – рекурсивна стъпка, която разделя проблема алчно.
  3. Ако отговорът е „да“, контролът се връща на обаждащия се, без възможност за разширяване на алчността.
int main()
{
    Scheduler *activity_sched = new Scheduler();
    activity_sched->scheduled = activity_sched->activity_select(
   				activity_sched->considered_index);
    return 0;
}

Archiструктура на алчния подход

Обяснение на кода:

  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 пункта повече от локално алчния избор.

Примери за Greedy Algorithms

Повечето мрежови алгоритми разчитат на алчен подход. Често срещани примери за алчни алгоритми включват:

  • Алгоритъмът за минимално обхващащо дърво на Прим
  • Задача на пътуващия търговец (приблизително)
  • Оцветяване на графична карта
  • Алгоритъмът за минимално обхващащо дърво на Крускал
  • Алгоритъмът за най-кратък път на Дейкстра
  • Покритие на върха на графа
  • Проблем с раницата
  • Последователност на работата с крайни срокове

Въпроси и Отговори

Алчните алгоритми са в основата на разделянето на дърветата на решенията, обвивките за избор на характеристики и търсенето на лъчи в трансформаторните декодери. Системите с изкуствен интелект също използват алчно предварително обучение на слоеве и алчна итерация на политики в обучението с подсилване, за да достигнат по-бързо до силни локални оптимуми.

Copilot и GPT scaffold кодиране на Дейкстра, Крускал, Хъфман и рутини за избор на дейности в Python, C++ или JavaРазработчиците все още валидират свойството на алчния избор и оптималната подструктура преди пускането им в експлоатация.ping, тъй като кодът с изкуствен интелект може да пропусне гранични случаи.

Алчният човек прави един локално оптимален избор на стъпка и никога не го преразглежда. Динамичното програмиране изследва припокриването.ping подзадачи и съхранява резултатите в таблица, за да гарантира глобален оптимум. Алчният метод е по-бърз, но работи само когато е налице свойството на алчния избор.

Свойството на алчния избор означава, че глобален оптимум може да бъде достигнат чрез локално оптимални избори. Оптималната подструктура означава, че оптималното решение на проблема съдържа оптимални решения на своите подзадачи. И двете условия трябва да са налице, за да бъде алчният алгоритъм доказуемо правилен.

Изборът на активност се извършва за O(n log n) след сортиране по време на завършване. Дейкстра с двоичен heap е O((V + E) log V). Крускал е O(E log E) с union-find. Хъфмановото кодиране е O(n log n). Сортирането обикновено доминира сложността.

Алчните алгоритми захранват GPS маршрутизацията (Dijkstra), мрежовия дизайн (Prim, Kruskal), компресията на файлове (Huffman), планирането на процесора и диска, балансирането на натоварването, обмяната на монети в касови апарати и протоколите за маршрутизиране на пакети като OSPF и BGP.

Алчността се проваля, когато локално оптималните избори водят до глобално по-лош резултат. Общият проблем на търговския пътник, раницата 0/1 и рестото на монети с неканонични купюри са класически случаи, при които алчността е неоптимална и се изисква динамично програмиране.

Двете стандартни техники са аргумент за размяна и „алчният остава напред“. В аргумент за размяна вие заменяте всеки неалчен избор с алчния, без да влошавате решението. „Алчният остава напред“ сравнява частично алчни и оптимални решения стъпка по стъпка.

Обобщете тази публикация с: