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

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

Формальное определение

Позволять ${ 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}$ точки.
• Цель: минимизировать стоимость ${ Displaystyle г ^ { mathcal {C}} ( mathbf {V}) = { underset {v in V} { max}}}$ d (v,${ Displaystyle { mathcal {C}}}$)

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

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

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

Вычислительная сложность

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

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

Приближения

Простой жадный алгоритм

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

• Выберите произвольную точку ${ 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}}$.
• Добавьте его к набору центров и обозначьте этот расширенный набор центров как ${ displaystyle C_ {2}}$. Продолжайте это до k центры найдены

Продолжительность

• Я^th итерация выбора i^th центр принимает ${ Displaystyle { mathcal {O}} (п)}$ время.
• Есть k такие итерации.
• Таким образом, в целом алгоритм принимает ${ Displaystyle { mathcal {O}} (нк)}$ время.^[3]

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

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

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

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

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

Случай 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}}$ (По принципу «голубятни», это единственная возможность)

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

${ displaystyle { begin {align} 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 {выровнен}}}$^[1]

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

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

Смотрите также

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

Рекомендации

дальнейшее чтение

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