Метрический k-центр

В теории графов , то метрика к -центру или метрическое расположение объекта задача является комбинаторной оптимизацией проблема изучается в теоретической информатике . Учитывая n городов с указанными расстояниями, нужно построить k складов в разных городах и минимизировать максимальное расстояние от города до склада. В теории графов это означает нахождение набора из k вершин, для которого наибольшее расстояние от любой точки до ближайшей вершины в k -множестве минимально. Вершины должны находиться в метрическом пространстве, обеспечивая полный граф , удовлетворяющийнеравенство треугольника .

Формальное определение [ править ]

Позвольте быть метрическим пространством, где является набором и является метрикой . Набор предоставляется вместе с параметром . Цель состоит в том, чтобы найти подмножество с таким, чтобы максимальное расстояние от точки до ближайшей точки было минимальным. Формально проблему можно определить следующим образом: для метрического пространства ( , d),${\ displaystyle (X, d)}$${\ displaystyle X}$${\ displaystyle d}$
${\ Displaystyle \ mathbf {V} \ substeq {\ mathcal {X}}}$${\ displaystyle k}$${\ Displaystyle {\ mathcal {C}} \ substeq \ mathbf {V}}$${\ displaystyle | {\ mathcal {C}} | = k}$${\ displaystyle \ mathbf {V}}$${\ displaystyle {\ mathcal {C}}}$
${\ Displaystyle {\ mathcal {X}}}$

• Вход: набор и параметр .${\ Displaystyle \ mathbf {V} \ substeq {\ mathcal {X}}}$${\ displaystyle k}$
• Выход: набор из точек.${\ displaystyle {\ mathcal {C}}}$${\ displaystyle k}$
• Цель: минимизировать затраты d (v, )${\ Displaystyle г ^ {\ mathcal {C}} (\ mathbf {V}) = {\ underset {v \ in V} {\ max}}}$${\ displaystyle {\ mathcal {C}}}$

То есть каждая точка в кластере находится на максимальном расстоянии от своего центра. ^[1]${\ Displaystyle г ^ {\ mathcal {C}} (V)}$

Задача кластеризации k-центров также может быть определена на полном неориентированном графе G  = ( V ,  E ) следующим образом:
дан полный неориентированный граф G  = ( V ,  E ) с расстояниями d ( v _i ,  v _j ) ∈  N, удовлетворяющими неравенства треугольника, найти подмножество C  ⊆  V с | C | =  k при минимизации:

${\ displaystyle \ max _ {v \ in V} \ min _ {c \ in C} d (v, c)}$

Вычислительная сложность [ править ]

В полном неориентированном графе G  = ( V ,  E ), если отсортировать ребра в порядке неубывания расстояний: d ( e ₁ ) ≤  d ( e ₂ ) ≤… ≤  d ( e _m ) и пусть G _i  = ( V,  E _i ), где E _i  = { e ₁ ,  e ₂ ,…,  e _i }. Задача k -центра эквивалентна нахождению наименьшего индекса i такого, что G _iимеет доминирующий набор размера не более k .^[2]

Хотя доминирующее множество является NP-полным , проблема k- центра остается NP-сложной . Это ясно, поскольку оптимальность данного допустимого решения для задачи k -центра может быть определена посредством сокращения доминирующего множества, только если мы знаем в первую очередь размер оптимального решения (т. Е. Наименьший индекс i такой, что G _i имеет доминирующее множество размера в большинстве к ), что именно трудно ядро из NP-трудной проблемы.

Приближения [ править ]

Простой жадный алгоритм [ править ]

Простой жадный алгоритм аппроксимации, который достигает коэффициента аппроксимации 2, строится с использованием обхода дальше всего за k итераций. Этот алгоритм просто выбирает точку, наиболее удаленную от текущего набора центров на каждой итерации, в качестве нового центра. Его можно описать следующим образом:${\ displaystyle {\ mathcal {C}}}$

• Выберите произвольную точку в${\ displaystyle {\ bar {c}} _ {1}}$${\displaystyle C_{1}}$
• Для каждой точки вычислить из${\displaystyle v\in \mathbf {V} }$${\displaystyle d_{1}[v]}$${\displaystyle {\bar {c}}_{1}}$
• Выберите точку с наибольшим расстоянием от .${\displaystyle {\bar {c}}_{2}}$${\displaystyle {\bar {c}}_{1}}$
• Добавьте его к набору центров и обозначьте этот расширенный набор центров как . Продолжайте до тех пор, пока не будут найдены k центров${\displaystyle C_{2}}$

Продолжительность [ править ]

• На i- ^ю итерацию выбора i- ^го центра требуется время.${\displaystyle {\mathcal {O}}(n)}$
• Всего k таких итераций.
• Таким образом, в целом алгоритм требует времени. ^[3]${\displaystyle {\mathcal {O}}(nk)}$

Доказательство коэффициента приближения [ править ]

Решение, полученное с помощью простого жадного алгоритма, является 2-приближением к оптимальному решению. Этот раздел посвящен доказательству этого коэффициента приближения.

Принимая во внимание множество п точек , принадлежащее к метрическому пространству ( , д), жадный K -CENTER алгоритма вычисляет множества K из K центров, таким образом, что K представляет собой 2-приближение к оптимальной к -Center кластеризации V .${\displaystyle \mathbf {V} \subseteq {\mathcal {X}}}$${\displaystyle {\mathcal {X}}}$

т.е. ^[1]${\displaystyle r^{\mathbf {K} }(\mathbf {V} )\leq 2r^{opt}(\mathbf {V} ,{\textit {k}})}$

Эта теорема может быть доказана с использованием следующих двух случаев:

Случай 1. Каждый кластер содержит ровно одну точку${\displaystyle {\mathcal {C}}_{opt}}$${\displaystyle \mathbf {K} }$

• Рассмотрим точку ${\displaystyle v\in \mathbf {V} }$
• Позвольте быть центром, которому он принадлежит в${\displaystyle {\bar {c}}}$${\displaystyle {\mathcal {C}}_{opt}}$
• Позвольте быть центром того, что находится в${\displaystyle {\bar {k}}}$${\displaystyle \mathbf {K} }$${\displaystyle \Pi ({\mathcal {C}}_{opt},{\bar {c}})}$
• ${\displaystyle d(v,{\bar {c}})=d(v,{\mathcal {C}}_{opt})\leq r^{opt}(\mathbf {V} ,k)}$
• Так же, ${\displaystyle d({\bar {k}},{\bar {c}})=d({\bar {k}},{\mathcal {C}}_{opt})\leq r^{opt}}$
• По неравенству треугольника: ${\displaystyle d(v,{\bar {k}})\leq d(v,{\bar {c}})+d({\bar {c}},{\bar {k}})\leq 2r^{opt}}$

Случай 2: Есть два центра и в том , что оба в , для некоторых (по принципу отверстия голубиного, это единственный другая возможность)${\displaystyle {\bar {k}}}$${\displaystyle {\bar {u}}}$${\displaystyle \mathbf {K} }$${\displaystyle \Pi ({\mathcal {C}}_{opt},{\bar {c}})}$${\displaystyle {\bar {c}}\in {\mathcal {C}}_{opt}}$

• Предположим, без ограничения общности, что было добавлено позже к центру, установленному жадным алгоритмом, скажем, на i- ^й итерации.${\displaystyle {\bar {u}}}$${\displaystyle \mathbf {K} }$
• Но поскольку жадный алгоритм всегда выбирает точку, наиболее удаленную от текущего набора центров, у нас есть это и,${\displaystyle {\bar {k}}\in {\mathcal {C}}_{i-1}}$

${\displaystyle {\begin{aligned}r^{\mathbf {K} }(\mathbf {V} )\leq r^{{\mathcal {C}}_{i-1}}(\mathbf {V} )&=d({\bar {u}},{\mathcal {C}}_{i-1})\\&\leq d({\bar {u}},{\bar {k}})\\&\leq d({\bar {u}},{\bar {c}})+d({\bar {c}},{\bar {k}})\\&\leq 2r^{opt}\end{aligned}}}$^[1]

Другой алгоритм двухфакторной аппроксимации [ править ]

Другой алгоритм с тем же коэффициентом приближения имеет преимущество в том , что к -центра задачи эквивалентно нахождению наименьшего индекса я такая , что G _я имеет доминирующее множество размера в большинстве к и вычисляет максимальное независимое множество в G _я , глядя для наименьшего индекса i , имеющего максимальное независимое множество размером не менее k . ^[4] Невозможно найти алгоритм аппроксимации с коэффициентом аппроксимации 2 - ε для любого ε> 0, если только P = NP. ^[5]Кроме того, расстояния всех ребер в G должны удовлетворять неравенству треугольника, если задача k- центра должна быть аппроксимирована в пределах любого постоянного множителя, если P = NP.^[6]

См. Также [ править ]

• Проблема коммивояжера
• Минимальный k-разрез
• Доминирующий набор
• Независимое множество (теория графов)
• Проблема с расположением объекта

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Хохбаум, Дорит С .; Шмойс, Дэвид Б. (1985), "Лучшая возможная эвристика для проблемы k-центра", Математика исследования операций , 10 , стр. 180–184