с 01.01.1989 по 01.01.2024
Алматы, Казахстан
Важным этапом в проектировании инженерных сетей является разработка конфигурации сети, отвечающая наперед заданным условиям. Основным для построения оптимизационных геометрических моделей является построения кратчайших линий связующих заданное дискретное множество точек пространства. Такие модели также выявляют геометрические факторы и определют те или иные свойства конфигурации сети в рассматриваемом физическом пространстве. Геометрические модели определяют образ проектируемого объекта, поэтому можно построить различные конфигурации трассировки сети, которые и позволяют выбрать оптимальную сеть. Для решения данной инженерной задачи в статье исследованы и разработаны оптимальные геометрические модели на плоскостях с евклидовой, ортогональной, полярной метрикой и алгоритмы для них. Разработан единый алгоритм трассировки разветвленных инженерных сетей на плоскостях с различной метрикой. Поставленная цель достигается применением и обобщением метода Штейнера. Как известно, проблема Штейнера связана с задачами построения минимального связующего дерева и в общем виде не решена. Практическое решение задачи трассировки заключается в поиске конфигурации разветвленной сети, имеющей наименьшую протяженность, что значительно влияет на ее стоимость. На первом этапе проектирования разрабатываются геометрические модели инженерных сетей, затем решаются оптимизационные задачи, которые сводятся к решению проблемы Я. Штейнера в общем виде [5; 27]. Алгоритм для решения задачи Штейнера основан на разбиении заданных дискретных точек плоскости на локальное подмножество, при этом применяется принцип наименьшего удлинения и сравнительный анализ различных геометрических моделей, которые позволяют выбрать и построить сеть требуемой конфигурации. Сформулирован единый алгоритм трассировки для построения конфигурации евклидовой, ортогональной и полярной сети. Сложность решения задачи Штейнера и инженерных задач трассировки обусловлена тем, что эти задачи принадлежат к экстремальным и к классу NP-трудных задач дискретной оптимизации.
геометрические модели, трассировка сети, кратчайшие линий, задача Штейнера, евклидова сеть Штейнера, ортогональная сеть Штейнера, полярная сеть Штейнера
1. Ананьев A.A. Новый алгоритм оптимизации дизайна транспортных сетей с учетом ограничений [Текст] / А.А. Ананьев, П.В. Ломовицкий, Д.В. Ужегов, А.Н. Хлюпин // Вычислительные методы и программирование. — М.: Научно-исследовательский вычислительный центр МГУ им. М.В. Ломоносова, 2017. Т. 18. — С. 158–168. — DOI:https://doi.org/10.26089/NumMet.v18r213 EDN: https://elibrary.ru/VQSUNP
2. Бабаян Б.А. Нахождение связывающей сети абсолютно минимальной длины [Текст] / Б.А. Бабаян, B.С. Попов // Тр. семинара отдела структурных логических схем. М.: ИТМ и ВТ АН СССР, 1969. — Вып. 7. — С. 27–45.
3. Багов М.А. Нелокальное решение сетевой задачи Штейнера [Текст] / М.А. Багов // Вестник KРAУНC. Физ.мат наука. — 2018. — № 4. — С. 148–157. — DOIhttps://doi.org/10.18454/2079-6641- 2018-24-4-148-157 DOI: https://doi.org/10.18454/2079-6641-2018-24-4-148-157; EDN: https://elibrary.ru/VQHNBI
4. Гильберт Э.Н. Минимальные деревья Штейнера [Текст] / Э.Н. Гильберт, Г.О. Поллак // Кибернетический сборник. — М.: Мир, 1974. — Вып. 8. — С. 19–50.
5. Есмухан Ж.М. Прикладная геометрия инженерных сетей: монография [Текст] / Ж.М. Есмухан, К.А. Куспеков. — Алматы: Наука, 2012. — 132 с.
6. Кельманс А.К. О построении кратчайшей связывающей сети [Текст] / А.К. Кельманс // Кибернетика и управление. — М.: Наука, 1967. — С. 115–130.
7. Курейчик В.В. Теория эволюционных вычислений [Текст] / В.В. Курейчик, В.М. Курейчик, С.И. Родзин. М.: Физматлит, 2013. — 260 с.
8. Курейчик В.М. Гибридный алгоритм разбиения на основе природных механизмов принятия решений [Текст] / В.М Курейчик., Б.К. Лебедев, О.Б. Лебедев // Известия РАН. Искусственный интеллект и принятие решений. 2012. — С. 3–15.
9. Курейчик В.М. Планирование сверхбольших интегральных схем на основе интеграции моделей адаптивного поиска [Текст] / В.М. Курейчик, Б.К. Лебедев, В.Б. Лебедев // Известия РАН. Теория и системы управления. 2013 — № 1. — С. 84–101.
10. Куспеков К.А. Метод разбиение и построения кратчайших сетей на плоскости с евклидовой метрикой [Текст] / К.А.Куспеков // Материалы Международной-Всероссийской 66-научно-практической конференции. 18–19 октября 2012 г. Сибирская государственная автомобильно-дорожная академия (СибАДИ). — Омск, 2012. — С. 178–181.
11. Куспеков К.А. Геометрические методы трассировки транспортно-логистических сетей [Текст] / К.А Куспеков., С.И. Ротков // Материалы 26-й Международной конференции по компьютерной графике и зрению, ГрафиКОН. — 2016. — С. 531–534.12. Куспеков К.А. Алгоритм построения оптимальной конфигурации транспортной сети заводов [Текст] / К.А. Куспеков. — Алматы: Доклады Национальной академии наук Республики Казахстан. — 2010. – № 3. С. 97–99. EDN: https://elibrary.ru/XCVXSR
12. Куспеков К.А. Методика построения оптимальной конфигурации кратчайших связывающих линии для n точек плоскости с полярной метрикой [Текст] / К.А. Куспеков // Вестник КузГТУ. — 2012. — № 2. — С. 86–87. EDN: https://elibrary.ru/OXWNON
13. Куспеков К.А. Свидетельство. Пакет программ для ЭВМ: Построение геометрической модели расчета трассировки сети на плоскости с евклидовой, ортогональной и полярной метрикой применяемые в решении различных инженерных задач [Текст] / К.А. Куспеков, Ш.А. Джомартова, А.Т. Мазакова. — № 1912, ИС009522. Минюст РК, г. Астана. — 1 августа 2017.
14. Лебедев Б.К. Интеллектуальная процедура построения дерева Штейнера на основе процедур отсечки и сужения [Текст] / Б.К. Лебедев // Известия ТРТУ. — 2000. № 1. — С. 89. EDN: https://elibrary.ru/IJLUGZ
15. Лепаров М.Н. О геометрических основах проектирования технического объекта [Текст] / М.Н. Лепаров // Геометрия и графика. — 2019. — Т. 7. — № 2. — С. 28–38. DOI:https://doi.org/10.12737/2308-4898-2023-11-4-3-14 DOI: https://doi.org/10.12737/article_5d2c187251b6c8.21632403; EDN: https://elibrary.ru/CFHAMF
16. Лотарев Д.Т. Локальная оптимизация в задаче Штейнера на евклидовой плоскости [Текст] / Д.Т. Лотарев, А.В. Супрун, А.П. Уздемир // Автоматика и телемеханика. — 2004. — № 7. — С. 60–70. EDN: https://elibrary.ru/NQYVZF
17. Лотарев Д.Т. Задача Штейнера для транспортной сети на поверхности заданной цифровой моделью [Текст] / Д.Т. Лотарев // Автоматика и телемеханика. — 1980. № 10. — 104–115.
18. Прим Р.К. Кратчайшие связывающие сети и некоторые обобщения [Текст] / Р.К. Прим // Кибернетический сборник. — 1961. — № 2. — С. 95–107.
19. Прокофьев В.М. Некоторые свойства кратчайшей линии, соединяющей любое число точек плоскости [Текст] / В.М. Прокофьев // Ученые записки Моск. гос. пед. ин-та им. В.И. Ленина. — М.: Изд-во МГПИ, 1957. Вып. 3. — С. 53–67.
20. Сальков Н.А. Отражения развития инженерной геометрии в журнале «Геометрия и графика» [Текст] / Н.А. Сальков, Н.С. Кадыкова // Геометрия и графика. 2020. — Т. 8. — № 2. — С. 82–100. — DOI:https://doi.org/10.12737/23084898-2020-82-100 DOI: https://doi.org/10.12737/2308-4898-2020-82-100; EDN: https://elibrary.ru/PZHJOC
21. Сальков Н.А. Геометрическая составляющая технических инновации [Текст] / Н.А. Сальков // Геометрия и графика. –2018. — Т. 6. — № 2. — С. 85–94. — DOIhttps://doi.org/10.12737/article5b55a5163fa05307622109 DOI: https://doi.org/10.12737/article_5b55a5163fa053.07622109; EDN: https://elibrary.ru/XVRALZ
22. Чернышев Ю.О. К вопросу о построении деревьев Штейнера с различной шириной ветвей для связывания элементов трехмерных СБИС [Текст] / Ю.О. Чернышев, Н.Н. Венцов // Известия ЮФУ. Технические науки. 2009. — № 4. — С. 72–76. EDN: https://elibrary.ru/KUWJHV
23. Boyce W.M. An improved program for the full Steiner tree problem // ACM. Trans, on Math. Software. 1977. V. 3, pp. 359–385. DOI: https://doi.org/10.1145/355759.355764
24. Chang S. The generation of minimal trees with a Steiner topology // I. ACM. 1972. V. 19, pp. 669–711. DOI: https://doi.org/10.1145/321724.321733
25. Cockayne E. J. Exact computation on Steiner minimal trees in the plane / E.J. Cockayne, E.E. Hewgill // Inf. Proc. Letters.1989. V. 22, pp. 151–156. DOI: https://doi.org/10.1016/0020-0190(86)90062-1
26. Courant R. What is Mathematics / R. Courant, H. Robbins. Oxford University Press, 1996, p. 556. DOI: https://doi.org/10.1093/oso/9780195105193.001.0001
27. Hwang F. The Steiner Tree Problem / F.K. Hwang, D.S. Richards, P. Winter // Annals of Discrete mathematics. 1992. V. 53.
28. Korhonon P. An algorithm for transfor ming a spanning tree into a Steiner // Procc. 9 th Int. Progn. Symp., Budapest 1976. North Holland, Amsterdam, 1979, pp. 343–357.
29. Kuspekov K.A. Optimization geometric models of transport network tracing used in city planning. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences — ISPRS Archives, 2023, 48(5/W2-2023), pp. 63–69. DOI: https://doi.org/10.5194/isprs-archives-xlviii-5-w2-2023-63-2023; EDN: https://elibrary.ru/MINOUX
30. Melzak S.A. On the problem of Stelner // J. Canad. Math. Bull. 1961. V. 4, pp. 143–148. DOI: https://doi.org/10.4153/CMB-1961-016-2
31. Smith I.M. An 0 (n logn) heuristic algorithm for the Steiner minimal tree problems on the euclidaen metric / I.M. Smith, D.T. Lee, I.S. Liebman // Networks. 1981. V. 11, pp. 23–29. DOI: https://doi.org/10.1002/net.3230110104
32. Trifonov A.G. Formulation of the Optimization Problem and Numerical Methods of Its Solution, http://matlab.exponenta.ru/optimiz/book_2/index.php. Cited April 24, 2017.
33. Winter P. Anargoritm for the Steiner problem in the euchlidean plane // Networks. 1985. V. 15, pp. 323–345. DOI: https://doi.org/10.1002/net.3230150305
