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

Abstract

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