Вестник КРАУНЦ. Физ.-мат. науки. 2018. № 4(24). C. 148-157. ISSN 2079-6641

Содержание

DOI: 10.18454/2079-6641-2018-24-4-148-157

ИНФОРМАЦИОННЫЕ И ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ

УДК 519.85; 519.17

НЕЛОКАЛЬНОЕ РЕШЕНИЕ СЕТЕВОЙ ЗАДАЧИ ШТЕЙНЕРА

М. А. Багов

Институт прикладной математики и автоматизации – филиал Федерального государственного бюджетного научного учреждения «Федеральный научный центр «Кабардино-Балкарский научный центр Российской академии наук» (ИПМА КБНЦ РАН)

E-mail: maratniipma@mail.ru

Представлены метод и алгоритм оптимизации потоковых сетей Штейнера основанные на динамической декомпозиции и ранговой оптимизации сети.

Ключевые слова: потоковая сеть Штейнера, ранговая оптимизация, динамическая декомпозиция, компьютерное проектирование.

 

INFORMATION AND COMPUTING TECHNOLOGIES

MSC 65K05; 94C15

A SOLUTION WITH NONLOCAL EFFECT TO THE STEINER PROBLEM IN NETWORKS

M. A. Bagov

Institute of Applied Mathematics and Automation of Kabardino-Balkarian Scientific Center of the Russian Academy of Sciences

E-mail: maratniipma@mail.ru

This paper presents optimization algorithms and methods for Steiner flow network problem employing optimal rank dynamic mode decomposition.

Key words: Steiner flow networks, rank optimization, dynamic mode decomposition, computer design.

Список литературы/References

  1. Гилберт Э.Н., Поллак Г.О., “Минимальные деревья Штейнера”, Кибернетический сборник, 1971, № 1(6), 19–49. [Gilbert EH.N., Pollak G.O., “Minimal’nye derev’ya SHtejnera”, Kiberneticheskij sbornik, 1971, № 1(6), 19–49].
  2. Гордеев Э.Н., Тарасцов О.Г., “Задача Штейнера. Обзор”, Дискретная математика, 2 (1993), 3–28. [Gordeev EH.N., Tarascov O.G., “Zadacha SHtejnera. Obzor”, Diskretnaya matematika, 2 (1993), 3–28].
  3. Melzak Z.A., “On the problem of Steiner”, Canad. Math. Bull, 4 (1961), 143–148.
  4. Cockayne E.J., “On the efficiency of the algorithm for Steiner minimal trees”, SIAM J. Appl. Math, 18 (1970), 150–159.
  5. Boyce W.M., “An improved program for the full Steiner tree problem”, ACM Trans. jn Math. Software, 3 (1977), 359–385.
  6. Boyce W. M., Seery J. B., STEINER 72: An improved version of the minimal network problem., Rech. Rep., 35, Comp.Sci. Res. CTR. Bell.Lab., Murray Hill, N.-Y..
  7. Панюков А.В., “Топологические методы решения задачи Штейнера на графе”, Автоматика и телемеханика, 2004, № 3, 89–99. [Panyukov A.V., “Topologicheskie metody resheniya zadachi SHtejnera na grafe”, Avtomatika i telemekhanika, 2004, № 3, 89–99].
  8. Кельманс А. К., “Построение минимального покрывающего дерева”, Кибернетика и управление, Наука, М., 1967, 115–130. [Kel’mans A. K., “Postroenie minimal’nogo pokryvayushchego dereva”, Kibernetika i upravlenie, Nauka, M., 1967, 115–130].
  9. Лотарев Д.Т., Уздемир А.П., “Преобразование задачи Штейнера на евклидовой плоскости к задаче Штейнера на графе”, Автоматика и телемеханика, 2005, № 10, 80–92. [Lotarev D.T., Uzdemir A.P., “Preobrazovanie zadachi SHtejnera na evklidovoj ploskosti k zadache SHtejnera na grafe”, Avtomatika i telemekhanika, 2005, № 10, 80–92].
  10. Korte B., Promel H.-J., Steger A., “Steiner trees in VLSI-layout”, Rep. 89566-OR, Inst fur Okon. und Op. Res. Rheinische, Fr.-Wil.-Univ.-Bonn, 1989.
  11. Лотарев Д. Т., “Задача Штейнера для транспортной сети на поверхности заданной цифровой моделью”, Автоматика и телемеханика, 1980, № 10, 104–115. [Lotarev D. T., “Zadacha SHtejnera dlya transportnoj seti na poverhnosti zadannoj cifrovoj model’yu”, Avtomatika i telemekhanika, 1980, № 10, 104–115].
  12. Gilbert E. N., “Minimal Cost Communication Networks”, Bell System technological Journal, 1967, № 9, 48–50.
  13. Багов М. А, Кудаев В. Ч., “Локальное решение сетевой задачи Штейнера”, Доклады Адыгской (Черкесской) Академии наук, 2014, № 16(4), 9–14. [Bagov M. A, Kudaev V. CH., “Lokal’noe reshenie setevoj zadachi SHtejnera”, Doklady Adygskoj (CHerkesskoj) Akademii nauk, 2014, № 16(4), 9–14].
  14. Багов М. А, Кудаев В. Ч., “Преобразование терминальной сети в сеть Штейнера”, Известия КБНЦ РАН, 2015, № 6(68), 31–37. [Bagov M. A, Kudaev V. CH., “Preobrazovanie terminal’noj seti v set’ SHtejnera”, Izvestiya KBNC RAN, 2015, № 6(68), 31–37].
  15. Багов М. А., Кудаев В. Ч., “Сетевая задача Штейнера с учетом энергетических затрат”, Вестник КРАУНЦ. Физ.-мат. науки, 2016, № 4-1(16), 85–92. [Bagov M. A., Kudaev V. Ch., “Setevaya zadacha SHtejnera s uchetom ehnergeticheskih zatrat”, Vestnik KRAUNC. Fiz.-mat. nauki, 2016, № 4-1(16), 85–92].
  16. Багов М. А., Кудаев В. Ч., “Математическое моделирование и оптимизация трубопроводной сети Штейнера”, Известия Кабардино-Балкарского научного центра РАН, 2017, № 1(73). [Bagov M. A., Kudaev V. CH., “Matematicheskoe modelirovanie i optimizaciya truboprovodnoj seti SHtejnera”, Izvestiya Kabardino-Balkarskogo nauchnogo centra RAN, 2017, № 1(73)].
  17. Меренков А.П., Сеннова Е.В., Сумароков С.В. и др., Математическое моделирование и оптимизация систем тепло-, водо-, нефте- и газоснобжения, Наука, Новосибирск, 1992, 407 с. [Merenkov A.P., Sennova E.V., Sumarokov S.V. i dr., Matematicheskoe modelirovanie i optimizaciya sistem teplo-, vodo-, nefte- i gazosnobzheniya, Nauka, Novosibirsk, 1992, 407 pp.]
  18. Булатов В.П., Кассинская Л.И., “Некоторые методы минимизации вогнутой функции на выпуклом многограннике”, Методы оптимизации и их приложения, Иркутск, СЭИ СО АН СССР, 1987, 151–172. [Bulatov V.P., Kassinskaya L.I., “Nekotorye metody minimizacii vognutoj funkcii na vypuklom mnogogrannike”, Metody optimizacii i ih prilozheniya, Irkutsk, SEHI SO AN SSSR, 1987, 151–172].
  19. Туй Х., “Вогнутое программирование при линейных ограничениях”, Доклады АН СССР, 1964, № 159(1), 32–35. [Mihalevich V. S., Trubin V. A., SHor N. Z., Optimizacionnye zadachi proizvodstvenno-transportnogo planirovaniya, Nauka, M., 1986, 260 pp.]
  20. Михалевич В. С., Трубин В. А., Шор Н. З., Оптимизационные задачи производственно-транспортного планирования, Наука, М., 1986, 260 с. [Mihalevich V. S., Trubin V. A., SHor N. Z., Optimizacionnye zadachi proizvodstvenno-transportnogo planirovaniya, Nauka, M., 1986, 260 pp.]
  21. Трубин В. А., Свойства и методы решения задач оптимального синтеза сетей, Об-во “Знание” УССР, Киев, 1982. [Trubin V. A., Svojstva i metody resheniya zadach optimal’nogo sinteza setej, Ob-vo “Znanie” USSR, Kiev, 1982].

Список литературы (ГОСТ)

  1. Гилберт Э.Н., Поллак Г.О. Минимальные деревья Штейнера // Кибернетический сборник. 1971. №1(6). С. 19-49.
  2. Гордеев Э.Н., Тарасцов О.Г. Задача Штейнера. Обзор // Дискретная математика. 1993. №2. С. 3-28.
  3. Melzak Z.A. On the problem of Steiner // Canad. Math. Bull. 1961. vol. 4. P. 143-148.
  4. Cockayne E.J. On the efficiency of the algorithm for Steiner minimal trees // SIAM J. Appl. Math. 1970. vol. 18. P. 150-159.
  5. Boyce W.M. An improved program for the full Steiner tree problem // ACM Trans. jn Math. Software. 1977. vol 3. P. 359-385.
  6. Boyce W.M., Seery J.B. STEINER 72: An improved version of the minimal network problem. Rech. Rep., 35, Comp.Sci. Res. CTR. Bell.Lab., Murray Hill, N.-Y.
  7. Панюков А.В. Топологические методы решения задачи Штейнера на графе // Автоматика и телемеханика. 2004. №3. С. 89-99.
  8. Кельманс А.К. Построение минимального покрывающего дерева / Кибернетика и управление. М.: Наука, 1967. P. 115-130.
  9. Лотарев Д.Т., Уздемир А.П. Преобразование задачи Штейнера на евклидовой плоскости к задаче Штейнера на графе // Автоматика и телемеханика. 2005. №10. С. 80-92.
  10. Korte B., Promel H.-J., Steger A. Steiner trees in VLSI-layout. Rep. 89566-OR, Inst fur Okon. und Op. Res. Rheinische, Fr.-Wil.-Univ.-Bonn. 1989.
  11. Лотарев Д.Т. Задача Штейнера для транспортной сети на поверхности заданной цифровой моделью // Автоматика и телемеханика. 1980. №10. С. 104-115.
  12. Gilbert E.N. Minimal Cost Communication Networks. Bell System technological Journal. 1967. no. 9. P. 48-50.
  13. Багов М.А, Кудаев В.Ч. Локальное решение сетевой задачи Штейнера // Доклады Адыгской (Черкесской) Академии наук. 2014. №16(4). С. 9-14.
  14. Багов М.А, Кудаев В.Ч. Преобразование терминальной сети в сеть Штейнера // Известия КБНЦ РАН. 2015. №6(68). С. 31-37.
  15. Багов М.А., Кудаев В.Ч. Сетевая задача Штейнера с учетом энергетических затрат // Вестник КРАУНЦ. Физ.-мат. науки. 2016. №4-1(16). С. 85-92.
  16. Багов М.А., Кудаев В.Ч. Математическое моделирование и оптимизация трубопроводной сети Штейнера // Известия Кабардино-Балкарского научного центра РАН. 2017. №1(73).
  17. Меренков А.П., Сеннова Е.В., Сумароков С.В. и др. Математическое моделирование и оптимизация систем тепло-, водо-, нефте- и газоснобжения. Новосибирск: Наука, 1992. 407 c.
  18. Булатов В.П., Кассинская Л.И. Некоторые методы минимизации вогнутой функции на выпуклом многограннике / Методы оптимизации и их приложения. Иркутск: СЭИ СО АН СССР, 1987. C. 151-172.
  19. Туй Х. Вогнутое программирование при линейных ограничениях // Доклады АН СССР. 1964. №159(1). С. 32-35.
  20. Михалевич В.С., Трубин В.А., Шор Н.З. Оптимизационные задачи производственно-транспортного планирования. М.: Наука, 1986. 260 c.
  21. Трубин В.А. Свойства и методы решения задач оптимального синтеза сетей. Киев: Об-во «Знание» УССР, 1982. 23 c.

 

Для цитирования: Багов М. А. Нелокальное решение сетевой задачи Штейнера // Вестник КРАУНЦ. Физ.-мат. науки. 2018. № 4(24). C. 148-157. DOI: 10.18454/2079-6641-2018-24-4-148-157.
For citation: Bagov M. A. A solution with nonlocal effect to the Steiner problem in networks, Vestnik KRAUNC. Fiz.-mat. nauki. 2018, 24: 4, 148-157. DOI: 10.18454/2079-6641-2018-24-4-148-157.

Поступила в редакцию / Original article submitted: 30.07.2018

  Багов Марbagат Алиевич – научный сотрудник отдела Систем автоматизированного проектирования смешанных систем и управления, институт прикладной математики и автоматизации, Кабардино-Балкарская Республика, г. Нальчик, Россия.
   Bagov Marat Alievich – Researcher of the Department of Systems-aided design and management of mixed systems, Institute of Applied Mathematics and Automation, Kabardino-Balkar Republic, Nalchik, Russia.

 

Скачать статью Багов М.А.