Задача Штейнера. Обзор

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