Preview

Цифровая трансформация

Расширенный поиск

Алгоритм нахождения множества Парето на конечном наборе начальных данных

Полный текст:

Аннотация

Предлагаемый в работе метод нахождения множества Парето Т на конечном наборе начальных данных N относится к двухэтапным алгоритмам решения ряда комбинаторных задач. На первом этапе без применения переборных операций осуществляется нахождение элементов из множества начальных данных, которые по своей внутренней структуре не могут войти в оптимальное подмножество Т. Математическая модель задачи представляет собой двухкритериальные подпространства, для каждого из которых построены паретовские слои на множестве N. Сформулированы достаточные условия существования подмножества, исключаемого из рассмотрения вследствие его удаления из множества Т. Достигаемое уменьшение множества начальных данных, из которых формируется оптимальное множество Т, ведет к уменьшению времени, необходимого для решения данной комбинаторной задачи. На втором этапе на основе алгоритма частичного перебора элементов отдельных паретовских слоев и с использованием структур данных, полученных на первом этапе, выполняется поиск всех недоминируемых элементов на множестве N. Разработанный алгоритм позволяет рассматривать оба этапа нахождения множества Парето как единый процесс, делая его эффективнее за счет существенного уменьшения времени решения поставленной задачи.

Об авторах

С В. Чебаков
Объединенный институт проблем информатики Национальной академии наук Беларуси
Беларусь
к. ф.-м. н., старший научный сотрудник


Л. В. Серебряная
Белорусский государственный университет информатики и радиоэлектроники
Беларусь
к. т. н., доцент кафедры программного обеспечения информационных технологий


Список литературы

1. Дубов, Ю. А. Многокритериальные модели формирования и выбора вариантов систем / Ю. А. Дубов, С. И. Травкин, В. Н. Якимец. – М.: Наука, 1986. – 296 с.

2. Посыпкин, М. А. Комбинированный параллельный алгоритм решения задачи о ранце / М. А. Посыпкин // Труды четвертой международной конференции «Параллельные вычисления и задачи управления» (Москва, 27–29 октября 2008 г.). – С. 177–189.

3. Чебаков, С. В. Алгоритм решения заданных комбинаторных задач на основе модели многокритериальной оптимизации / С. В. Чебаков, Л. В. Серебряная // Доклады БГУИР. – 2015. – № 4 (90). – С 16–22.

4. Kung, H. F. On Finding the Maxima of a set of Vectors / H. F. Kung, F. P. Preparata // Journal of the Association for Computing Machinery. – 1975. – Vol. 22. – P. 469–476.


Для цитирования:


Чебаков С.В., Серебряная Л.В. Алгоритм нахождения множества Парето на конечном наборе начальных данных. Информатизация образования . 2017;(1s):84-94.

For citation:


Chebakov S.V., Serebryanaya L.V. Algorithm of finding a set of Pareto on a final set of initial data. Informatization of Education . 2017;(1s):84-94. (In Russ.)

Просмотров: 239


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2522-9613 (Print)
ISSN 2524-2822 (Online)