ЖАДНЫЙ АЛГОРИТМ И МАТРОИДЫ (2023)

Рассмотрены некоторые задачи дискретной оптимизации, решаемые жадным алгоритмом, который на каждом шаге делает локально оптимальный выбор. Описаны различные примеры использования жадного алгоритма. Гарантом получения правильного ответа жадным алгоритмом является матроидная структура решаемых задач. Приведены сведения из теории матроидов, а также примеры прикладных задач, сформулированных на матроидах, и алгоритмы их решения.

Тип: Статья
Автор (ы): Бардушкина Ирина Вячеславовна, Терещенко Анатолий Михайлович, Ревякин Александр Михайлович
Ключевые фразы: ЖАДНЫЙ АЛГОРИТМ, ОПТИМИЗАЦИЯ НА ГРАФАХ И СЕТЯХ, ОСТОВ, МАТРОИДЫ, ГРИДОИДЫ, ЗАДАЧИ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ

Идентификаторы и классификаторы

УДК
519.11. Теория перечисления
eLIBRARY ID
52663764
Текстовый фрагмент статьи