Проблема вибору діяльності Жадібний Алго-1 - GeeksforGeeks

Ми використовуємо файли cookie, щоб забезпечити найкращий досвід перегляду веб-сайту. Використовуючи наш веб-сайт, ви підтверджуєте, що прочитали та розумієте нашу Політику використання файлів cookie та Політику конфіденційності

проблема

Жадібний - це алгоритмічна парадигма, яка формує рішення по частинах, завжди вибираючи наступний фрагмент, який пропонує найбільш очевидну та негайну користь. Жадібні алгоритми використовуються для задач оптимізації. Проблему оптимізації можна вирішити за допомогою Greedy, якщо проблема має таку властивість: На кожному кроці ми можемо зробити вибір, який найкраще виглядає на даний момент, і отримати оптимальне рішення повної проблеми.
Якщо Жадібний алгоритм може вирішити проблему, тоді він, як правило, стає найкращим методом для вирішення цієї проблеми, оскільки Жадібні алгоритми загалом ефективніші за інші методи, такі як динамічне програмування. Але жадібні алгоритми не завжди можна застосовувати. Наприклад, проблему дробового рюкзака (див. Це) можна вирішити за допомогою Жадібного, але 0-1 рюкзака не можна вирішити за допомогою Жадібного.

Нижче наведено деякі стандартні алгоритми, які є Жадібними алгоритмами.
1) Дерево мінімального розмаху Крускала (MST): В алгоритмі Крускала ми створюємо MST, підбираючи краї по черзі. Greedy Choice - вибрати найменший край ваги, який не спричиняє циклу в побудованому до цього часу MST.
2) Мінімальне дерево розширення Prim: В алгоритмі Prim ми також створюємо MST, підбираючи ребра по одному. Ми підтримуємо два набори: набір вершин, вже включених до MST, і набір вершин, які ще не включені. Greedy Choice - вибрати найменший ваговий край, який з’єднує два набори.