Эвристический алгоритм поиска приближённого решения задачи Штейнера, основанный на физических аналогиях
Автор: Лисин Андрей Владимирович, Файзуллин Рашит Тагирович
Журнал: Компьютерная оптика @computer-optics
Рубрика: Обработка изображений: Восстановление изображений, выявление признаков, распознавание образов
Статья в выпуске: 4 т.37, 2013 года.
Бесплатный доступ
В статье проводится анализ существующих подходов к решению задачи Штейнера на основе физических аналогий. На основании анализа существующих решений предложен алгоритм поиска минимальных деревьев Штейнера, основанный на физических аналогиях и использующий триангуляцию Делоне для начального приближения. Приводится сравнение результатов работы предложенного алгоритма с результатами алгоритма с экспоненциальной сложностью, дающего оптимальные решения.
Задача штейнера, эвристический алгоритм, триангуляция делоне
Короткий адрес: https://sciup.org/14059198
IDR: 14059198
Heuristic algorithm for finding approximate solution of Steiner problem based on physical analogies
The article contains analyze of existent methods for solving Steiner problem that use physical analogies. Algorithm for construction of minimal Steiner trees based on existent solutions and Delaunay triangulation for initial approximation is suggested. Done comparison of suggested algorithm output and one with exponential complexity, which produces exact results.
