Д. Т. Лотарев, А. В. Супрун, А. П. Уздемир, “Локальная оптимизация в задаче Штейнера на евклидовой плоскости”, Автомат. и телемех., 2004, выпуск 7,страницы 60

Эта публикация цитируется в 4 статьях

Дискретная оптимизация

Локальная оптимизация в задаче Штейнера на евклидовой плоскости

Д. Т. Лотарев^a, А. В. Супрун^b, А. П. Уздемир^a

^a Институт системного анализа РАН, Москва
^b Московский физико-технический институт

Аннотация: Под локально оптимальным деревом Штейнера понимается дерево, в котором для некоторой заданной матрицы смежности точки Штейнера размещены оптимальным образом. Матрица смежности определяет точку локального минимума, а все допустимые для этой матрицы смежности размещения (координаты) точек Штейнера определяют окрестность минимума. Решение является локально оптимальным, если длину дерева невозможно уменьшить изменением размещения точек Штейнера. Рассмотрен алгоритм локальной оптимизации, основанный на идее метода покоординатного спуска.

Статья представлена к публикации членом редколлегии: Ю. С. Попков

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