В този урок ще научите какво е алчен алгоритъм. Също така ще намерите пример за алчен подход.
Алчният алгоритъм е подход за решаване на проблем чрез избор на най-добрата опция, налична в момента, без да се притеснявате за бъдещия резултат, който би донесъл. С други думи, най-добрият избор на местно ниво цели постигането на най-добри глобални резултати.
Този алгоритъм може да не е най-добрият вариант за всички проблеми. В някои случаи може да доведе до грешни резултати.
Този алгоритъм никога не се връща, за да обърне взетото решение. Този алгоритъм работи в подход отгоре надолу.
Основното предимство на този алгоритъм е:
- Алгоритъмът е по-лесен за описване .
- Този алгоритъм може да работи по - добре от други алгоритми (но не във всички случаи).
Приложимо решение
Възможното решение е това, което осигурява оптималното решение на проблема.
Алчен алгоритъм
- Като начало наборът от решения (съдържащ отговори) е празен.
- На всяка стъпка елемент се добавя към набора от решения.
- Ако наборът от решения е осъществим, текущият елемент се запазва.
- В противен случай елементът се отхвърля и никога повече не се разглежда.
Пример - алчен подход
Проблем: Трябва да направите промяна на сума, като използвате възможно най-малкия брой монети. Сума: $ 28 Налични монети: $ 5 монета $ 2 монета $ 1 монета
Решение:
- Създайте празно решение-set = ().
- монети = (5, 2, 1)
- сума = 0
- Докато сумата ≠ 28, направете следното.
- Изберете монета C от монети, така че сума + C <28.
- Ако C + sum> 28, не връщайте решение.
- В противен случай, сума = сума + C.
- Добавете C към набора от решения.
До първите 5 повторения наборът от решения съдържа 5 монети от 5 долара. След това получаваме монета от 1 $ 2 и накрая 1 $ 1 монета.
Алчен алгоритъм приложения
- Сортиране на избора
- Проблем с раницата
- Минимално обхващащо дърво
- Проблем с най-краткия път с един източник
- Проблем с планирането на работа
- Алгоритъм на минималното обхващащо дърво на Prim
- Алгоритъм на минималното обхващащо дърво на Крускал
- Алгоритъм на минималното обхващащо дърво на Дейкстра
- Кодиране на Хъфман
- Алгоритъм на Форд-Фулкърсън
