Вестник КРАУНЦ. Физ.-мат. науки. 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
- Гилберт Э.Н., Поллак Г.О., “Минимальные деревья Штейнера”, Кибернетический сборник, 1971, № 1(6), 19–49. [Gilbert EH.N., Pollak G.O., “Minimal’nye derev’ya SHtejnera”, Kiberneticheskij sbornik, 1971, № 1(6), 19–49].
- Гордеев Э.Н., Тарасцов О.Г., “Задача Штейнера. Обзор”, Дискретная математика, 2 (1993), 3–28. [Gordeev EH.N., Tarascov O.G., “Zadacha SHtejnera. Obzor”, Diskretnaya matematika, 2 (1993), 3–28].
- Melzak Z.A., “On the problem of Steiner”, Canad. Math. Bull, 4 (1961), 143–148.
- Cockayne E.J., “On the efficiency of the algorithm for Steiner minimal trees”, SIAM J. Appl. Math, 18 (1970), 150–159.
- Boyce W.M., “An improved program for the full Steiner tree problem”, ACM Trans. jn Math. Software, 3 (1977), 359–385.
- 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..
- Панюков А.В., “Топологические методы решения задачи Штейнера на графе”, Автоматика и телемеханика, 2004, № 3, 89–99. [Panyukov A.V., “Topologicheskie metody resheniya zadachi SHtejnera na grafe”, Avtomatika i telemekhanika, 2004, № 3, 89–99].
- Кельманс А. К., “Построение минимального покрывающего дерева”, Кибернетика и управление, Наука, М., 1967, 115–130. [Kel’mans A. K., “Postroenie minimal’nogo pokryvayushchego dereva”, Kibernetika i upravlenie, Nauka, M., 1967, 115–130].
- Лотарев Д.Т., Уздемир А.П., “Преобразование задачи Штейнера на евклидовой плоскости к задаче Штейнера на графе”, Автоматика и телемеханика, 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].
- 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.
- Лотарев Д. Т., “Задача Штейнера для транспортной сети на поверхности заданной цифровой моделью”, Автоматика и телемеханика, 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].
- Gilbert E. N., “Minimal Cost Communication Networks”, Bell System technological Journal, 1967, № 9, 48–50.
- Багов М. А, Кудаев В. Ч., “Локальное решение сетевой задачи Штейнера”, Доклады Адыгской (Черкесской) Академии наук, 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].
- Багов М. А, Кудаев В. Ч., “Преобразование терминальной сети в сеть Штейнера”, Известия КБНЦ РАН, 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].
- Багов М. А., Кудаев В. Ч., “Сетевая задача Штейнера с учетом энергетических затрат”, Вестник КРАУНЦ. Физ.-мат. науки, 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].
- Багов М. А., Кудаев В. Ч., “Математическое моделирование и оптимизация трубопроводной сети Штейнера”, Известия Кабардино-Балкарского научного центра РАН, 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)].
- Меренков А.П., Сеннова Е.В., Сумароков С.В. и др., Математическое моделирование и оптимизация систем тепло-, водо-, нефте- и газоснобжения, Наука, Новосибирск, 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.]
- Булатов В.П., Кассинская Л.И., “Некоторые методы минимизации вогнутой функции на выпуклом многограннике”, Методы оптимизации и их приложения, Иркутск, СЭИ СО АН СССР, 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].
- Туй Х., “Вогнутое программирование при линейных ограничениях”, Доклады АН СССР, 1964, № 159(1), 32–35. [Mihalevich V. S., Trubin V. A., SHor N. Z., Optimizacionnye zadachi proizvodstvenno-transportnogo planirovaniya, Nauka, M., 1986, 260 pp.]
- Михалевич В. С., Трубин В. А., Шор Н. З., Оптимизационные задачи производственно-транспортного планирования, Наука, М., 1986, 260 с. [Mihalevich V. S., Trubin V. A., SHor N. Z., Optimizacionnye zadachi proizvodstvenno-transportnogo planirovaniya, Nauka, M., 1986, 260 pp.]
- Трубин В. А., Свойства и методы решения задач оптимального синтеза сетей, Об-во “Знание” УССР, Киев, 1982. [Trubin V. A., Svojstva i metody resheniya zadach optimal’nogo sinteza setej, Ob-vo “Znanie” USSR, Kiev, 1982].
Список литературы (ГОСТ)
- Гилберт Э.Н., Поллак Г.О. Минимальные деревья Штейнера // Кибернетический сборник. 1971. №1(6). С. 19-49.
- Гордеев Э.Н., Тарасцов О.Г. Задача Штейнера. Обзор // Дискретная математика. 1993. №2. С. 3-28.
- Melzak Z.A. On the problem of Steiner // Canad. Math. Bull. 1961. vol. 4. P. 143-148.
- Cockayne E.J. On the efficiency of the algorithm for Steiner minimal trees // SIAM J. Appl. Math. 1970. vol. 18. P. 150-159.
- Boyce W.M. An improved program for the full Steiner tree problem // ACM Trans. jn Math. Software. 1977. vol 3. P. 359-385.
- 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.
- Панюков А.В. Топологические методы решения задачи Штейнера на графе // Автоматика и телемеханика. 2004. №3. С. 89-99.
- Кельманс А.К. Построение минимального покрывающего дерева / Кибернетика и управление. М.: Наука, 1967. P. 115-130.
- Лотарев Д.Т., Уздемир А.П. Преобразование задачи Штейнера на евклидовой плоскости к задаче Штейнера на графе // Автоматика и телемеханика. 2005. №10. С. 80-92.
- 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.
- Лотарев Д.Т. Задача Штейнера для транспортной сети на поверхности заданной цифровой моделью // Автоматика и телемеханика. 1980. №10. С. 104-115.
- Gilbert E.N. Minimal Cost Communication Networks. Bell System technological Journal. 1967. no. 9. P. 48-50.
- Багов М.А, Кудаев В.Ч. Локальное решение сетевой задачи Штейнера // Доклады Адыгской (Черкесской) Академии наук. 2014. №16(4). С. 9-14.
- Багов М.А, Кудаев В.Ч. Преобразование терминальной сети в сеть Штейнера // Известия КБНЦ РАН. 2015. №6(68). С. 31-37.
- Багов М.А., Кудаев В.Ч. Сетевая задача Штейнера с учетом энергетических затрат // Вестник КРАУНЦ. Физ.-мат. науки. 2016. №4-1(16). С. 85-92.
- Багов М.А., Кудаев В.Ч. Математическое моделирование и оптимизация трубопроводной сети Штейнера // Известия Кабардино-Балкарского научного центра РАН. 2017. №1(73).
- Меренков А.П., Сеннова Е.В., Сумароков С.В. и др. Математическое моделирование и оптимизация систем тепло-, водо-, нефте- и газоснобжения. Новосибирск: Наука, 1992. 407 c.
- Булатов В.П., Кассинская Л.И. Некоторые методы минимизации вогнутой функции на выпуклом многограннике / Методы оптимизации и их приложения. Иркутск: СЭИ СО АН СССР, 1987. C. 151-172.
- Туй Х. Вогнутое программирование при линейных ограничениях // Доклады АН СССР. 1964. №159(1). С. 32-35.
- Михалевич В.С., Трубин В.А., Шор Н.З. Оптимизационные задачи производственно-транспортного планирования. М.: Наука, 1986. 260 c.
- Трубин В.А. Свойства и методы решения задач оптимального синтеза сетей. Киев: Об-во «Знание» УССР, 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
Багов Марат Алиевич – научный сотрудник отдела Систем автоматизированного проектирования смешанных систем и управления, институт прикладной математики и автоматизации, Кабардино-Балкарская Республика, г. Нальчик, Россия.
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.
Скачать статью Багов М.А.