Алчни алгоритми, обяснени с примери

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

Може да сте чували за много техники за алгоритмичен дизайн, докато преглеждате някои от статиите тук. Някои от тях са:

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

Представете си, че отивате на туризъм и целта ви е да достигнете възможно най-високия връх. Вече имате картата преди да започнете, но има хиляди възможни пътища, показани на картата. Прекалено сте мързеливи и просто нямате време да оцените всеки един от тях. Прецакай картата! Започнахте да се разхождате с проста стратегия - бъдете алчни и недалновидни. Просто поемете по пътеки, които се наклоняват най-много нагоре. Това изглежда като добра стратегия за туризъм. Но винаги ли е най-доброто?

След като пътуването приключи и цялото ви тяло е болно и уморено, за първи път погледнете туристическата карта. Боже мой! Има кална река, която трябваше да прекося, вместо да продължавам да вървя нагоре. Това означава, че алчният алгоритъм избира най-добрия незабавен избор и никога не преразглежда избора си. По отношение на оптимизирането на решение, това просто означава, че алчното решение ще се опита да намери локални оптимални решения - които могат да бъдат много - и може да пропусне глобално оптимално решение.

Официално определение

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

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

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

Проблем с интервалното планиране

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

  • Имате набор от N графика на лекции за един ден в университет. Графикът за конкретна лекция е във формата (s time, f time), където s time представлява времето за начало на тази лекция и по същия начин f time представлява времето за завършване. Като се има предвид списък с N графици за лекции, трябва да изберем максимален набор от лекции, които да се провеждат през деня, така че   нито една от лекциите да не се припокрива една с друга, т.е. ако лекция Li и Lj са включени в нашата селекция, тогава началното време на j > = крайно време на i или обратно .
  • Вашият приятел работи като съветник в лагера и отговаря за организирането на дейности за набор от къмпингуващи. Един от плановете му е следното упражнение за мини триатлон: всеки състезател трябва да плува 20 обиколки на басейн, след това да кара велосипед на 10 мили, след това да пробяга 3 мили.
  • Планът е състезателите да се изпратят разпределени, чрез следното правило: състезателите трябва да използват пула един по един. С други думи, първо един състезател плува 20-те обиколки, излиза и започва да кара колело.
  • Щом този първи човек излезе от басейна, втори състезател започва да плува 20-те обиколки; щом излезе или започне да кара колело, трети състезател започва да плува и т.н.
  • Всеки състезател има прогнозирано време за плуване, прогнозирано време за колоездене и прогнозирано време за бягане. Вашият приятел иска да определи график за триатлон: ред, в който да подреди стартовете на състезателите.
  • Да кажем, че времето за завършване на даден график е най-ранното време, в което всички състезатели ще бъдат завършени с всичките три крака на триатлона, като се приеме, че прогнозите за времето са точни. Каква е най-добрата поръчка за изпращане на хора, ако човек иска цялото състезание да приключи възможно най-скоро? По-точно, дайте ефективен алгоритъм, който създава график, чието време за завършване е възможно най-малко

Проблемът с планирането на лекциите

Нека разгледаме различните подходи за решаване на този проблем.

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

Първо най-ранното начално време

Първо най-малкият интервал,  т.е. в крайна сметка избирате лекциите по реда на общия им интервал, който не е нищо друго освен тяхното   finish time - start time. Отново това решение не е правилно. Погледнете следния случай.

Първо най-кратък интервал

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

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

Най-малко конфликтният интервал първо

Диаграмата ни показва, че най-малко конфликтният интервал е този в средата само с 2 конфликта. След това можем да изберем само двата интервала в самите краища с конфликти по 3 всеки. Но оптималното решение е да изберете 4-те интервала на най-високото ниво.

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

function interval_scheduling_problem(requests) schedule \gets \{\} while requests is not yet empty choose a request i_r \in requests that has the lowest finishing time schedule \gets schedule \cup \{i_r\} delete all requests in requests that are not compatible with i_r end return schedule end 

Кога използваме алчни алгоритми

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

Алчните алгоритми ни помагат да решаваме много различни видове проблеми, като:

Проблем с най-краткия път:

Проблем с минималното обхващащо дърво в графика

Проблем с кодирането на Huffman

Проблем с K центрове