Preview

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

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

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

Аннотация

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

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


Чебаков С.В., Серебряная Л.В. Алгоритм нахождения множества Парето на конечном наборе начальных данных. Информатизация образования. 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.)

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


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


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