Другие журналы

научное издание МГТУ им. Н.Э. Баумана

НАУКА и ОБРАЗОВАНИЕ

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

Вероятностные характеристики минимальных деревьев Штейнера на манхэттенской плоскости

# 07, июль 2015
DOI: 10.7463/0715.0780838
Файл статьи: SE-BMSTU...o280.pdf (440.15Кб)
автор: Сальников В. Н.

УДК 519.176+514.76+519.23

Россия,  Московский Государственный Университет им. М.В.Ломоносова

В данной работе рассматриваются свойства минимальных деревьев Штейнера для случая манхеттенской плоскости в контексте введения вероятностной меры. Данная проблема является важной, так как точные алгоритмы решения задачи Штейнера имеют повышенную вычислительную сложность (NP-трудные), а результат ее решения (в особенности для большого числа соединяемых точек) имеет множество практических применений. В связи с этим в работе рассматривается возможность ранжирования возможных топологий минимальных деревьев с учетом вероятности их применения. Для этого проведен анализ известных фактов о структуре минимальных деревьев для выбранной метрики с целью оценки их полезности для названной задачи. Предложен вариант введения вероятностной меры для случая небольшого числа граничных (заданных) вершин как иллюстрация доказанной теоремы о структуре минимальных деревьев.
Данная работа рассматривается как продолжение предыдущей аналогичной деятельности для задачи поиска минимальных заполнений и представляет собой первый шаг в решении более общей (сложной) задачи. Изложенный метод демонстрирует возможность доведения всех вычислений до конца аналитически, что позволяет надеятся на возможность его расширения для большего числа граничных точек (возможно с применением вычислительной техники).
Благодаря введению понятия существенной точки Штейнера, удалось существенно ограничить неоднозначность решения исходной задачи одновременно сравнив такой подход с более классическими работами в данной области. Указаны основные проблемы, препятствующие применению классических подходов для задачи введения вероятностной меры.
В перспективе предполагается попытка расширения области применения описанного подхода как в плане увеличения размеров системы (количество граничных точек), так и выбранной метрики (особенный интерес представляет Евклидова метрика). В особенности представляет интерес возможность выделения классов топологий с существенно большей/меньшей вероятностью с целью принципиального ограничения количества вариантов проверяемых топологий.

Список литературы
  1. Karp Richard M. Reducibility among combinatorial problems // Complexity of Computer Computations: Proc. of a Symp. on the Complexity of Computer Computations / ed. by R.E. Miller, J.W. Thatcher. New York, NY: Plenum Press, 1972. P. 85-103. (The IBM Research Symposia Series).
  2. Garey M.R., Graham R.L., Johnson D.S. The Complexity of Computing Steiner Minimal Trees // Siam Journal on Applied Mathematics. 1977. Vol. 32, no. 4. P. 835-859. DOI: 10.1137/0132072
  3. Hwang F.K., Richards D.S., Winter P. The Steiner Tree Problem. North-Holland, New York, 1992. (Annals of Discrete Mathematics; vol. 53).
  4. Salnikov V. Probabilistic properties of topologies of finite metric spaces’ minimal fillings // Journal of Mathematical Sciences. 2014, Vol. 203, iss. 6. P. 873-883. DOI: 10.1007/s10958-014-2179-2
  5. Ivanov A.O., Tuzhilin A.A. One-dimensional Gromov minimal filling problem // Sbornik Mathematics. 2012. Vol. 203, no. 5. P. 677-726. DOI: 10.1070/SM2012v203n05ABEH004239
  6. Hanan M. On Steiner’s problem with rectilinear distance // Siam Journal on Applied Mathematics. 1966. Vol. 14, no. 2. P. 255 - 265. DOI: 10.1137/0114025
  7. Gromov M. Filling Riemannian manifolds // Journal of Differential Geometry. 1983. Vol. 18. P. 1-147.
  8. Ivanov A.O., Tuzhilin A.A. Gromov minimal fillings for finite metric spaces // Publications de l’Institut Mathematique. 2013. Vol. 94, iss. 108. P. 3-15. DOI: 10.2298/PIM1308003I
  9. Ivanov A.O., Tuzhilin A.A. Minimal fillings of finite metric spaces: The state of the art // In: Discrete Geometry and Algebraic Combinatorics / ed. by A. Bark, O. Musin. AMS, Providence, RI, US, 2014. P. 9–35. (Contemporary Mathematics; vol. 625). DOI: 10.1090/conm/625
  10. Gilbert E.N. Random minimal trees // Journal of the Society for Industrial and Applied Mathematics. 1965. Vol. 13, no. 2. P. 376-387. DOI: 10.1137/0113021
Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА
18.12.2017
С 21 по 24 ноября 2017г. в МГТУ им. Н.Э. Баумана прошла XII Всероссийская инновационная молодежная научно-инженерная выставка «Политехника», посвященная 170-летию со дня рождения Н.Е. Жуковского в рамках Всероссийского инновационного молодежного научно-инженерного форума «Политехника».

11.10.2017
XII Всероссийская инновационная молодежная научно-инженерная выставка «ПОЛИТЕХНИКА», посвященная 170-летию со дня рождения Н.Е. Жуковского 21–24 ноября 2017 года г. Москва

25.05.2017
C 15 по 17 мая 2017г. в МГТУ им. Н.Э. Баумана прошел III этап (Всероссийский) Всероссийской студенческой олимпиады по физике (в технических вузах).

25.04.2017
С 12 по 14 апреля в МГТУ им. Н.Э. Баумана прошел Всероссийский этап Всероссийской олимпиады по безопасности жизнедеятельности.

4.04.2017
С 14 по 16 марта 2017г. в МГТУ им. Н.Э. Баумана прошел III (Всероссийский) тур Всероссийской студенческой олимпиады по иностранному языку (английский в технических вузах).




Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2018 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)