Датахакер
Какой алгоритм использует стратегию жадного выбора?
на скрине с лекции задача 12, там про монеты и вот такой разбор.
Компьютеры и связь
Юридическая консультация
Семья и дом
Еда и кулинария
Города и страны, туризм
Датахакер
на скрине с лекции задача 12, там про монеты и вот такой разбор.
v4-flash
Жадная стратегия, это когда алгоритм на каждом шаге выбирает вариант, который выглядит лучшим прямо сейчас, не пересматривая выбор позже. Кроме дейкстры сюда относятся алгоритмы Прима и Крускала для построения минимального остовного дерева, оба на каждом шаге берут самое дешёвое доступное ребро. Ещё пример: классическая задача о размене монет, где на каждом шаге берётся самый крупный подходящий номинал, но здесь есть подвох, важный для экзамена, жадность работает только для удобных систем номиналов, для произвольных наборов монет она может дать неверный ответ, и это стоит упомянуть отдельно, чтобы показать понимание ограничений метода, а не просто перечислить названия.
Датахакер
у меня в билете как раз крускал попался, спас что за неделю до этого лабу по нему делал, повезло
4o-mini
Классические примеры: алгоритм Дейкстры, построение минимального остовного дерева (Прима и Крускала), задача о размене монет с удобными номиналами, жадная упаковка рюкзака по частям.
Пока нет премиум-вопросов в подборке
Не нашли то, что искали?
Задайте свой вопрос
Лучший ответ
4.1 Fast
4.1 Fast
Какой алгоритм использует стратегию жадного выбора?
Разница между первыми примерами и последним важна для экзамена: жадный алгоритм даёт верный ответ не в любой задаче, где напрашивается жадное решение, а только там, где доказано, что локально лучший выбор на каждом шаге ведёт к глобально лучшему результату. Для дейкстры, прима и крускала это доказано формально, поэтому их жадность работает. Для рюкзака с целыми предметами это не так: набор из самых дорогих вещей по одной не всегда даёт максимальную суммарную ценность при ограничении по весу, там нужен другой подход, чаще всего динамическое программирование.