Эвристический алгоритм поиска приближённого решения задачи Штейнера, основанный на физических аналогиях
Автор: Лисин Андрей Владимирович, Файзуллин Рашит Тагирович
Журнал: Компьютерная оптика @computer-optics
Рубрика: Обработка изображений: Восстановление изображений, выявление признаков, распознавание образов
Статья в выпуске: 4 т.37, 2013 года.
Бесплатный доступ
В статье проводится анализ существующих подходов к решению задачи Штейнера на основе физических аналогий. На основании анализа существующих решений предложен алгоритм поиска минимальных деревьев Штейнера, основанный на физических аналогиях и использующий триангуляцию Делоне для начального приближения. Приводится сравнение результатов работы предложенного алгоритма с результатами алгоритма с экспоненциальной сложностью, дающего оптимальные решения.
Задача штейнера, эвристический алгоритм, триангуляция делоне
Короткий адрес: https://sciup.org/14059198
IDR: 14059198
