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