4430
правок
Минимальные k-связные геометрические сети: различия между версиями
Материал из WEGA
Минимальные k-связные геометрические сети (посмотреть исходный код)
Версия от 13:31, 17 сентября 2016
, 17 сентября 2016→Нотация
Irina (обсуждение | вклад) м (→Нотация) |
Irina (обсуждение | вклад) м (→Нотация) |
||
| Строка 46: | Строка 46: | ||
'''Задача построения сети с повышенной живучестью''' | '''Задача построения сети с повышенной живучестью''' | ||
Для заданного набора S точек в <math>\mathbb{R}^d \;</math> и функции требования связности <math>r: S \times S \to \mathbb{N} \;</math> найти геометрическую сеть минимальной стоимости, охватывающую точки из S, такую, что для любой пары вершин <math>p, q \in S \;</math> подсеть имеет | Для заданного набора S точек в <math>\mathbb{R}^d \;</math> и функции требования связности <math>r: S \times S \to \mathbb{N} \;</math> найти геометрическую сеть минимальной стоимости, охватывающую точки из S, такую, что для любой пары вершин <math>p, q \in S \;</math> подсеть имеет <math>r_{p, q} \;</math> внутренне вершинно-непересекающихся (или реберно-непересекащихся, соответственно) путей между p и q. | ||
Во многих приложениях этой задачи, нередко считающихся наиболее интересными [9, 13], функция требования связности определяется при помощи функции от одного аргумента, присваивающей каждой вершине p ее тип связности | Во многих приложениях этой задачи, нередко считающихся наиболее интересными [9, 13], функция требования связности определяется при помощи функции от одного аргумента, присваивающей каждой вершине p ее тип связности <math>r_v \in \mathbb{N} \;</math>. Тогда для любой пары вершин <math>p, q \in S \;</math> требование связности <math>r_{p, q} \;</math> задается просто в виде <math>min \{ r_p, r_q \} \;</math> [12, 13, 17, 18]. В число таких приложений входит задача о вычислении дерева Штейнера, (см., например, [2]), в которой <math>r_p \in \{ 0, 1 \} \;</math> для любой вершины <math>p \in S \;</math>. | ||
Схема аппроксимации с полиномиальным временем выполнения (PTAS) представляет собой семейство алгоритмов | '''Схема аппроксимации с полиномиальным временем выполнения''' (PTAS) представляет собой семейство алгоритмов <math>\{ \mathcal{A}_\varepsilon \} \;</math>, такое, что для каждого фиксированного " > 0 алгоритм <math>\mathcal{A}_\varepsilon \;</math> исполняется за время, полиномиальное относительно размера входного графа, и обеспечивает <math>(1 + \varepsilon) \;</math>-аппроксимацию. | ||
== Родственные работы == | == Родственные работы == | ||
