k-центр: самая дальняя точка, гарантия 2 и почему лучше нельзя

Если ты докажешь гарантию 2 для выбора самой дальней точки, предъявишь по её ответу нижнюю границу оптимума и объяснишь, почему множитель меньше двух означал бы P = NP, листай до «Теперь сам».

Как думаешь, куда ставить второй склад

Двенадцать магазинов на карте, три склада. Цель - чтобы худшая доставка была как можно короче: важен самый дальний магазин, а не средний. Первый склад поставили у магазина в левом нижнем углу.

Ответь себе до чтения: куда ставить второй? В «центр тяжести» оставшихся магазинов? Рядом с самой плотной группой? Правило этого урока делает то, что кажется грубым: ставит склад прямо у магазина, который сейчас хуже всех обслужен. И это правило не просто разумно - лучшего множителя, чем у него, не найдёт никто, пока не доказано P = NP.

На что это похоже

Пожарные части в новом районе. Первую построили. Где вторая? Там, куда первая доезжает дольше всего: именно этот дом сгорит первым. Третью - там, куда теперь дольше всего из обеих. Каждая новая часть закрывает самое больное место на текущий момент.

Почему это работает: если после всех построек остался дом в r минутах от ближайшей части, то каждая часть когда-то тоже была «самым больным местом» - то есть стояла не ближе r к предыдущим. Значит, на карте есть k + 1 точек, попарно далёких друг от друга. Никакая расстановка k частей не обслужит их все быстро: двум точкам придётся делить одну часть.

Механизм: самая дальняя точка и свидетели

Задача. Точки, расстояния с неравенством треугольника, число k. Выбрать k центров среди точек и минимизировать радиус - наибольшее расстояние от точки до ближайшего центра.

Жадное правило (Гонсалес, 1985). Первый центр - любая точка. Пока центров меньше k, новым центром становится точка, наиболее удалённая от уже выбранных.

Гарантия 2. Пусть жадность закончила с радиусом r, и точка x удалена от всех центров на r. Каждый центр в момент выбора был самой дальней точкой, и расстояния до центров только уменьшаются по мере добавления новых. Поэтому k центров и точка x - это k + 1 точек, попарно удалённых не меньше чем на r. Теперь возьми оптимальное решение с радиусом OPT. В нём k центров и k + 1 точек-свидетелей - две из них обслуживает один центр c. По неравенству треугольника расстояние между ними не больше d(·, c) + d(c, ·) ≤ 2 · OPT. Но оно не меньше r. Значит, r ≤ 2 · OPT.

Обрати внимание, что доказательство дало больше, чем гарантию: OPT ≥ r / 2 - и это число известно после работы алгоритма. Свидетели - готовый сертификат, который можно показать заказчику.

Почему не лучше двух. Доминирующее множество: набор вершин графа, такой, что каждая вершина либо в наборе, либо соседствует с вершиной из набора. Вопрос «есть ли доминирующее множество из k вершин» NP-полон. Сделаем из графа задачу о центрах: расстояние 1 между соседями, 2 между остальными (неравенство треугольника выполняется: 2 ≤ 1 + 1). Радиус любого набора из k < n центров - 1 или 2, и радиус 1 бывает ровно тогда, когда центры образуют доминирующее множество. Алгоритм с множителем α < 2 при оптимуме 1 обязан выдать радиус меньше 2, то есть 1, - и тем самым ответить на NP-полный вопрос. Такой приём - разрыв между ответами «да» и «нет», который приближение обязано различить, - подробно разобран в главе о пределах приближенияРазбирается в разделе 22, глава «Пределы приближения - PTAS, APX и почему дальше нельзя»: Разрыв: почему некоторые задачи нельзя приблизить.

Правило

Для k-центра с неравенством треугольника выбор каждый раз самой дальней точки даёт радиус не больше 2 · OPT: центры вместе с самой дальней оставшейся точкой - k + 1 точек, попарно удалённых хотя бы на радиус, и две из них в оптимуме делят центр. Множитель 2 неулучшаем при P ≠ NP.

Разбор: двенадцать магазинов, три склада

dalnie - жадный выбор, optimum_troek - перебор всех троек центров, svidetel - самая дальняя точка после выбора.

import math

def rasst(a, b):
    return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)

def do_centrov(tochki, centry):
    d = []
    for p in tochki:
        luchshee = math.inf
        for c in centry:
            luchshee = min(luchshee, rasst(p, tochki[c]))
        d.append(luchshee)
    return d

def dalnie(tochki, k):
    centry = [0]
    while len(centry) < k:
        d = do_centrov(tochki, centry)
        dalnij = 0
        for i in range(len(tochki)):
            if d[i] > d[dalnij]:
                dalnij = i
        centry.append(dalnij)
    return centry

def optimum_troek(tochki):
    n = len(tochki)
    luchshee = math.inf
    for a in range(n):
        for b in range(a + 1, n):
            for c in range(b + 1, n):
                r = max(do_centrov(tochki, [a, b, c]))
                luchshee = min(luchshee, r)
    return luchshee

tochki = [[1, 1], [2, 3], [3, 1], [8, 2], [9, 4], [10, 1],
          [4, 9], [5, 11], [6, 9], [14, 10], [2, 6], [12, 7]]
centry = dalnie(tochki, 3)
d = do_centrov(tochki, centry)
r = max(d)
svidetel = 0
for i in range(len(tochki)):
    if d[i] > d[svidetel]:
        svidetel = i
print(centry, round(r, 3), svidetel)
print(round(r / 2, 3), round(optimum_troek(tochki), 3))

[0, 9, 7] 9.0 5
4.5 5.831

Первый склад у магазина 0 (1, 1). Дальше всех от него магазин 9 (14, 10) - второй склад там. Третий - у магазина 7 (5, 11), верхней группы. Радиус 9: магазин 5 (10, 1) в девяти единицах от первого склада. Перебор всех 220 троек говорит, что лучше - 5,831, отношение 1,54.

Но главное - строка без перебора: 4.5. Магазины 0, 9, 7 и 5 попарно удалены не меньше чем на 9, а значит, любые три склада оставят какую-то пару из них на одном складе, и худшая доставка будет не меньше 4,5. Отчёт без перебора выглядит так: «наш план - 9, лучший возможный - не меньше 4,5». Точный оптимум 5,831 лежит внутри вилки.

Откуда потеря. Перебор находит оптимум со складами у магазинов 10 (2, 6), 5 (10, 1) и 9 (14, 10) - одинокая точка в углу есть и в нём. Проигрыш жадности - в первом складе: он стоит в углу (1, 1), и левым группам достаётся склад, а не середина между ними. Старт решает, а правило «самая дальняя» его не исправляет.

Разбор: где множитель 2 становится точным

Граф превращён в таблицу расстояний 1 и 2, как в доводе о невозможности. Два графа на шести вершинах, два центра.

def tablica(n, ryobra):
    d = []
    for i in range(n):
        d.append([2] * n)
        d[i][i] = 0
    for r in ryobra:
        d[r[0]][r[1]] = 1
        d[r[1]][r[0]] = 1
    return d

def radius(d, centry):
    hudshee = 0
    for v in range(len(d)):
        blizh = 2
        for c in centry:
            blizh = min(blizh, d[v][c])
        hudshee = max(hudshee, blizh)
    return hudshee

def dalnie(d, k):
    centry = [0]
    while len(centry) < k:
        dalnij = 0
        hud = -1
        for v in range(len(d)):
            blizh = 2
            for c in centry:
                blizh = min(blizh, d[v][c])
            if blizh > hud:
                hud = blizh
                dalnij = v
        centry.append(dalnij)
    return centry

def luchshie(d):
    n = len(d)
    best = [2, []]
    for a in range(n):
        for b in range(a + 1, n):
            if radius(d, [a, b]) < best[0]:
                best = [radius(d, [a, b]), [a, b]]
    return best

cikl = tablica(6, [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [5, 0]])
c = dalnie(cikl, 2)
print(c, radius(cikl, c), luchshie(cikl))
zvezdy = tablica(6, [[0, 1], [0, 2], [3, 4], [3, 5], [1, 2]])
c = dalnie(zvezdy, 2)
print(c, radius(zvezdy, c), luchshie(zvezdy))

[0, 2] 2 [1, [0, 3]]
[0, 3] 1 [1, [0, 3]]

Цикл из шести вершин: доминирующее множество {0, 3} есть (каждая вершина цикла рядом с 0 или 3), оптимум 1. Жадность выбрала 0, затем первую из самых дальних - вершину 2 (расстояние 2), и вершина 4 осталась на расстоянии 2: ответ ровно вдвое хуже оптимума. Во втором графе жадности повезло: самая дальняя от 0 вершина - 3, и она сразу закрыла вторую звезду.

Этот разбор и есть довод о невозможности в действии. В мире расстояний 1 и 2 у любого алгоритма ответ либо 1, либо 2 - промежуточного нет. Множитель 2 позволяет ошибаться ровно на эту ступеньку. Множитель 1,99 ошибаться уже не позволяет, а значит, обязан находить доминирующие множества.

Что ломается без этого

Нет неравенства треугольника. Шаг «две точки у одного центра, значит, между ними не больше 2 · OPT» держится на нём. Без него гарантии нет никакой - как у коммивояжёра.

Путают k-центр с k-средними. k-центр минимизирует худшее расстояние и чувствителен к выбросам: одна дальняя точка оттягивает на себя целый склад. Кластеризация k-средних минимизирует сумму квадратов расстояний - это другая цель, к выбросам она тоже чувствительна (квадрат большого расстояния велик), но выброс в ней сдвигает центр группы, а не обязательно забирает центр себе. Решают её локальным поискомРазбирается в разделе 22, глава «Локальный поиск, отжиг, эвристики»: Локальный поиск: сосед, улучшение и локальный оптимум Ллойда. Взять одну цель и мерить другой - частая ошибка постановки.

Ищут множитель 1,5 «посложнее». Если P ≠ NP, его нет - для этой задачи двойка не рубеж сегодняшних знаний, а предел.

Зачем это в работе

Размещение складов, пунктов выдачи, кешей CDN, станций скорой помощи - везде, где обещание звучит как «не дальше N минут до любого клиента». Самая дальняя точка - двадцать строк, O(n · k) вычислений расстояний, если хранить для каждой точки расстояние до ближайшего центра (программа урока для простоты пересчитывает его заново - O(n · k²)), и к ответу прилагается сертификат: k + 1 точек, которые попарно далеки, и «лучше половины нашего радиуса не сможет никто». Это ответ на вопрос «а может, другой подрядчик сделает лучше» - не словами, а точками на карте.

Похожая идея - стандартный способ рассадить начальные центры для k-средних: в k-means++ следующий центр выбирается случайно, с вероятностью, пропорциональной квадрату расстояния до ближайшего центра, так что дальние точки выбираются чаще. Разнесённые центры спасают от плохого начала.

Теперь сам

1. Точки на прямой: 0, 1, 2, 10, 11, 12, 20. Два центра, первый - в точке 0. Что выберет жадность, каков радиус, какую нижнюю границу дают свидетели и каков оптимум?
2. Почему в доказательстве свидетелей k + 1, а не k?
3. Кто-то утверждает, что нашёл быстрый алгоритм для k-центра с множителем 1,8 при любых расстояниях с неравенством треугольника. Что из этого следует?