Просмотр кода страницы Задача о 1-центре

'''Задача о 1-центре''' или '''минимаксная задача размещения объектов''' — это классическая задача [[Комбинаторная оптимизация|комбинаторной оптимизации]], задача в дисциплине «[[исследование операций]]», — частный случай [[Задача о размещении объектов|задачи о размещении объектов]]. В наиболее общем случае формулируется следующим образом:
: Задано множество местоположений потребителей, пространство возможных точек размещения объектов (производства или обслуживания) и функция стоимости перевозки от любой точки возможного размещения до точки потребления
: Нужно найти оптимальную точку расположения объектов, минимизирующее максимальную стоимость доставки от объекта до потребителя.

Простой частный случай, когда объекты размещения и точки потребления находятся на плоскости, а стоимостью доставки является евклидово расстояние ('''планарная минимаксная евклидова задача размещения объектов, евклидова задача о 1-центре на плоскости'''), известна также как [[задача о наименьшей окружности]]. Её обобщение на многомерные евклидовы пространства известно как [[Ограничивающая сфера|задача о наименьшей ограничивающей сфере]]. В дальнейшем обобщении ('''взвешенная евклидова задача размещения''') точкам потребления приписаны веса и цена транспортировки является суммой расстояний, умноженных на соответствующие веса. Другой частный случай — {{не переведено 5|задача о ближайшей строке|||closest string}}, когда входом задачи служит [[Строковый тип|строка]], а расстояние измеряется как [[расстояние Хэмминга]].

Существуют многочисленные частные случаи задачи, зависящие как от выбора местоположения точек потребления и объектов производства (или обслуживания), так и от выбора функции, вычисляющей расстояние.

== Задача о 1-центре в терминах теории графов ==
Постановка такого варианта задачи заключается в том, что дан [[Граф (математика)|граф]] <math>G = (V, E)</math>, <math>k \in \mathbb{N}</math> а также функция стоимости <math>c \colon E \to \mathbb{Q}^+</math> и необходимо найти множество <math>Z \subset V</math> такое, что <math>\operatorname{rad}(Z) = \max_{v \in V} \min_{z \in Z} c(z, v)</math> для него минимально, т.е. такое множество <math>Z</math>, что максимальная стоимость пути из ближайшей к любой вершине <math>Z</math> вершины останется минимальной. Также задача может быть дополнена фугкцией стоимости вершин <math>w \colon V \to \mathbb{Q}^+</math>и тогда радиус для нее будет определяться как <math>\operatorname{rad}(Z) = \max_{v \in V} [w(v) \cdot \min_{z \in Z} c(z, v)]</math>. 

Идея приближенного решения задачи заключается в поиске <math>Z</math> [[Жадный алгоритм|жадным алгоритмом]] для фиксированного радиуса <math>R</math>. Пока существуют вершины, не покрытые <math>Z</math>, необходимо жадно выбрать вершину <math>z</math> и рассматривать все другие вершины в доступности <math>2R</math>. Алгоритм повторяется для разных значений <math>R</math>. Далее приведено описание метода в формальном виде:

# Установи <math>Z = \emptyset</math> и <math>U = V</math>.
# Пока <math>U \neq \emptyset</math>:
## <math>z = \operatorname{argmax}\{w(u) \mid u \in U\}</math>.
## <math>Z = Z \cup \{z\}</math>.
## <math>U = U \setminus \{v \in U \mid w(v) \cdot \operatorname{dist}(v, z) \leqslant 2R \}</math>.
# Выведи <math>Z</math>.

Пусть <math>R^*</math> - оптимальное решение для <math>Z^*</math>. В случае, когда <math>R \geqslant R^*</math>, жадный алгоритм вернет множество <math>Z</math> такое, что <math>|Z| \leqslant |Z^*|</math>. Исходя из этого определим <math>f(R) = |\operatorname{GreedyCenter}(G, c, w, R)|</math> и заметим, что функция <math>f</math> не [[Монотонная функция|монотонна]]. Далее обозначим радуис <math>R' = \max_{v \in V} [w(v) \cdot \sum_{e \in E} c(e)]</math>, с помощью которого лишь одна вершина в <math>Z</math> сможет покрыть все вершины графа, т.е. <math>f(R') = 1</math>, а <math>f(0) = |V| = n</math>.

Лемма. Для любого графа <math>G = (V, E)</math> с оптимальным множеством <math>Z^*</math> и радиусом <math>R^* = \operatorname{rad}(Z^*)</math> справедливо неравенство <math>f(R) \leqslant k</math> для всех <math>R \geqslant R^*</math>.

Доказательство. Пусть <math>V_i = \{v \in V \mid w(v) \cdot \operatorname{dist}(v, z_i) \leqslant R^*\}</math> и <math>z \in V_i</math> - выбранная вершина в цикле алгоритма <math>\operatorname{GreedyCenter}</math>. Тогда действительно неравенство:

{{center|<math>\begin{align}
w(v) \cdot \operatorname{dist}(v, z) & \leqslant w(v) \cdot (\operatorname{dist}(v, v_i) + \operatorname{dist}(v_i, z)) \\
& \leqslant w(v) \cdot \operatorname{dist}(v, v_i) + w(z) \cdot \operatorname{dist}(v_i, z) \\
& \leqslant 2 \cdot R^* \leqslant 2 \cdot R
\end{align}</math>}}Все вершины из <math>V_i</math> будут удалены в конце итерации, а значит, цикл завершится максимум через <math>k = |Z^*|</math> итераций, а следовательно <math>|Z| \leqslant k</math>.

Из леммы следует, что запускать жадный алгоритм можно до тех пор, пока результирующее множество <math>Z</math> не станет меньше требуемого <math>k</math>, используя для вычисления радиусов [[Матрица расстояний|матрицу расстояний]]. Таким образом общая временная сложность алгоритма равна <math>O(n^4)</math>, а фактор аппроксимации равен <math>2</math>.  

== Разрешимость ==
При условии [[Равенство классов P и NP|неравенства классов P и NP]] для любого <math>r < 2</math> не существует полиномиального алгоритма с фактором аппроксимации <math>r</math>. Доказательство этого утверждения сводится к редукции к [[Доминирующее множество|задаче о доминирующем множестве]]: Пусть <math>(G, k)</math> подается на вход алгоритму, решающему задачу о доминирующем множестве. Также пусть <math>c(e) = 1</math> для всех рёбер <math>e \in E(G)</math>. Тогда <math>G</math> содержит домнирующее множество размера <math>k</math>, если множество <math>Z</math> содержит <math>k</math> вершин и радиус (<math>\operatorname{rad}(Z)</math>) равен <math>1</math>. Если бы существовал <math>r</math>-аппроксимирующий алгоритм <math>\mathcal{A} </math> с <math>r < 2</math>, то <math>\mathcal{A}(G, 1, k, c)</math> находил бы доминирующее множество с точно таким же фактором аппроксимации, что невозможно.<!-- Добавить ссылку на статью с доминирующими множествами, где доказано, что это невозможно для r < 2 -->

== См. также ==
* [[Задача о размещении объектов|Задача о размещении объектов с минимизацией суммы расстояний]] (она же «Задача о 1-медиане») с {{не переведено 5|Медиана множества очек|медианой множества точек||geometric median}} в качестве частного случая
* [[Задача о размещении объектов|Задача о максиминном размещении объектов]] (как можно дальше, размещение вредных объектов)
* [[Задача о размещении объектов|Задача о k-центре]]
* [[K-medians|Задача о k-медиане]]

== Примечания ==
{{примечания|2}}

== Литература ==
{{refbegin|colwidth=30em}}
* {{статья
|автор=Nimrod Megiddo
|ref=Megiddo
|заглавие=The weighted Euclidean 1-center problem
|издание=Mathematics of Operations Research
|том=8
|выпуск=4
|страницы=498–504
|издательство=Institute for Operations Research and the Management Sciences
|место=Hanover
|date=November 1983
|url=http://theory.stanford.edu/~megiddo/pdf/weight1.pdf
|doi=10.1287/moor.8.4.498
}}
* {{статья
|автор=Abdelaziz Foul
|ref=Foul
|заглавие=A 1-center problem on the plane with uniformly distributed demand points
|издание=Operations Research Letters
|том=34
|выпуск=3
|страницы=264–268
|издательство=Elsevier
|год=2006
|url=http://www.sciencedirect.com/science/article/pii/S016763770500060X
|doi=10.1016/j.orl.2005.04.011
}}
* {{статья
|автор=R. Chandrasekaran
|ref=Chandrasekaran
|заглавие=The weighted euclidean 1-center problem
|издание=Operations Research Letters
|том=1
|выпуск=3
|страницы=111–112
|издательство=Elsevier
|год=July 1982
 |url=http://www.sciencedirect.com/science/article/pii/0167637782900098
 |doi=10.1016/0167-6377(82)90009-8
}}
* {{статья
|автор=M. Colebrook, S. Alonso Gutiérrez, J. Sicilia
|ref=Colebrook, Gutiérrez, Sicilia
|заглавие=A New Algorithm for the Undesirable 1-Center Problem on Networks
|ссылка=https://archive.org/details/sim_journal-of-the-operational-research-society_2002-12_53_12/page/1357
|издание=[[Journal of the Operational Research Society]]
|том=53
|выпуск=12
|страницы=1357–1366
|издательство=Palgrave Macmillan Journals
|год=2002
|jstor=822725
|doi=10.1057/palgrave.jors.2601468
}}
* {{статья
|автор=Rainer E. Burkard, Helidon Dollani
|ref=Burkard, Dollani
|заглавие=A Note on the Robust 1-Center Problem on Trees
|издание=Annals of Operations Research
|том=110
|выпуск=1-4
|страницы=69–82
|издательство=Kluwer Academic Publishers
|год=2002
|issn=1572-9338
|doi=10.1023/A:1020711416254
}}
{{refend}}
[[Категория:Комбинаторная оптимизация]]
[[Категория:Исследование операций]]
{{rq|checktranslate|style}}