Переформулировка: перестановка, подмножество, граф или интервалы

Если ты привык сначала называть объект задачи, а потом искать алгоритм, листай до «Теперь сам».

Как думаешь, это одна задача или две

Первая: «Разведи экзамены по дням так, чтобы ни у одного студента не было двух экзаменов в один день, и дней было как можно меньше». Вторая: «Разведи встречи по переговоркам так, чтобы пересекающиеся встречи были в разных комнатах, и комнат было как можно меньше».

Одна и та же это задача или нет? Ответь себе до чтения.

По форме - одна: «конфликтующие вещи - в разные слоты, слотов поменьше». Это раскраска графа: вершины - экзамены или встречи, ребро - конфликт, цвет - день или комната. Но конфликты у экзаменов произвольные (любые два экзамена могут делить студента), а у встреч - пересечения отрезков на оси времени. Из-за этого вторая задача решается точно за n log n, а для первой быстрого точного алгоритма не знает никто.

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

Библиотечный каталог. Книгу про «оптимизацию процесса А в нашей компании» ты там не найдёшь. Найдёшь, если спросишь библиотекаря про её тему в общих словах: «расписания», «графы», «строки». Переформулировка - это перевод твоей задачи на язык каталога, где у каждой полки есть название и десятки лет работы.

Механизм: слова задачи → объект → полка

Скиена в главе 1 даёт рабочий словарь: какое слово в задаче на какой объект указывает.

Переформулировка идёт в три шага. Назвать объект, который ищется (порядок модулей - перестановка). Назвать ограничения на него (модуль после всех, от кого зависит, - рёбра графа). Найти задачу с таким объектом и такими ограничениями (это топологическая сортировка из раздела 10).

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

Правило

Назови объект, который ищется (перестановка, подмножество, дерево, граф, точки, строка), и ограничения на него - и ищи алгоритм уже для этого объекта. Проверь, нет ли у твоих данных особой структуры (интервалы, дерево вместо графа, маленький параметр): она может превратить трудную задачу в лёгкую.

Разбор: порядок сборки модулей

«Собери пять модулей: db нужен log, auth нужен db, app нужны auth и ui, а ui нужен log. В каком порядке собирать?» Ищется порядок всех модулей - перестановка. Ограничение «после всех, от кого зависит» - это рёбра ориентированного графа. Значит, это топологическая сортировка: брать модуль, у которого не осталось несобранных зависимостей.

def poryadok_sborki(moduli, nuzhno):
    # nuzhno: [a, b] - модуль b собирается после a (ребро a -> b)
    vhodyashchih = {}
    sledom = {}
    for m in moduli:
        vhodyashchih[m] = 0
        sledom[m] = []
    for r in nuzhno:
        sledom[r[0]].append(r[1])
        vhodyashchih[r[1]] = vhodyashchih[r[1]] + 1
    gotovye = []
    for m in moduli:
        if vhodyashchih[m] == 0:
            gotovye.append(m)
    poryadok = []
    while len(gotovye) > 0:
        m = gotovye.pop(0)
        poryadok.append(m)
        for dalshe in sledom[m]:
            vhodyashchih[dalshe] = vhodyashchih[dalshe] - 1
            if vhodyashchih[dalshe] == 0:
                gotovye.append(dalshe)
    if len(poryadok) < len(moduli):
        ostalis = []
        for m in moduli:
            if vhodyashchih[m] > 0:
                ostalis.append(m)
        return "не собрать, застряли: " + str(ostalis)
    return poryadok

moduli = ["app", "auth", "db", "log", "ui"]
nuzhno = [["log", "db"], ["db", "auth"], ["auth", "app"],
          ["ui", "app"], ["log", "ui"]]
print(poryadok_sborki(moduli, nuzhno))
print(poryadok_sborki(moduli, nuzhno + [["app", "log"]]))

['log', 'db', 'ui', 'auth', 'app']
не собрать, застряли: ['app', 'auth', 'db', 'log', 'ui']

Переформулировка дала больше, чем порядок. Она сразу сказала, что делать, если порядка нет: в графе с циклом топологической сортировки не существует, и алгоритм сам это видит - модули, у которых остались несобранные зависимости, застревают. Во втором вызове log зависит от app напрямую, а app от log - через цепочку db, auth: застряли все пять, потому что все они либо в цикле, либо ждут кого-то из него. Ни одной строчки «обработки особого случая» не понадобилось - это свойство объекта, а не находка программиста.

Разбор: раскраска графа против раскраски интервалов

Теперь задачи из начала. Экзамены a1..a4 и b1..b4, конфликт - между ai и bj при i ≠ j (у каждой такой пары есть общий студент). В жизни рёбра получают из записей студентов: у каждого студента каждая пара его экзаменов - ребро, а повторы склеивает множество. Здесь граф задан сразу, чтобы был виден его вид. Встречи - отрезки времени, конфликт - пересечение. Обе задачи решим жадной раскраской: вершины по очереди, каждой - наименьший цвет, не занятый соседями (раздел 10), и сравним с оптимумом, найденным перебором с возвратом.

def sosedstvo(vershiny, rebra):
    sosedi = {}
    for v in vershiny:
        sosedi[v] = []
    for r in rebra:
        sosedi[r[0]].append(r[1])
        sosedi[r[1]].append(r[0])
    return sosedi

def zhadnaya(poryadok, sosedi):
    # каждой вершине по порядку - наименьший цвет, не занятый соседями;
    # возвращает само назначение: словарь «вершина -> цвет»
    cvet = {}
    for v in poryadok:
        zanyato = set()
        for u in sosedi[v]:
            if u in cvet:
                zanyato.add(cvet[u])
        c = 0
        while c in zanyato:
            c = c + 1
        cvet[v] = c
    return cvet

def chislo_cvetov(cvet):
    # Предусловие: хотя бы одна вершина
    return max(cvet.values()) + 1

def stavit(i, vershiny, sosedi, cvet, k):
    # перебор с возвратом: красим вершины по одной всеми k цветами
    if i == len(vershiny):
        return True
    v = vershiny[i]
    for c in range(k):
        svoboden = True
        for u in sosedi[v]:
            if cvet.get(u, -1) == c:
                svoboden = False
        if svoboden:
            cvet[v] = c
            if stavit(i + 1, vershiny, sosedi, cvet, k):
                return True
            cvet.pop(v)
    return False

def optimum(vershiny, sosedi):
    # Предусловие: хотя бы одна вершина (для пустого входа ответ 0)
    k = 1
    while not stavit(0, vershiny, sosedi, {}, k):
        k = k + 1
    return k

# экзамены a1..a4 и b1..b4: ai конфликтует с bj при i != j
vershiny = ["a1", "b1", "a2", "b2", "a3", "b3", "a4", "b4"]
rebra = []
for i in range(1, 5):
    for j in range(1, 5):
        if i != j:
            rebra.append(["a" + str(i), "b" + str(j)])
sosedi = sosedstvo(vershiny, rebra)
print("графа: жадно по порядку",
      chislo_cvetov(zhadnaya(vershiny, sosedi)),
      "| жадно, сначала все a",
      chislo_cvetov(zhadnaya(sorted(vershiny), sosedi)),
      "| оптимум", optimum(vershiny, sosedi))

# встречи [начало, конец) положительной длины: конфликт, если каждая
# начинается раньше, чем кончается другая; касание - не конфликт
vstrechi = [[0, 4], [1, 3], [2, 6], [5, 8], [7, 9], [3, 5]]
imena = []
for i in range(len(vstrechi)):
    imena.append(i)
konflikty = []
for i in range(len(vstrechi)):
    for j in range(i + 1, len(vstrechi)):
        a = vstrechi[i]
        b = vstrechi[j]
        if a[0] < b[1] and b[0] < a[1]:
            konflikty.append([i, j])
sosedi = sosedstvo(imena, konflikty)
def nachalo(i):
    return vstrechi[i][0]
po_nachalu = sorted(imena, key=nachalo)
komnaty = zhadnaya(po_nachalu, sosedi)
print("интервалов: жадно по началу", chislo_cvetov(komnaty),
      "| оптимум", optimum(imena, sosedi))
for i in imena:
    print("  встреча", vstrechi[i], "- комната", komnaty[i])

графа: жадно по порядку 4 | жадно, сначала все a 2 | оптимум 2
интервалов: жадно по началу 3 | оптимум 3
  встреча [0, 4] - комната 0
  встреча [1, 3] - комната 1
  встреча [2, 6] - комната 2
  встреча [5, 8] - комната 0
  встреча [7, 9] - комната 1
  встреча [3, 5] - комната 1

На графе экзаменов жадность зависит от порядка: a1, b1, a2, b2, … даёт 4 дня при оптимуме 2, и на таких графах разрыв растёт без предела. Почему: ai и bi между собой не конфликтуют, а с каждой прежней парой конфликтуют крест-накрест. К приходу ai у его соседей b1..b(i−1) уже заняты цвета 0..i−2, и он получает новый цвет i − 1; bi - тот же. При n парах жадность тратит n дней, а оптимум остаётся 2: все a в один день, все b в другой. Хорошего порядка заранее не знает никто - раскраска произвольного графа NP-трудна (раздел 10), и для экзаменов честный выбор - перебор на малых входах или эвристика.

У интервалов есть порядок, который работает всегда: по началу. Граф, в котором вершины - отрезки на прямой, а рёбра - пересечения, называется интервальным графом, и для него жадная раскраска по началу точна. Вот почему: когда встреча получает цвет c, цвета 0..c−1 заняты встречами, которые начались не позже (одновременное начало тоже считается) и ещё идут в момент её начала. Значит, в этот момент идут одновременно c + 1 встреч, и меньше c + 1 комнат не хватит никому. Ответ жадного алгоритма равен наибольшему числу одновременно идущих встреч - нижней границе для любого решения. Одни и те же слова «развести по слотам», а объект другой - и задача из NP-трудной стала решаемой за сортировку. Программа выше строит граф конфликтов попарно - только чтобы сравнить с перебором. Само расписание, кому какой день или комната, zhadnaya возвращает словарём - его последние строки вывода и отдают заказчику; число цветов из него считает chislo_cvetov. Быстрому способу граф не нужен: число комнат равно наибольшему числу одновременно идущих встреч, а его за n log n даёт заметание из прошлого урока. Само назначение тоже строится за n log n без графа: идём по встречам в порядке начала и держим кучу занятых комнат по времени освобождения (раздел 9). Если комната из вершины кучи свободна к началу встречи, встреча занимает её; иначе открывается новая комната.

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

Изобретение заново. Неделя на «свой алгоритм расстановки модулей» с ручной обработкой циклов, хотя это топологическая сортировка из учебника.

Перебор там, где хватило бы сортировки. Задачу о переговорках узнали как «раскраску графа», прочитали, что она NP-трудная, - и сдались, не заметив, что граф интервальный.

Модель потеряла главное. Комнаты бывают разной вместимости, а модель «интервалы и цвета» этого не знает. Если вместимость важна, задача уже другая.

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

Запрос «найди в документации, как решают нашу задачу» без переформулировки ничего не находит. После неё - находит: «topological sort», «interval partitioning», «graph coloring heuristics». Название объекта - это поисковый запрос в литературу, библиотеку и на форум, а как искать по нему - тема следующей главыРазбирается в разделе 26, глава «Как узнать задачу и найти готовое решение»: Сведение: решить новую задачу вызовом известной.

Теперь сам

1. «Выбрать в команду проекта людей так, чтобы покрыть все нужные навыки, и людей было как можно меньше». Какой это объект? Какое у задачи название?
2. «Найти, в каком порядке объехать 12 точек доставки со склада и вернуться на склад, чтобы путь был короче». Объект и название?
3. Встречи [1, 5), [2, 3), [4, 7), [6, 8). Сколько нужно комнат? Что вернёт жадная раскраска по началу?