ОБРАБОТКА ИЗОБРАЖЕНИЙ, РАСПОЗНАВАНИЕ ОБРАЗОВ

Эвристический алгоритм поиска приближённого решения задачи Штейнера, основанный на физических аналогиях

А. В. Лисин, Р. Т. Файзуллин

Омский государственный технический университет

Аннотация: В статье проводится анализ существующих подходов к решению задачи Штейнера на основе физических аналогий. На основании анализа существующих решений предложен алгоритм поиска минимальных деревьев Штейнера, основанный на физических аналогиях и использующий триангуляцию Делоне для начального приближения. Приводится сравнение результатов работы предложенного алгоритма с результатами алгоритма с экспоненциальной сложностью, дающего оптимальные решения.

Ключевые слова: задача Штейнера, эвристический алгоритм, триангуляция Делоне.

Поступила в редакцию: 14.09.2013