Какво е алчен алгоритъм?
В алчния алгоритъм набор от ресурси се разделя рекурсивно въз основа на максималната, непосредствена наличност на този ресурс на всеки даден етап на изпълнение.
За да се реши проблем, базиран на алчния подход, има два етапа
- Сканиране на списъка с елементи
- Оптимизация
Тези етапи са обхванати паралелно в този урок за алчен алгоритъм, в хода на разделяне на масива.
За да разберете алчния подход, ще трябва да имате работещи познания за рекурсия и превключване на контекста. Това ви помага да разберете как да проследите кода. Можете да определите алчната парадигма от гледна точка на вашите нужни и достатъчни твърдения.
Две условия определят алчната парадигма.
- Всяко поетапно решение трябва да структурира проблема към най-добре приетото му решение.
- Достатъчно е, ако структурирането на проблема може да спре в краен брой алчни стъпки.
С продължаването на теоретизирането, нека опишем историята, свързана с алчния подход за търсене.
В този урок за алчен алгоритъм ще научите:
- История на алчните алгоритми
- Алчни стратегии и решения
- Характеристики на алчния подход
- Защо да използваме алчния подход?
- Как да решим проблема за избор на дейност
- Архитектура на алчния подход
- Недостатъци на алчните алгоритми
История на алчните алгоритми
Ето важна забележителност на алчните алгоритми:
- Алчните алгоритми са концептуализирани за много алгоритми за разходка на графики през 50-те години.
- Есджер Джикстра концептуализира алгоритъма за генериране на минимално обхващащи се дървета. Той имаше за цел да съкрати обхвата на маршрутите в холандската столица Амстердам.
- През същото десетилетие Prim и Kruskal постигнаха стратегии за оптимизация, които се основаваха на минимизиране на разходите по пътя по претеглените маршрути.
- През 70-те американски изследователи Кормен, Ривест и Стайн предлагат рекурсивна подструктура на алчни решения в своето класическо въведение в книгата за алгоритмите.
- Парадигмата за алчното търсене е регистрирана като различен тип стратегия за оптимизация в записите на NIST през 2005 г.
- До момента протоколи, които работят в мрежата, като например отворения най-кратък път (OSPF) и много други протоколи за превключване на мрежови пакети, използват алчната стратегия за минимизиране на времето, прекарано в мрежата.
Алчни стратегии и решения
Логиката в най-лесния си вид се свеждаше до „алчен“ или „не алчен“. Тези твърдения бяха дефинирани от подхода, предприет за напредък във всеки етап от алгоритъма.
Например алгоритъмът на Джикстра използва стъпаловидно алчна стратегия за идентифициране на хостове в Интернет чрез изчисляване на функция на разходите. Стойността, върната от функцията за разходи, определя дали следващият път е „алчен“ или „не-алчен“.
Накратко, алгоритъмът престава да бъде алчен, ако на който и да е етап направи стъпка, която не е лакома на местно ниво. Алчните проблеми спират без допълнителен обхват на алчността.
Характеристики на алчния подход
Важните характеристики на алчния алгоритъм на алчен метод са:
- Има подреден списък с ресурси, с разходи или атрибуции на стойност. Те количествено определят ограниченията върху системата.
- Ще вземете максималното количество ресурси за времето, когато се прилага ограничението.
- Например при проблем с планиране на дейности разходите за ресурси са в часове и дейностите трябва да се извършват в сериен ред.
Защо да използваме алчния подход?
Ето причините за използването на алчния подход:
- Алчният подход има няколко компромиса, което може да го направи подходящ за оптимизация.
- Една изтъкната причина е незабавното постигане на най-осъществимото решение. В проблема за избор на дейност (Обяснено по-долу), ако повече дейности могат да бъдат извършени преди приключване на текущата дейност, тези дейности могат да бъдат извършени в рамките на едно и също време.
- Друга причина е да разделите проблема рекурсивно въз основа на условие, без да е необходимо да комбинирате всички решения.
- В проблема за избор на дейност стъпката „рекурсивно разделяне“ се постига чрез сканиране на списък с елементи само веднъж и разглеждане на определени дейности.
Как да решим проблема за избор на дейност
В примера за планиране на дейности има време за "начало" и "завършване" за всяка дейност. Всяка дейност се индексира с номер за справка. Има две категории дейности.
- разглеждана дейност : е активността, която е препратката, от която се анализира способността за извършване на повече от една останала дейност.
- останали дейности: дейности с един или повече индекси преди разглежданата дейност.
Общата продължителност дава разходите за извършване на дейността. Това е (завърши - започни) ни дава продължителността като цена на дадена дейност.
Ще научите, че алчната степен е броят на останалите дейности, които можете да извършите по време на разглежданата дейност.
Архитектура на алчния подход
ЕТАП 1)
Сканирайте списъка с разходите за дейност, започвайки с индекс 0 като разглеждания индекс.
СТЪПКА 2)
Когато по това време могат да бъдат завършени повече дейности, разглежданата дейност завършва, започнете да търсите една или повече останали дейности.
СТЪПКА 3)
Ако няма повече останали дейности, текущата оставаща дейност се превръща в следващата разглеждана дейност. Повторете стъпка 1 и стъпка 2 с новата разгледана дейност. Ако не останат останали дейности, преминете към стъпка 4.
СТЪПКА 4)
Върнете обединението на разглежданите индекси. Това са индексите на активността, които ще се използват за максимизиране на производителността.
Обяснение на кода
#include#include #include #define MAX_ACTIVITIES 12
Обяснение на кода:
- Включени заглавни файлове / класове
- Максимален брой дейности, предоставени от потребителя.
using namespace std;class TIME{public:int hours;public: TIME(){hours = 0;}};
Обяснение на кода:
- Пространството от имена за поточни операции.
- Дефиниция на клас за TIME
- Клеймо за час.
- Конструктор по подразбиране TIME
- Променливата на часовете.
class Activity{public:int index;TIME start;TIME finish;public: Activity(){start = finish = TIME();}};
Обяснение на кода:
- Определение на клас от дейност
- Времеви марки, определящи продължителност
- Всички времеви марки са инициализирани на 0 в конструктора по подразбиране
class Scheduler{public:int considered_index,init_index;Activity *current_activities = new Activity[MAX_ACTIVITIES];Activity *scheduled;
Обяснение на кода:
- Част 1 от дефиницията на класа на планировчика.
- Считаният индекс е отправна точка за сканиране на масива.
- Индексът за инициализация се използва за присвояване на произволни времеви марки.
- С помощта на новия оператор динамично се разпределя масив от обекти на дейност.
- Планираният указател определя текущото основно местоположение за алчност.
Scheduler(){considered_index = 0;scheduled = NULL;… …
Обяснение на кода:
- Конструктор на планировщика - част 2 от дефиницията на класа на планировчика.
- Разглежданият индекс определя текущото начало на текущото сканиране.
- Текущата алчна степен не е дефинирана в началото.
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);}… …
Обяснение на кода:
- Цикъл for за инициализиране на началните часове и крайните часове на всяка от планираните в момента дейности.
- Инициализация на началния час.
- Инициализация на крайния час винаги след или точно в началния час.
- Изявление за отстраняване на грешки за отпечатване на разпределени продължителности.
public:Activity * activity_select(int);};
Обяснение на кода:
- Част 4 - последната част от дефиницията на класа на планировчика.
- Функцията за избор на активност взема като основа индекс на начална точка и разделя алчното търсене на алчни подпроблеми.
Activity * Scheduler :: activity_select(int considered_index){this->considered_index = considered_index;int greedy_extent = this->considered_index + 1;… …
- С помощта на оператора за разделителна способност на обхвата (: :) се предоставя дефиницията на функцията.
- Разглежданият индекс е индексът, наречен по стойност. 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++;}… …
Обяснение на кода:
- Основната логика - алчната степен е ограничена до броя на дейностите.
- Началните часове на текущата дейност се проверяват като планируеми, преди разглежданата дейност (дадена от разглеждания индекс) да приключи.
- Докато това е възможно, се отпечатва незадължителен оператор за отстраняване на грешки.
- Преминаване към следващия индекс на масива от дейности
… if ( greedy_extent <= MAX_ACTIVITIES ){return activity_select(greedy_extent);}else{return NULL;}}
Обяснение на кода:
- Условните проверки дали всички дейности са били обхванати.
- Ако не, можете да рестартирате своя алчен с разглеждания индекс като текуща точка. Това е рекурсивна стъпка, която алчно разделя изявлението на проблема.
- Ако отговорът е да, той се връща към повикващия без възможност за разширяване на алчността.
int main(){Scheduler *activity_sched = new Scheduler();activity_sched->scheduled = activity_sched->activity_select(activity_sched->considered_index);return 0;}
Обяснение на кода:
- Основната функция, използвана за извикване на планировчика.
- Инстаниран е нов планировчик.
- Функцията за избор на активност, която връща указател на тип дейност, се връща към повикващия след приключване на алчното търсене.
Изход:
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 точки по-високо като неоптимално решение.
Примери за алчни алгоритми
Повечето мрежови алгоритми използват алчния подход. Ето списък с няколко примера за алчен алгоритъм:
- Алгоритъм на минималното обхващащо дърво на Prim
- Проблем с пътуващ продавач
- Графика - Оцветяване на картата
- Алгоритъм на минималното обхващащо дърво на Крускал
- Алгоритъм на минималното обхващащо дърво на Дейкстра
- Графика - Покритие на върха
- Проблем с раницата
- Проблем с планирането на работа
Резюме:
За да обобщим, статията дефинира алчната парадигма, показа как алчната оптимизация и рекурсия може да ви помогне да получите най-доброто решение до определен момент. Алчният алчен алгоритъм е широко използван за решаване на проблеми на много езици като алчен алгоритъм Python, C, C #, PHP, Java и др. Изборът на активност на примера на алчен алгоритъм е описан като стратегически проблем, който може да постигне максимална производителност, използвайки алчния Приближаване. В крайна сметка бяха обяснени недостатъците на използването на алчния подход.