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

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

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

За да разрешите проблем, базиран на алчния подход, има два етапа

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

Тези етапи се разглеждат паралелно в този урок за алгоритъм на Greedy, в хода на разделянето на масива.

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

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

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

С продължаване на теоретизирането, нека опишем историята, свързана с подхода на Greedy search.

История на Greedy Algorithms

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

  • Алчните алгоритми са концептуализирани за много алгоритми за обхождане на графики през 1950-те години.
  • Esdger Djikstra концептуализира алгоритъма за генериране на минимални обхващащи дървета. Той имаше за цел да съкрати обхвата на маршрутите в холандската столица Амстердам.
  • През същото десетилетие Прим и Крускал постигнаха стратегии за оптимизация, които се основаваха на минимизиране на разходите за маршрути по претеглени маршрути.
  • През 70-те години американските изследователи Кормен, Ривест и Стайн предложиха рекурсивно подструктуриране на алчни решения в тяхната класическа книга за въведение в алгоритмите.
  • Парадигмата за алчно търсене е регистрирана като различен тип стратегия за оптимизация в записите на NIST през 2005 г.
  • Досега протоколите, които управляват мрежата, като първо отваряне по най-краткия път (OSPF) и много други мрежови протоколи за превключване на пакети, използват алчната стратегия за минимизиране на времето, прекарано в мрежа.

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

Логиката в най-лесната си форма беше сведена до „алчен“ или „не алчен“. Тези твърдения бяха определени от подхода, предприет за напредък във всеки етап на алгоритъма.

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

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

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

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

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

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

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

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

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

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

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

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

Общата продължителност дава разходите за извършване на дейността. Това е (край – начало) ни дава продължителността като цена на дейност.

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

Archiструктура на Greedy подхода

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

ЕТАП 2) Когато повече дейности могат да бъдат завършени до времето, разглежданата дейност приключи, започнете да търсите една или повече оставащи дейности.

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

СТЪПКА 4 ) Връща обединението на разглежданите индекси. Това са индексите на дейност, които ще се използват за максимизиране на производителността.

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

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

#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. Разглежданият индекс е отправната точка за сканиране на масив.
  3. Индексът за инициализация се използва за присвояване на произволни времеви отпечатъци.
  4. Масив от обекти на дейност се разпределя динамично с помощта на оператора new.
  5. Планираният указател определя текущото базово местоположение за алчност.
Scheduler()
{
   	 considered_index = 0;
   	 scheduled = NULL;
...
...

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

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

  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);
 }
…
…

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

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

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

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

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

  1. Част 4 – последната част от дефиницията на класа на планировчика.
  2. Функцията за избор на дейност взема индекс на начална точка като основа и разделя алчното търсене на алчни подпроблеми.
Activity * Scheduler :: activity_select(int considered_index)
{
    this->considered_index = considered_index;
    int greedy_extent = this->considered_index + 1;
…
… 

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

  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++;
    	}
…
...

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

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

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

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

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

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

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

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

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

  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

Ограничения на алчната техника

Не е подходящ за алчни проблеми, където се изисква решение за всеки подпроблем като сортиране.

При такива практически проблеми с алгоритъма на Greedy методът на Greedy може да е грешен; в най-лошия случай дори да доведе до неоптимално решение.

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

По-долу е изображение на недостатъка на метода Greedy:

Ограничения на алчната техника

В алчното сканиране, показано тук като дърво (по-висока стойност, по-висока алчност), състояние на алгоритъм при стойност: 40 вероятно ще приеме 29 като следваща стойност. Освен това търсенето му завършва на 12. Това възлиза на стойност 41.

Въпреки това, ако алгоритъмът пое по неоптимален път или възприеме завладяваща стратегия. тогава 25 ще бъде последвано от 40 и цялостното подобрение на разходите ще бъде 65, което се оценява с 24 точки по-високо като неоптимално решение.

Примери за Greedy Algorithms

Повечето мрежови алгоритми използват алчния подход. Ето списък с няколко примера за алгоритъм на Greedy:

  • Алгоритъмът на Prim за минимално обхващащо дърво
  • Проблем с пътуващ продавач
  • Графика – Оцветяване на картата
  • Алгоритъмът на Kruskal за минимално обхващащо дърво
  • Алгоритъмът за минимално обхващащо дърво на Дейкстра
  • Graph – Vertex Cover
  • Проблем с раницата
  • Проблем с планирането на работата

Oбобщение

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