<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Publishing DTD v1.3 20210610//EN" "JATS-journalpublishing1-3.dtd">
<article article-type="research-article" dtd-version="1.3" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xml:lang="ru"><front><journal-meta><journal-id journal-id-type="publisher-id">dt</journal-id><journal-title-group><journal-title xml:lang="ru">Цифровая трансформация</journal-title><trans-title-group xml:lang="en"><trans-title>Digital Transformation</trans-title></trans-title-group></journal-title-group><issn pub-type="ppub">2522-9613</issn><issn pub-type="epub">2524-2822</issn><publisher><publisher-name>Educational Establishment “Belarusian State University of Informatics and Radioelectronics”</publisher-name></publisher></journal-meta><article-meta><article-id custom-type="elpub" pub-id-type="custom">dt-10</article-id><article-categories><subj-group subj-group-type="heading"><subject>Research Article</subject></subj-group><subj-group subj-group-type="section-heading" xml:lang="ru"><subject>НАУЧНЫЕ ПУБЛИКАЦИИ</subject></subj-group><subj-group subj-group-type="section-heading" xml:lang="en"><subject>SCIENTIFIC PUBLICATION</subject></subj-group></article-categories><title-group><article-title>Алгоритм нахождения множества Парето на конечном наборе начальных данных</article-title><trans-title-group xml:lang="en"><trans-title>Algorithm of finding a set of Pareto on a final set of initial data</trans-title></trans-title-group></title-group><contrib-group><contrib contrib-type="author" corresp="yes"><name-alternatives><name name-style="eastern" xml:lang="ru"><surname>Чебаков</surname><given-names>С В.</given-names></name><name name-style="western" xml:lang="en"><surname>Chebakov</surname><given-names>S. V.</given-names></name></name-alternatives><bio xml:lang="ru"><p>к. ф.-м. н., старший научный сотрудник</p></bio><xref ref-type="aff" rid="aff-1"/></contrib><contrib contrib-type="author" corresp="yes"><name-alternatives><name name-style="eastern" xml:lang="ru"><surname>Серебряная</surname><given-names>Л. В.</given-names></name><name name-style="western" xml:lang="en"><surname>Serebryanaya</surname><given-names>L. V.</given-names></name></name-alternatives><bio xml:lang="ru"><p>к. т. н., доцент кафедры программного обеспечения информационных технологий</p></bio><xref ref-type="aff" rid="aff-2"/></contrib></contrib-group><aff xml:lang="ru" id="aff-1"><institution>Объединенный институт проблем информатики Национальной академии наук Беларуси</institution><country>Belarus</country></aff><aff xml:lang="ru" id="aff-2"><institution>Белорусский государственный университет информатики и радиоэлектроники</institution><country>Belarus</country></aff><pub-date pub-type="collection"><year>2017</year></pub-date><pub-date pub-type="epub"><day>30</day><month>12</month><year>2017</year></pub-date><volume>0</volume><issue>1s</issue><fpage>84</fpage><lpage>94</lpage><permissions><copyright-statement>Copyright &amp;#x00A9; Чебаков С.В., Серебряная Л.В., 2017</copyright-statement><copyright-year>2017</copyright-year><copyright-holder xml:lang="ru">Чебаков С.В., Серебряная Л.В.</copyright-holder><copyright-holder xml:lang="en">Chebakov S.V., Serebryanaya L.V.</copyright-holder><license xml:lang="ru" license-type="creative-commons-attribution" xlink:href="https://creativecommons.org/licenses/by/4.0/" xlink:type="simple"><license-p>Данная работа распространяется под лицензией Creative Commons Attribution 4.0.</license-p></license><license xml:lang="en" license-type="creative-commons-attribution" xlink:href="https://creativecommons.org/licenses/by/4.0/" xlink:type="simple"><license-p>This work is licensed under a Creative Commons Attribution 4.0 License.</license-p></license></permissions><self-uri xlink:href="https://dt.bsuir.by/jour/article/view/10">https://dt.bsuir.by/jour/article/view/10</self-uri><abstract><p>Предлагаемый в работе метод нахождения множества Парето Т на конечном наборе начальных данных N относится к двухэтапным алгоритмам решения ряда комбинаторных задач. На первом этапе без применения переборных операций осуществляется нахождение элементов из множества начальных данных, которые по своей внутренней структуре не могут войти в оптимальное подмножество Т. Математическая модель задачи представляет собой двухкритериальные подпространства, для каждого из которых построены паретовские слои на множестве N. Сформулированы достаточные условия существования подмножества, исключаемого из рассмотрения вследствие его удаления из множества Т. Достигаемое уменьшение множества начальных данных, из которых формируется оптимальное множество Т, ведет к уменьшению времени, необходимого для решения данной комбинаторной задачи. На втором этапе на основе алгоритма частичного перебора элементов отдельных паретовских слоев и с использованием структур данных, полученных на первом этапе, выполняется поиск всех недоминируемых элементов на множестве N. Разработанный алгоритм позволяет рассматривать оба этапа нахождения множества Парето как единый процесс, делая его эффективнее за счет существенного уменьшения времени решения поставленной задачи.</p></abstract><trans-abstract xml:lang="en"><p>A two-stage algorithm for solving the optimization task for finding the Pareto set on a given finite set of initial data N is proposed. A method is developed for finding a subset of dominated elements of the initial set N by constructing the Pareto layers on two-criterial subspaces that does not use backtracking algorithms. An iterative algorithm for constructing the Pareto set is proposed.</p></trans-abstract></article-meta></front><back><ref-list><title>References</title><ref id="cit1"><label>1</label><citation-alternatives><mixed-citation xml:lang="ru">Дубов, Ю. А. Многокритериальные модели формирования и выбора вариантов систем / Ю. А. Дубов, С. И. Травкин, В. Н. Якимец. – М.: Наука, 1986. – 296 с.</mixed-citation><mixed-citation xml:lang="en">Дубов, Ю. А. Многокритериальные модели формирования и выбора вариантов систем / Ю. А. Дубов, С. И. Травкин, В. Н. Якимец. – М.: Наука, 1986. – 296 с.</mixed-citation></citation-alternatives></ref><ref id="cit2"><label>2</label><citation-alternatives><mixed-citation xml:lang="ru">Посыпкин, М. А. Комбинированный параллельный алгоритм решения задачи о ранце / М. А. Посыпкин // Труды четвертой международной конференции «Параллельные вычисления и задачи управления» (Москва, 27–29 октября 2008 г.). – С. 177–189.</mixed-citation><mixed-citation xml:lang="en">Посыпкин, М. А. Комбинированный параллельный алгоритм решения задачи о ранце / М. А. Посыпкин // Труды четвертой международной конференции «Параллельные вычисления и задачи управления» (Москва, 27–29 октября 2008 г.). – С. 177–189.</mixed-citation></citation-alternatives></ref><ref id="cit3"><label>3</label><citation-alternatives><mixed-citation xml:lang="ru">Чебаков, С. В. Алгоритм решения заданных комбинаторных задач на основе модели многокритериальной оптимизации / С. В. Чебаков, Л. В. Серебряная // Доклады БГУИР. – 2015. – № 4 (90). – С 16–22.</mixed-citation><mixed-citation xml:lang="en">Чебаков, С. В. Алгоритм решения заданных комбинаторных задач на основе модели многокритериальной оптимизации / С. В. Чебаков, Л. В. Серебряная // Доклады БГУИР. – 2015. – № 4 (90). – С 16–22.</mixed-citation></citation-alternatives></ref><ref id="cit4"><label>4</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref></ref-list><fn-group><fn fn-type="conflict"><p>The authors declare that there are no conflicts of interest present.</p></fn></fn-group></back></article>
