4511
правок
Лес Штейнера: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 5: | Строка 5: | ||
== Постановка задачи == | == Постановка задачи == | ||
Построение леса Штейнера представляет собой фундаментальную задачу проектирования сетей. Говоря неформально, цель заключается в установлении соединений между парами вершин данной сети по минимальной стоимости. Это обобщение широко известной задачи построения [[дерево Штейнера|дерева Штейнера]]. К примеру, предположим, что телекоммуникационная компания получает от своих клиентов запросы на коммуникации. Каждому клиенту требуется соединение между двумя вершинами в данной сети. Задача компании заключается в построении сетевой инфраструктуры с минимальной стоимостью, удовлетворяющей всем запросам на коммуникации. | Построение леса Штейнера представляет собой фундаментальную задачу проектирования сетей. Говоря неформально, цель заключается в установлении соединений между парами вершин данной сети по минимальной стоимости. Это обобщение широко известной задачи построения [[дерево Штейнера|дерева Штейнера]]. К примеру, предположим, что телекоммуникационная компания получает от своих клиентов запросы на коммуникации. Каждому клиенту требуется соединение между двумя вершинами в данной сети. Задача компании заключается в построении сетевой инфраструктуры с минимальной стоимостью, удовлетворяющей всем запросам на коммуникации. | ||
== Формальное определение и нотация == | == Формальное определение и нотация == | ||
Экземпляр задачи построения дерева Штейнера I = (G, c, R) составляют неориентированный граф G = (V, E) с множеством вершин V и множеством ребер E, неотрицательная стоимостная функция c: E | Экземпляр задачи построения дерева Штейнера I = (G, c, R) составляют неориентированный граф G = (V, E) с множеством вершин V и множеством ребер E, неотрицательная стоимостная функция <math>c: E \to Q^+ \;</math> и множество пар вершин <math>R = \{ (s_1, t_1 ), ..., (s_k, t_k) \} \subseteq V \times V \;</math>. Пары в множестве R называются ''парами полюсов''. Допустимое решение задачи представляет собой подмножество <math>F \subseteq E \;</math> ребер графа G, такое, что для каждой пары полюсов <math>(s_i, t_i) \in R \;</math> существует путь между <math>s_i \;</math> и <math>t_i \;</math> в подграфе G[F], порожденном F. Пусть [[стоимость]] c(F) определяется как суммарная стоимость всех ребер в F, т.е. <math>c(F) = \sum_{e \in P} c(e) \;</math>. Задача заключается в нахождении допустимого решения F с минимальной стоимостью c(F). Легко заметить, что существует оптимальное решение, являющееся лесом. | ||