У овом упутству ћете научити шта је похлепни алгоритам. Такође ћете наћи пример похлепног приступа.
Похлепни алгоритам је приступ решавању проблема избором најбоље опције која је тренутно доступна, без бриге о будућем резултату који би донео. Другим речима, најбољи локални избори имају за циљ постизање најбољих глобалних резултата.
Овај алгоритам можда није најбоља опција за све проблеме. У неким случајевима може произвести погрешне резултате.
Овај алгоритам се никада не враћа уназад на донету одлуку. Овај алгоритам ради у приступу од врха према доле.
Главна предност овог алгоритма је:
- Алгоритам је лакше описати .
- Овај алгоритам може да ради боље од осталих алгоритама (али не у свим случајевима).
Изводљиво решење
Изводљиво решење је оно које пружа оптимално решење проблема.
Похлепни алгоритам
- За почетак је скуп решења (који садржи одговоре) празан.
- У сваком кораку ставка се додаје у скуп решења.
- Ако је скуп решења изводљив, задржава се тренутна ставка.
- Иначе, ставка се одбацује и никада више не разматра.
Пример - Похлепни приступ
Проблем: Морате да промените износ користећи најмањи могући број кованица. Износ: $ 28 Доступни кованице: Кованица од 5 долара Кованица од 2 долара Кованица од 1 долара
Решење:
- Креирајте празан сет-решења = ().
- кованице = (5, 2, 1)
- сума = 0
- Док је збир = 28, урадите следеће.
- Изаберите новчић Ц од кованица тако да је збир + Ц <28.
- Ако је Ц + сума> 28, не враћа решење.
- Иначе, збир = збир + Ц.
- Додајте Ц у скуп решења.
До првих 5 понављања, сет решења садржи 5 кованица од 5 долара. После тога добијамо новчић од 1 долара и коначно 1 новчић од 1 долара.
Похлепни алгоритам
- Сортирање избора
- Кнапсацк Проблем
- Минимално дрвеће у распону
- Проблем најкраће путање са једним извором
- Проблем распоређивања послова
- Примов минимални алгоритам дрвећа у распону
- Крускалов алгоритам минималног распона дрвећа
- Дијкстрин алгоритам минималног распона стабла
- Хуффман Цодинг
- Форд-Фулкерсон алгоритам
