Вступ до жадного алгоритму
Стратегія, що використовується для вирішення проблем. Жадібний алгоритм розглядається як один із підходів, що використовуються для вирішення проблем. Це єретик, що вирішує проблеми, іде на вибір, який здається найкращим на той момент. Цей підхід найкраще використовувати для вирішення проблем оптимізації. Проблеми з оптимізацією можна визначити як проблеми, які вимагають мінімальних або максимальних результатів. Жадний алгоритм - це найпростіший і найпростіший підхід, який можна використовувати для досягнення оптимального рішення.
Що таке жадібний алгоритм?
Жадібний алгоритм - це алгоритмічна стратегія, яка використовується для найкращого вибору на дуже малому етапі, а в кінцевому підсумку виходить глобально оптимальне рішення. Цей алгоритм вибирає найкраще можливе рішення на той момент, не зважаючи на будь-які наслідки. Жадний метод говорить, що проблему слід вирішувати на етапах, коли кожен вхід розглядається з огляду на те, що цей вклад здійсненний. Оскільки цей підхід орієнтований лише на негайний результат без огляду на більшу картину, вважається жадібним.
Визначення основної концепції
До цього часу ми знаємо, що таке жадібний алгоритм і чому його так називають. Наведені нижче покажчики дозволять вам краще зрозуміти жадібний алгоритм. На сьогоднішній день було дуже зрозуміло, що жадібний алгоритм працює лише тоді, коли є проблема; тим не менш, такий підхід застосовується лише в тому випадку, якщо ми маємо умову або обмеження у цій проблемі.
Типи проблем
- Проблема мінімізації: Вирішити проблему легко, враховуючи, що всі умови виконані. Однак, коли ця проблема вимагає мінімального результату, вона називається проблемою мінімізації.
- Проблема максимізації: Проблема, яка вимагає максимального результату, відома як проблема максимізації.
- Проблема оптимізації: Проблема називається проблемою оптимізації, коли вона вимагає або мінімальних, або максимальних результатів.
Типи рішень
- Можливе рішення: Тепер, коли виникає проблема, ми маємо багато правдоподібних рішень цієї проблеми. Однак, беручи до уваги умову, поставлену в цій проблемі, ми обираємо рішення, які відповідають даній умові. Такі рішення, які допомагають нам отримати результати, що відповідають заданій умові, називаються можливим рішенням .
- Оптимальне рішення: рішення називається оптимальним, коли воно вже можливо і досягає мети проблеми; найкращий результат. Ця мета може бути як мінімальним, так і максимальним результатом. Слід зазначити, що будь-яка проблема матиме лише одне оптимальне рішення.
Наступний приклад змусить вас легко зрозуміти жадібний метод. Скажімо, хочеться придбати найкращий автомобіль, доступний на ринку. Один із методів вибору цього автомобіля - це аналіз усіх автомобілів на ринку. Тепер, це забирає багато часу, щоб зробити його легким, вибираючи автомобіль із тих конкретних марок, в які вони зацікавлені інвестувати. Класифікуючи це далі, можна знову вибрати потрібні моделі, дивлячись на його особливості. Тому підхід, застосований тут, жадібний, оскільки це рішення було оптимальним рішенням для вас, враховуючи, що всі фактори були сприятливими для вас.
Основні компоненти жадібного алгоритму
Тепер, коли ми краще розуміємо цей механізм, давайте вивчимо основні компоненти жадібного алгоритму, який відрізняє його від інших процесів:
- Набір кандидатів: Відповідь створюється з цього набору.
- Функція відбору: вона вибирає найкращого кандидата, який буде включений у рішення.
- Функція техніко-економічного обґрунтування: Цей розділ розраховує, чи можна використовувати кандидата для участі у вирішенні.
- Об'єктивна функція: вона присвоює значення повному чи частковому рішенню.
- Функція рішення: Це використовується, щоб вказати, чи було виконано належне рішення.
Де найкраще працює жадібний алгоритм?
Жадібний алгоритм може бути застосований до наведених нижче проблем.
- Жадний підхід може бути використаний для пошуку графіка мінімального діапазону дерева, використовуючи алгоритм Прима або Крускала
- Пошук найкоротшого шляху між двома вершинами - ще одна проблема, яку можна вирішити за допомогою жадібного алгоритму. Застосування алгоритму Дейкстри разом із жадібним алгоритмом дасть вам оптимальне рішення.
- Хаффман Кодування
Переваги
Найбільша перевага алгоритму «Жадібний» перед іншими полягає в тому, що його легко здійснити і дуже ефективно в більшості випадків.
Недоліки
Жадібний алгоритм в основному будує частину рішення частиною і вибираючи наступну частину таким чином, щоб вона негайно дала найкраще рішення цієї проблеми. Як наслідок, не виникає ніякої уваги чи турботи щодо наслідків прийнятого рішення. Ніколи не переглядаючи зроблений раніше вибір, жадібний алгоритм не вдається створити оптимальне рішення, хоча він дає майже оптимальне рішення . Проблема "Рюкзак" та "Продавець продавця подорожей" - приклади проблем, коли жадібний алгоритм не вдається створити оптимальне рішення.
- Проблема з рюкзаком : Найбільш відома під назвою проблема рюкзака - це повсякденна проблема, з якою стикаються багато людей. Скажімо, у нас є набір предметів, і кожен має різну вагу та вартість (прибуток), яку потрібно заповнити в контейнер, або слід зібрати таким чином, щоб загальна вага була меншою або дорівнює вазі контейнера, тоді як загальний прибуток максимізований .
Висновок
Жадібний алгоритм найкраще застосувати, коли потрібне рішення в режимі реального часу, а приблизні відповіді - «досить добре». Зрозуміло, що жадібний алгоритм мінімізує час, переконуючись, що виробляється оптимальне рішення, отже, його більше застосувати в ситуації, коли потрібно менше часу. Ознайомившись із цією статтею, можна мати гарне уявлення про жадібні алгоритми. Крім того, у цій публікації пояснюється, чому вона вважається найкращою структурою, яка відповідає на майже всі проблеми програмування, а також допомагає вам вирішити найбільш оптимальне рішення в даний момент часу.
Однак, з грубого боку, для застосування теорії жадібного алгоритму потрібно більше працювати, щоб знати правильні проблеми. Хоча це наукова концепція, яка має логіку, але вона також має суть творчості.
Рекомендовані статті
Це було керівництвом щодо Що таке жадібний алгоритм. Тут ми обговорили основні поняття, компоненти, перевагу та недолік жадного алгоритму. Ви також можете ознайомитися з іншими запропонованими нами статтями, щоб дізнатися більше -
- Алгоритм програмування
- Що таке Perl?
- Вступ до алгоритму
- Що таке Agile Sprint?