|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
Приближенные алгоритмы построения деревьев Штейнерадипломная работа (Специалист)
- Научный руководитель: Гасанов Э.Э.
- Автор: Ефимов Алексей Андреевич
- Тип: Специалист
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Год защиты: 2015
- Аннотация: В работе Алексея Ефимова рассматривается задача построения деревьев Штейнера в случае манхэттенской метрики. Исследованы свойства деревьев Штейнера в данной метрике и проведено сравнение с соответствующими свойствами в евклидовой метрике. Проведен сравнительный анализ основных алгоритмов построения стягивающих деревьев, близких по сложности к деревьям Штейнера. На основе анализа примеров, для которых данные алгоритмы дают наиболее сильное отличие по сложности от деревьев Штейнера, предложено 2 алгоритма построения стягивающих деревьев, дающие на всех примерах, кроме примера, называемого «лепестком», более хорошие результаты, чем известные алгоритмы. Наиболее интересным представляется второй алгоритм, названный автором «трезубцем», который побеждает известные алгоритмы на всех примерах, где эти алгоритмы работают плохо. Приведены оценки сложности предложенных алгоритмов, но они довольно грубые и могут быть снижены при более тонком подсчете.
- Добавил в систему: Гасанов Эльяр Эльдарович