<?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">sibsutis</journal-id><journal-title-group><journal-title xml:lang="ru">Вестник СибГУТИ</journal-title><trans-title-group xml:lang="en"><trans-title>The Herald of the Siberian State University of Telecommunications and Information Science</trans-title></trans-title-group></journal-title-group><issn pub-type="ppub">1998-6920</issn><publisher><publisher-name>СибГУТИ</publisher-name></publisher></journal-meta><article-meta><article-id custom-type="elpub" pub-id-type="custom">sibsutis-411</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></article-categories><title-group><article-title>Разработка и исследование моделей, методов и алгоритмов для синтеза и анализа решений задач геометрического покрытия</article-title><trans-title-group xml:lang="en"><trans-title></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>Zabelin</surname><given-names>S. ..</given-names></name></name-alternatives><email xlink:type="simple">zabelinsl@mail.ru</email><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>Frolovsky</surname><given-names>V. ..</given-names></name></name-alternatives><email xlink:type="simple">frolovsky@asu.cs.nstu.ru</email><xref ref-type="aff" rid="aff-2"/></contrib></contrib-group><aff xml:lang="ru" id="aff-1"><institution>СибГУТИ</institution><country>Russian Federation</country></aff><aff xml:lang="ru" id="aff-2"><institution>НГТУ</institution><country>Russian Federation</country></aff><pub-date pub-type="collection"><year>2013</year></pub-date><pub-date pub-type="epub"><day>26</day><month>10</month><year>2022</year></pub-date><volume>0</volume><issue>2</issue><fpage>42</fpage><lpage>53</lpage><permissions><copyright-statement>Copyright &amp;#x00A9; Забелин С.Л., Фроловский В.Д., 2022</copyright-statement><copyright-year>2022</copyright-year><copyright-holder xml:lang="ru">Забелин С.Л., Фроловский В.Д.</copyright-holder><copyright-holder xml:lang="en">Zabelin S..., Frolovsky 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://vestnik.sibsutis.ru/jour/article/view/411">https://vestnik.sibsutis.ru/jour/article/view/411</self-uri><abstract><p>Задача геометрического покрытия относится к классу NP -трудных задач комбинаторной оптимизации и исследуется в рамках проблемы «раскроя и упаковки». Требуется расположить различные геометрические объекты на покрываемой поверхности таким образом, чтобы вся поверхность была покрыта с наименьшей площадью перекрытий объектов, а также использовать наименьшее количество объектов. В статье рассматриваются реализации алгоритмов первого подходящего, вероятностного, экстремального, муравьиного и генетического алгоритмов. Данные метаэвристические алгоритмы можно адаптировать для решения задач в различных системах: освещения, агротехнических, охранных, беспроводной связи, воздушного наблюдения. Алгоритмы помогут повысить эффективность систем и уменьшить затраты на их проектирование и реализацию.</p></abstract><kwd-group xml:lang="ru"><kwd>задачи оптимизации геометрического покрытия</kwd><kwd>вероятностный алгоритм</kwd><kwd>экстремальный алгоритм</kwd><kwd>генетический алгоритм</kwd><kwd>муравьиный алгоритм</kwd><kwd>метаэвристические алгоритмы</kwd></kwd-group><kwd-group xml:lang="en"><kwd>NP-трудные задачи</kwd><kwd>optimization problem of geometric coverage</kwd><kwd>NP-completeness problems</kwd><kwd>probabilistic algorithm</kwd><kwd>extreme algorithm</kwd><kwd>genetic algorithm</kwd><kwd>ant algorithm</kwd><kwd>metaheuristic algorithms</kwd></kwd-group></article-meta></front><back><ref-list><title>References</title><ref id="cit1"><label>1</label><citation-alternatives><mixed-citation xml:lang="ru">Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометрического проектирования. Киев. Наукова думка. 1986. 268 с.</mixed-citation><mixed-citation xml:lang="en">Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометрического проектирования. Киев. Наукова думка. 1986. 268 с.</mixed-citation></citation-alternatives></ref><ref id="cit2"><label>2</label><citation-alternatives><mixed-citation xml:lang="ru">Канторович Л.В., Заллгаллер В.А. Рациональный раскрой промышленных материалов. СПб. Невский диалект. 2012. -304 с.</mixed-citation><mixed-citation xml:lang="en">Канторович Л.В., Заллгаллер В.А. Рациональный раскрой промышленных материалов. СПб. Невский диалект. 2012. -304 с.</mixed-citation></citation-alternatives></ref><ref id="cit3"><label>3</label><citation-alternatives><mixed-citation xml:lang="ru">Романовский И.В. Алгоритмы решения экстремальных задач. М. Наука. 1977. -420 с.</mixed-citation><mixed-citation xml:lang="en">Романовский И.В. Алгоритмы решения экстремальных задач. М. Наука. 1977. -420 с.</mixed-citation></citation-alternatives></ref><ref id="cit4"><label>4</label><citation-alternatives><mixed-citation xml:lang="ru">Мухачева Э.А., Верхотуров М.А., Мартынов В.В. Модели и методы расчёта раскроя-упаковки геометрических объектов. Уфа. УГАТУ. 1998. 216 с.</mixed-citation><mixed-citation xml:lang="en">Мухачева Э.А., Верхотуров М.А., Мартынов В.В. Модели и методы расчёта раскроя-упаковки геометрических объектов. Уфа. УГАТУ. 1998. 216 с.</mixed-citation></citation-alternatives></ref><ref id="cit5"><label>5</label><citation-alternatives><mixed-citation xml:lang="ru">Мухачева Э.А., Валихметов Ю.И., Телицкий С.В., Хасанова Э.И. Проектирование размещения ортогональных объектов на полигонах с препятствиями. Информационные технологии. 2010. № 10. – С. 16-22.</mixed-citation><mixed-citation xml:lang="en">Мухачева Э.А., Валихметов Ю.И., Телицкий С.В., Хасанова Э.И. Проектирование размещения ортогональных объектов на полигонах с препятствиями. Информационные технологии. 2010. № 10. – С. 16-22.</mixed-citation></citation-alternatives></ref><ref id="cit6"><label>6</label><citation-alternatives><mixed-citation xml:lang="ru">Мухачева А. С. Простые эвристики для решения двумерной задачи максимального покрытия. // Принятие решений в условиях неопределённости. Межвузовский научный сборник. Вып.2. Ч.1. Уфа: УГАТУ. 2005. С.24-32.</mixed-citation><mixed-citation xml:lang="en">Мухачева А. С. Простые эвристики для решения двумерной задачи максимального покрытия. // Принятие решений в условиях неопределённости. Межвузовский научный сборник. Вып.2. Ч.1. Уфа: УГАТУ. 2005. С.24-32.</mixed-citation></citation-alternatives></ref><ref id="cit7"><label>7</label><citation-alternatives><mixed-citation xml:lang="ru">Телицкий С.В., Филиппова А.С. Комплексный подход к решению задачи покрытия области заготовками неопределённых размеров. Научно-технические ведомости СПбГПУ. Информатика. Телекоммуникации. Управление. 2012. 2(145)/2012. – С. 61-67.</mixed-citation><mixed-citation xml:lang="en">Телицкий С.В., Филиппова А.С. Комплексный подход к решению задачи покрытия области заготовками неопределённых размеров. Научно-технические ведомости СПбГПУ. Информатика. Телекоммуникации. Управление. 2012. 2(145)/2012. – С. 61-67.</mixed-citation></citation-alternatives></ref><ref id="cit8"><label>8</label><citation-alternatives><mixed-citation xml:lang="ru">Филиппова А.С., Кузнецов В.Ю. Задачи о минимальном покрытии ортогональных многоугольников с запретными участками. Информационные технологии. 2008. №9 (145). 2008. С. 60-65.</mixed-citation><mixed-citation xml:lang="en">Филиппова А.С., Кузнецов В.Ю. Задачи о минимальном покрытии ортогональных многоугольников с запретными участками. Информационные технологии. 2008. №9 (145). 2008. С. 60-65.</mixed-citation></citation-alternatives></ref><ref id="cit9"><label>9</label><citation-alternatives><mixed-citation xml:lang="ru">Курейчик В.М., Гладков Л.А., Курейчик В.В. Генетические алгоритмы. М. ФИЗМАТЛИТ. 2006. -320 с.</mixed-citation><mixed-citation xml:lang="en">Курейчик В.М., Гладков Л.А., Курейчик В.В. Генетические алгоритмы. М. ФИЗМАТЛИТ. 2006. -320 с.</mixed-citation></citation-alternatives></ref><ref id="cit10"><label>10</label><citation-alternatives><mixed-citation xml:lang="ru">Фроловский В.Д. Приближённые методы решения NP-трудных задач в системах автоматизации проектирования. Новосибирск. НГТУ. 2006. 100 с.</mixed-citation><mixed-citation xml:lang="en">Фроловский В.Д. Приближённые методы решения NP-трудных задач в системах автоматизации проектирования. Новосибирск. НГТУ. 2006. 100 с.</mixed-citation></citation-alternatives></ref><ref id="cit11"><label>11</label><citation-alternatives><mixed-citation xml:lang="ru">Фроловский В.Д. Оптимизация раскроя материалов на оборудовании с ЧПУ (модели, методы, алгоритмы). Издательский Дом: LAP LAMBERT Academic Publishing. Saarbrücken, Germany. 2011. 124 с.</mixed-citation><mixed-citation xml:lang="en">Фроловский В.Д. Оптимизация раскроя материалов на оборудовании с ЧПУ (модели, методы, алгоритмы). Издательский Дом: LAP LAMBERT Academic Publishing. Saarbrücken, Germany. 2011. 124 с.</mixed-citation></citation-alternatives></ref><ref id="cit12"><label>12</label><citation-alternatives><mixed-citation xml:lang="ru">Dorigo, M. The ant system: Optimization by a colony of cooperating agents / M. Dorigo, V. Maniezzo, A. Colorni // IEEE Transactions on Systems, Man and Cybernetics. 1996. №26. P. 29–41.</mixed-citation><mixed-citation xml:lang="en">Dorigo, M. The ant system: Optimization by a colony of cooperating agents / M. Dorigo, V. Maniezzo, A. Colorni // IEEE Transactions on Systems, Man and Cybernetics. 1996. №26. P. 29–41.</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>
