Эвристический алгоритм поиска приближённого решения задачи Штейнера, основанный на физических аналогиях
Лисин А.В., Файзуллин Р.Т.

PDF, 1066 kB

DOI: 10.18287/0134-2452-2013-37-4-503-510

Страницы: 503-510.

Аннотация:
В статье проводится анализ существующих подходов к решению задачи Штейнера на основе физических аналогий. На основании анализа существующих решений предложен алгоритм поиска минимальных деревьев Штейнера, основанный на физических аналогиях и использующий триангуляцию Делоне для начального приближения. Приводится сравнение результатов работы предложенного алгоритма с результатами алгоритма с экспоненциальной сложностью, дающего оптимальные решения..

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

Литература:

  1. Courant, R. What is Mathematics / R. Courant, H. Robbins. – Oxford University Press, 1996. – 556 p.
  2. Hwang, F. The Steiner Tree Problem / F.K. Hwang, D.S. Richards, P. Winter // Annals of Discrete mathematics. – 1992. – Vol. 53.
  3. Yang, Z.-X. Geometry Experiment Algorithm Steiner Minimal Tree Problem / Z.-X. Yang, X.-Y. Kia, J.-Y. Hao, Y.-P. Gao // Journal of Applied Mathematics. – 2013. – Vol. 2013. – P. 1-10.
  4. Богаченко, Н.Ф. Механические аналогии в задаче Штейнера / Н.Ф. Богаченко, Р.Т. Файзуллин // Математические структуры и моделирование. – 2002. – № 9. – С. 1-8.
  5. Gilbert, E.N. Steiner Minimal Trees / E.N. Gilbert, H.O. Pol­lak // Journal on Applied Mathematics. – 1968. – Vol. 16. – P. 323-345.
  6. Кормен, Т. Алгоритмы. Построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. – 2-е изд. – М.: Издательский дом «Вильямс», 2012. – 1296 с.
  7. Скворцов, А.В. Триангуляция Делоне и её применение / А.В. Скворцов. – Томск: Издательство Томского университета, 2002. – 128 с.
  8. Marcelo, Z.N. An Interactive Programme for Steiner trees [Электронный ресурс]. URL: http://arxiv.org/abs/1210.7788 (дата обращения 28.08.2013).
  9. Берн, М.У. / Поиск кратчайших сетей / М.У. Берн, Р.Л. Грэм // В мире науки. – 1989. – № 3.
  10. Du, D.Z. An approach for proving lower bounds: Solution of Gilbert–Pollak’s conjuncture on Steiner ratio / D.Z. Du, F.K. Hwang // Proc. 31-st Annual Symp. On Found. Of Comput. Sci. – 1990. – P. 76-85.
© 2009, IPSI RAS
Institution of Russian Academy of Sciences, Image Processing Systems Institute of RAS, Russia, 443001, Samara, Molodogvardeyskaya Street 151; E-mail: ko@smr.ru; Phones: +7 (846) 332-56-22, Fax: +7 (846) 332-56-20