|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
Об одном приближенном решении прямоугольной задачи Штейнерадипломная работа (Бакалавр)
- Научный руководитель: Половников В.С.
- Автор: Дипчак Анна Сергеевна
- Тип: Бакалавр
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Год защиты: 2011
- Аннотация: Анна Дипчак занимается решением прямоугольной задачи Штейнера, в общем виде являющейся NP-полной. В дипломной работе ею был разработан полиномиальный алгоритм сложности О(n^2), находящий приближенное решение, проведено сравнение предлагаемого алгоритма с другими существующими эвристическими алгоритмами, статистические сравнительные оценки длин получаемого алгоритмом штейнерового дерева с длиной минимального прямоугольного штейнерового дерева. Так же была в виде гипотезы выдвинута процедура приведения получаемого дерева к минимальному.
- Добавил в систему: Половников Владимир Сергеевич