|
Дискретный анализ и исследование операций, сер. 1, 1999, том 6, выпуск 4, страницы 104–120
(Mi da330)
|
|
|
|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Максимизация линейной целевой функции с помощью жадного алгоритма
В. В. Шенмайер Новосибирский государственный университет
Аннотация:
Рассматриваются задачи, обобщающие известную задачу о базе матроида максимального веса. Цель статьи состоит в выявлении классов задач, при решении которых с использованием жадных алгоритмов удается получать оптимальные решения при любой линейной целевой функции. Предложено обобщение аксиомы матроидов, являющееся достаточным и необходимым условием оптимальности жадного алгоритма в случае монотонных вниз систем целочисленных неотрицательных векторов. Расширена область действия критерия оптимальности, справедливого для случая систем множеств, не обладающих свойством монотонности вниз. Установлены новые критерии и достаточные условия оптимальности жадного алгоритма – как в общем, так и в частных случаях. Библиогр. 11.
Статья поступила: 01.04.1999
Образец цитирования:
В. В. Шенмайер, “Максимизация линейной целевой функции с помощью жадного алгоритма”, Дискретн. анализ и исслед. опер., сер. 1, 6:4 (1999), 104–120
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da330 https://www.mathnet.ru/rus/da/v6/s1/i4/p104
|
Статистика просмотров: |
Страница аннотации: | 416 | PDF полного текста: | 155 |
|