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

Metric k-center

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

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

Позволять быть метрическое пространство куда это набор и это метрика
Множество , предоставляется вместе с параметром . Цель - найти подмножество с такое, что максимальное расстояние до точки в к ближайшей точке в сводится к минимуму. Формально проблему можно определить следующим образом:
Для метрического пространства (, г),

  • Сырьё: набор , а параметр .
  • Выход: набор из точки.
  • Цель: минимизировать стоимость d (v,)

То есть каждая точка в кластере находится на расстоянии не более от соответствующего центра. [1]

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

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

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

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

Приближения

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

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

  • Выберите произвольную точку в
  • За каждую точку вычислить из
  • Выберите точку с наибольшим удалением от .
  • Добавьте его к набору центров и обозначьте этот расширенный набор центров как . Продолжайте это до k центры найдены

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

  • Яth итерация выбора ith центр принимает время.
  • Есть k такие итерации.
  • Таким образом, в целом алгоритм принимает время.[3]

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

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

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

т.е. [1]

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

Случай 1. Каждый кластер содержит ровно одну точку

  • Рассмотрим точку
  • Позволять быть центром, которому он принадлежит в
  • Позволять быть центром это в
  • По аналогии,
  • По неравенству треугольника:


Случай 2: Есть два центра и из которые оба в , для некоторых (По принципу «голубятни», это единственная возможность)

  • Без ограничения общности предположим, что был добавлен позже в центральный набор жадным алгоритмом, скажем в яth итерация.
  • Но поскольку жадный алгоритм всегда выбирает точку, наиболее удаленную от текущего набора центров, мы имеем и,

[1]

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

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

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

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

  1. ^ а б c Хар-пелед, Сариэль (2011). Алгоритмы геометрической аппроксимации. Бостон, Массачусетс, США: Американское математическое общество. ISBN 0821849115.
  2. ^ Вазирани, Виджай В. (2003), Алгоритмы аппроксимации, Берлин: Springer, стр. 47–48, ISBN 3-540-65367-8
  3. ^ Гонсалес, Теофило Ф. (1985), "Кластеризация для минимизации максимального межкластерного расстояния", Теоретическая информатика, 38, Elsevier Science B.V., стр. 293–306, Дои:10.1016/0304-3975(85)90224-5
  4. ^ Хохбаум, Дорит С.; Шмойс, Дэвид Б. (1986), «Единый подход к алгоритмам аппроксимации для проблем узких мест», Журнал ACM, 33, стр. 533–550, ISSN 0004-5411
  5. ^ Хохбаум, Дорит С. (1997), Аппроксимационные алгоритмы для NP-сложных задач, Бостон: PWS Publishing Company, стр. 346–398, ISBN 0-534-94968-1
  6. ^ Крещенци, Пьерлуиджи; Канн, Вигго; Халльдорссон, Магнус; Карпинский, Марек; Woeginger, Герхард (2000), «Минимальный k-центр», Сборник задач оптимизации NP

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