Приближенный алгоритм $S^*$ для задачи Штейнера на евклидовых ориентированных графах

В работе рассматривается задача Штейнера на евклидовых ориентированных графах, т. е. таких, каждая вершина которых обладает евклидовыми координатами, а длины дуг определяются евклидовым расстоянием между их конечными вершинами. Задача формулируется следующим образом. Имея граф $G(M,N)$ с заданной на дугах фунцией $d\colon N \to \mathbb R_+$, такой, что $d(j)= \sqrt{(x_{\mathbf{beg} j}-x_{\mathbf{end} j})^2+(y_{\mathbf{beg} j}-y_{\mathbf{end} j})^2}$, начальную вершину $b\in M$, множество терминальных вершин $E\subset M$, необходимо найти наименьший подграф $G$, содержащий пути от $b$ до всех вершин из $E$. Задача Штейнера является NP-сложной. В работе предложен эвристический алгоритм, учитывающий взаимное расположение вершин графа для построения дерева Штейнера. Он основан на алгоритме динамического программирования, дающего точное решение. Его суть состоит в том, чтобы некоторым образом ограничить набор подмножеств терминальных вершин, для которых решается подзадача в методе динамического программирования, так, чтобы общее их число было ограничено полиномом от числа терминалов. (В исходном алгоритме рассматриваются всевозможные подмножества терминалов, т. е. всего $2^n$.) Представлены три разных способа ограничения множества терминальных подмножеств, доказывается полиномиальность алгоритма при таких ограничениях, приводится сравнение их эффективности и точности решения между собой, а также с другими известными приближенными методами. Библиогр. 10 назв.