Въведение в алчния алгоритъм
Стратегия, използвана за решаване на проблеми. Алчният алгоритъм се счита за един от подходите, използвани за решаване на проблеми. Този еретик за решаване на проблеми върви с вземане на избор, който изглежда най-добър в този момент. Този подход се използва най-добре за решаване на проблеми с оптимизацията. Проблемите с оптимизацията могат да бъдат определени като проблеми, които изискват минимални или максимални резултати. Алчният алгоритъм е най-простият и лесен подход, който може да се използва за постигане на оптимално решение.
Какво е алчен алгоритъм?
Алчен алгоритъм е алгоритмична стратегия, използвана за да се направи най-добрият незадължителен избор на много малък етап, като в крайна сметка извежда глобално оптимално решение. Този алгоритъм избира най-доброто възможно решение в този момент, без оглед на каквито и да е последствия. Алчният метод казва, че проблемът трябва да се решава на етапи, при които всеки един вход се счита, като се има предвид, че този вход е осъществим. Тъй като този подход се фокусира само върху незабавен резултат, без да се взема предвид по-голямата картина, се счита за алчен.
Определяне на основната концепция
До сега знаем какво е алчен алгоритъм и защо е наречен така. По-долу показалците ще ви накарат да разберете алчния алгоритъм по-добре. Досега стана ясно, че алчният алгоритъм работи само когато има проблем; въпреки това, този подход е приложим само ако имаме условие или ограничение за този проблем.
Видове проблеми
- Проблем с минимизацията: Решението на проблем е лесно, като се имат предвид всички условия. Когато обаче този проблем изисква минимален резултат, той се нарича проблем за минимизиране.
- Проблем с максимизацията: Проблемът, който изисква максимален резултат, е известен като проблем с максимизацията.
- Проблем с оптимизацията: Проблемът се нарича проблем с оптимизацията, когато изисква минимални или максимални резултати.
Видове решения
- Възможно решение: Сега, когато възникне проблем, ние имаме много правдоподобни решения на този проблем. И все пак, вземайки предвид условието, поставено по този проблем, ние избираме решения, които отговарят на даденото условие. Такива решения, които ни помагат да постигнем резултати, отговарящи на даденото условие, се наричат осъществимо решение .
- Оптимално решение: Решението се нарича оптимално, когато то вече е осъществимо и постига целта на проблема; най-добрият резултат. Тази цел може да бъде или минимален, или максимален резултат. Тук трябва да се отбележи, че всеки проблем ще има само едно оптимално решение.
Следващият пример ще ви накара да разберете лесно алчния метод. Кажете, човек иска да купи най-добрата кола на разположение на пазара. Един от методите за избор на тази кола е чрез анализ на всички автомобили на пазара. Сега, като това отнема много време, за да улесните избора на автомобил от онези конкретни марки, в които се интересуват да инвестират. Категоризирайки това допълнително, отново ще изберете желаните модели, като разгледате характеристиките му. Следователно подходът, използван тук, е алчен, тъй като това решение е било оптималното решение за вас, като се има предвид, че всички фактори са били благоприятни за вас.
Основни компоненти на алчния алгоритъм
Сега, когато имаме по-добро разбиране на този механизъм, нека проучим основните компоненти на алчния алгоритъм, който го отличава от другите процеси:
- Набор от кандидати: От този набор се създава отговор.
- Функция за избор: Избира най-добрия кандидат, който да бъде включен в решението.
- Функция за осъществимост: Този раздел изчислява дали кандидат може да бъде използван за принос към решението.
- Обективна функция: Присвоява стойност на цялостно или частично решение.
- Функция за решение: Използва се за индикация дали е изпълнено правилното решение.
Къде най-добре работи алчният алгоритъм?
Алчен алгоритъм може да се приложи към споменатите по-долу проблеми.
- Алчният подход може да се използва за намиране на графика на минимално обхващащо дърво с помощта на алгоритъма на Prim или Kruskal
- Намирането на най-краткия път между два върха е още един проблем, който може да бъде решен с алчен алгоритъм. Прилагането на алгоритъма на Dijkstra заедно с алчния алгоритъм ще ви даде оптимално решение.
- Хюфман Кодиране
Предимства
Най-голямото предимство, което алгоритъмът на Алчния има пред останалите, е, че той е лесен за изпълнение и много ефективен в повечето случаи.
Недостатъци
Алчният алгоритъм основно изгражда решение част по част и избира следващата част по такъв начин, че да даде най-доброто решение на настоящия проблем в момента. В резултат на това няма никакво внимание или притеснение от последиците от взетото настоящо решение. Никога не преосмисля предварително направените решения, алчният алгоритъм не успява да произведе оптимално решение, въпреки че дава почти оптимално решение . Проблемът с раницата и проблемът с продавачите на пътувания са примери за проблеми, при които алчният алгоритъм не успява да създаде оптимално решение.
- Проблем с раницата : Най-често известният с името проблем с раницата е ежедневен проблем, с който се сблъскват много хора. Кажете, ние имаме набор от артикули и всеки има различна тежест и стойност (печалба), запълнена в контейнер или трябва да се събира по такъв начин, че общото тегло да е по-малко или равно на това на контейнера, докато общата печалба е максимална,
заключение
Алчният алгоритъм е най-подходящ, когато човек се нуждае от решение в реално време и приблизителните отговори са „достатъчно добри“. Ясно е, че алчният алгоритъм минимизира времето, като същевременно се гарантира, че се произвежда оптимално решение, следователно е по-приложимо да се използва в ситуация, в която се изисква по-малко време. След като прочетете тази статия, човек може да има добра представа за алчните алгоритми. В допълнение, тази публикация обяснява защо се счита за най-добрата рамка, която отговаря на почти всички предизвикателства пред програмирането, заедно с това да ви помогне да вземете най-оптималното решение в даден момент от време.
От груба страна обаче, за прилагането на теорията на алчния алгоритъм човек трябва да работи по-усилено, за да знае правилните проблеми. Въпреки че е научна концепция, която има логика, тя също има същност на креативността.
Препоръчителни статии
Това е ръководство за това какво е алчен алгоритъм. Тук обсъдихме основната концепция, компоненти, предимство и недостатък на алчния алгоритъм. Можете да разгледате и другите ни предложени статии, за да научите повече -
- Алгоритъм в програмирането
- Какво е Perl?
- Въведение в алгоритъма
- Какво е Agile Sprint?