Алчни алгоритми се техника за решавање на проблеми, кај кои се прави избор кој изгледа најдобар во моментот на разгледување на само одреден дел од проблемот, со цел доаѓање до точно решение за целосниот проблем. Притоа, кај секој чекор од решавање на проблемот, се обидуваме да направиме избор кој е оптимален, и ќе ни дозволи да го разгледуваме остатокот од проблемот без потреба од враќање наназад и менување на одлуките.

Овие алгоритми се најчесто едноставни за пишување, но и лесни за анализа на нивната мемориска и временска сложеност. Главниот проблем кај истите е создавањето на алгоритам кој е точен, и функционира за разни податоци. Во ова и наредните предавања, ќе разгледаме разни проблеми, вклучувајќи и посложени алгоритми кои се користат при изнаоѓање на најкраток пат.

Да започнеме со едноставен пример. Нека имаме танкер со вкупно N литри гориво, и неколку коли со различна големина на нивниот резервоар. Прашањето кое сакаме да го одговориме е колку најмногу коли можеме да наполниме со гориво, така што резервоарот на секоја од тие коли ќе биде наполнет до крај (до врв).

Решението на оваа задача е едноставно: треба да ги подредиме колите според големината на нивниот резервоар (почнувајќи од онаа со најмал резервоар), и да ги полниме во истиот тој редослед - најпрвин онаа со најмал резервоар, па онаа со втор најмал резервоар, итн. Бидејќи прашањето кое сакаме да го одговориме е колку најмногу коли може да наполниме до врвот, овој алгоритам секогаш ќе работи прецизно. Притоа, ова претставува пример за алчен алгоритам, бидејќи во секој чекор од алгоритамот, го правиме изборот кој изгледа најдобар во тој момент (на почетокот, најдобар избор е да го наполниме резервоарот на првата кола со најмал резервоар; па понатаму, најдобар избор е да го наполниме резервоарот на втората кола со најмал резервоар, итн).

Доколку не ви е јасно зошто овој алгоритам е точен, замислете го обратното: дали има смисла да ставиме гориво во кола со поголем резервоар, кога можеме да ставиме гориво во кола со помал резервоар, а притоа секоја кола се брои идентично (т.е. прашањето во задачата е колку најмногу коли може да наполниме)? Едноставно, тоа нема никаква логика - во таков случај, само ќе потрошиме дополнително гориво за полнење на поголем резервоар, и ќе останеме со помалку гориво за полнење на останатите коли кои ни се на располагање.

Постојат повеќе проблеми кои се слични на претходниот, и кои се решаваат на истиот начин. На пример, користејќи ја истата идеја, можеме да пресметаме колку најмногу различни активности може да направи едно лице, ако тоа има ограничено време (на пример, 7 дена), и за секоја активност ни е познато времето кое е потребно за спроведување на истата (на пример, 1 ден за патување до Париз, 5 дена за изучување на програмски јазик, 4 дена за читање, 7 дена за искачување на највисокиот врв во Македонија, и 2 дена за гледање на серијалот Војна на ѕвездите). Во овој случај, ги подредуваме активностите по потребното време [1, 2, 4, 5, 7], и пресметуваме дека е можно да се спроведат дури 3 од тие активности за само 7 дена (1+2+4=7).

Враќање кусур

Еден од најчестите примери кој се споменува при дискутирањето на алчните алгоритми е проблемот за враќање на кусур. Нека имаме неограничен број на монети од 1, 2, 5 и 10 денари. Колку најмалку монети се потребни, за враќање на кусур од N денари? Да разгледаме неколку примери:

• 3 денари: 2 + 1, значи, потребни се 2 монети за кусур од 3 денари
• 8 денари: 5 + 2 + 1, значи потребни се 3 монети за кусур од 8 денари
• 17 денари: 10 + 5 + 2, значи потребни се 3 монети за кусур од 17 денари
• 19 денари: 10 + 5 + 2 + 2, значи потребни се 4 монети за кусур од 19 денари

Притоа, делува едноставно да смислиме алгоритам за овој проблем. Едноставно, можеме да ги подредиме монетите во редослед од најголема до најмала, и секогаш да ја земаме најголемата монета која е сеуште помала или еднаква на преостанатиот кусур. На пример, доколку треба да вратиме кусур од 17 денари, почнуваме од монетата од 10 денари. Таа е помала од 17, па ја враќаме и ни остануваат 7 денари (17-10) како кусур кој сеуште не сме го вратиле. Сега, 5 денари е најголемата монета која е помала од 7, па ја враќаме таа. На крај, останува 7-5=2, и имаме монета од точно тој износ (2 денари). Со три монети (една од 10 денари, една од 5 денари, и една од 2) сме успеале да вратиме кусур од 17 денари. Притоа, не постои начин да го вратиме овој кусур, од 17 денари, со помалку од три монети.

Ако се сеќавате, на почетокот од ова предавање, споменавме дека треба да се внимава при користењето на алчни алгоритми, и навистина да сме сигурни дека тие функционираат пред да ги искористиме при решавање на одреден проблем. Кај примерот со колите и полнењето на истите со гориво, беше очигледно дека алгоритамот е соодветен, и дека ќе функционира за разни вредности. Но, кај проблемот на враќање на кусур со најмал број на монети, потребно е да внимаваме на вредностите на монетите. За примерот со монети од 1, 2, 5 и 10 денари, каков што видовме погоре, алчниот алгоритам функционираше точно.

Но, што доколку имаме случај каде постојат и други монети. На пример, да замислиме дека имаме и монета од 7 денари, и дека треба да вратиме кусур од 14 денари. Во ваква ситуација, алгоритамот споменат погоре ќе искористи 3 монети (10 + 2 + 2) за враќање на кусур, но истиот можеме да го вратиме со само 2 монети (7 + 7). Затоа, запаметете, секогаш кога користиме алчен алгоритам за решавање на одреден проблем, треба да внимаваме на точноста на истиот. Ова можеме да го направиме преку разгледување на повеќе разни примери со цел да видиме како истиот функционира, проверка на алгоритамот на помали вредности, пишување на доказ дека истиот ќе работи, итн.

Во наредните предавања, ќе разгледаме два алгоритми кои секогаш точно го решаваат проблемот на враќање на кусур со најмал број на монети.

Во продолжение, прикажан е и друг пример каде алчен алгоритам (правењето на одлука без разгледување на следните чекори) функционира неточно. Во овој случај, разгледуваме како може да се дојде до максимална вкупна вредност, ако, при секој чекор, имаме избор од две вредности. Бидејќи 18 е поголемо од 5 (види слика подолу), алгоритамот ќе тргне по десната патека, иако максимален износ може да се постигне само доколку тргнеме по левата, и го земеме бројот 99.

Избор на активности

Последниот алгоритам кој ќе го разгледаме во ова предавање се користи за решавање на разни проблеми - избор на активности, планирање на извршувањето на процеси на компјутерски систем, итн. Накратко, ќе зборуваме за начин на планирање на активности (за кои знаеме кое е нивното време на почеток, и нивното време на завршување), со цел да исполниме најголем дел од нив.

На пример, нека ги имаме следните активности: гледање фудбалски натпревар од 20:00 – 22:00, филм од 22:15 – 23:00, и музичка емисија од 19:00 до 23:30. Колку најмногу активности можеме да изгледаме во целост? Притоа, забележете дека во овој пример разгледуваме само 3 активности, со цел полесно да го претставиме проблемот. Компјутерите, користејќи го алгоритамот кој ќе го презентираме, може да решаваат проблеми и со повеќе од милион активности.

Каков алчен алгоритам може да искористиме за решавање на овој проблем? Ќе ги разгледаме опциите кои изгледаат најлогични: да ги подредиме активностите според нивното време на почеток, да ги подредиме активностите според нивната должина, или да ги подредиме активностите според нивното време на завршување.

Алчниот алгоритам каде активностите се подредени според нивното време на почеток, и истите ги разгледуваме и земаме почнувајќи од онаа која започнува прва, нема да функционира точно. Тоа можеме да го забележиме и во пример активностите кои ги споменавме погоре: музичката емисија започнува прва, но доколку почнеме да ја гледаме истата, нема да можеме да изгледаме ништо друго. Доколку пак не ја гледаме истата, ќе можеме да ги одгледаме другите две активности.

Слично, нема да функционира ни алчниот алгоритам каде активностите ги разгледуваме почнувајќи од онаа со најкратка должина. Како пример, да ги разгледаме следните три активности: читање на книга од 20:00 - 21:00, разгледување на смешни инсерти на интернет од 20:50 -21:10, и следење на кошаркарски натпревар од 21:05 - 23:00. Тука, најкратката активност е разгледувањето на смешни инсерти со должина од само 20 минути, но доколку ја реализираме неа, нема да може да ги спроведеме другите две активности до крај. Бидејќи најдовме пример каде и овој алгоритам не функционира, можеме и него да го отфрлиме како неточен.

Интересно, овој проблем на избор на активности може да се реши користејќи го третиот алгоритам: разгледување на активности според нивното време на завршување. Истиот ќе функционира точно во сите ситуации. Притоа, активностите ги разгледуваме според нивното време на завршување бидејќи, во секој чекор, така ќе елиминираме најмалку од следните активности. Алгоритамот е едноставен: ги подредуваме активностите според нивното време на завршување, и истите ги разгледуваме една по една. Доколку одредена активност не е блокирана од некоја од претходните (кои сме решиле да ги реализираме во претходните чекори), ја земаме и реализираме и неа, и продолжуваме понатаму. Сложеноста на овој алгоритам ќе биде O(NlogN), бидејќи е потребно да ги подредиме елементите на почеток. Понатаму, само ги изминуваме истите со еден for циклус.

Следната програма го претставува овој проблем. Притоа, користиме пар од две вредности (почетното и крајното време) за претставување на активностите.

//koristi C++11 - http://mendo.mk/Lecture.do?id=26

#include <bits/stdc++.h>
using namespace std;

//funkcijata za podreduvanje
bool sort_by_end_time(pair<string, string> a, pair<string, string> b)
{
     return a.second < b.second;
}

//algoritamot za odbiranje na aktivnosti
void activitySelection(vector<pair<string, string> > &activities)
{
     if(activities.size() == 0)
     {
          return /* no activities */;
     }
     
     sort(activities.begin(), activities.end(), sort_by_end_time);
     
     
     //sekogash ja zemame prvata aktivnost po podreduvanjeto
     int lastSelected = 0;
     
     vector<int> takenActivities;
     takenActivities.push_back(lastSelected);
     
     for (int i = 1; i < activities.size(); i++)
     {
          //ako pochetnoto vreme na i-tata aktivnost
          //e pogolema ili ednakva na vremeto na zavrshuvanje
          //na poslednata odbrana aktivnost, ja zemame i nea
          if (activities[i].first >= activities[lastSelected].second)
          {
               takenActivities.push_back(i);
               lastSelected = i;
          }
     }
     
     //otpechati gi odbranite aktivnosti
     for(int t : takenActivities)
     {
          cout << activities[t].first << " " << activities[t].second << endl;
     }
}


int main()
{
     vector<pair<string, string> > activities;
     activities.push_back( { "20:00", "21:00" } );
     activities.push_back( { "20:50", "21:10" } );
     activities.push_back( { "21:05", "23:00" } );
     
     activitySelection(activities);
     return 0;
}

Во следните предавања, ќе разгледаме и други ситуации каде можеме да користиме алчни алгоритми, но и ситуации каде не можеме да користиме. Засега, важно е да се запамети дека треба многу да внимаваме при реализацијата на истите; и да провериме, на разни податоци, дали алгоритамот кој сме го смислиле и создале навистина функционира во сите ситуации. Како пример, го разгледавме проблемот на враќање на кусур, каде алчните алгоритми не функционираат секогаш точно.

Дозвола за користење: CC BY-NC 2.5 ©