От теоретических головоломок к практическим применениям
Делиться
Рита раскрашивает цветок с шестью лепестками, расположенными по кругу. Она хочет раскрасить каждый из шести лепестков ровно в один из следующих четырёх цветов: красный, оранжевый, жёлтый и синий. Никакие два соседних лепестка не могут быть одного цвета. Не обязательно использовать все четыре цвета. Сколько существует способов раскрасить лепестки цветка, удовлетворяя этим ограничениям? Это было основой задачи № 25 конкурса Кэли 2025 года, и это, как ни странно, является частным примером класса комбинаторных задач по науке о данных, связанных с понятием раскраски графов. В следующих разделах мы решим конкретную задачу Риты, получим её общие решения в открытой и замкнутой форме, а также рассмотрим некоторые интересные практические приложения в промышленности.
Примечание: Все рисунки и формулы в следующих разделах созданы автором данной статьи.
Теоретическая головоломка
Чтобы решить задачу Риты, давайте начнем с визуализации лепестков цветка в виде циклического графа, состоящего из 6 узлов, соединенных ребрами, как показано на рисунке 1:
На рисунке 2 показаны некоторые допустимые раскраски лепестков (также называемые правильными раскрасками):
Пусть P(n, k) — число способов раскрасить цикл из n узлов в k цветов так, чтобы никакие соседние узлы не имели одинаковый цвет.
Теперь рассмотрим, что произойдёт, если разбить цикл на цепочку из n узлов. Сколько существует способов (Pchain(n, k)) раскрасить цепочку из n узлов в k цветов так, чтобы ни один из соседних узлов не был одного цвета? Для начального (самого левого) узла цепочки мы можем выбрать k цветов. Но для каждого из последующих n – 1 узлов мы можем выбрать только k – 1 цвет, поскольку один из цветов уже был выбран предыдущим узлом. Это наглядно показано на рисунке 3 ниже:
Таким образом, мы имеем:
Однако обратите внимание, что в некоторых из этих допустимых раскрасок первый и последний узлы цепи будут иметь одинаковый цвет. Если вычесть эти случаи из Pchain(n, k), то получим P(n, k), что и требуется. Более того, обратите внимание, что вычитаемые случаи эквивалентны P(n – 1, k), то есть числу способов раскрасить цикл из n – 1 узлов в k цветов так, чтобы ни один из соседних узлов не имел одинакового цвета. Этот так называемый манёвр удаления-сжатия проиллюстрирован на рисунке 4 ниже:
На рисунке 5 ниже показаны базовые случаи для P(n, k) для заданного значения k:
Объединяя все эти идеи, получаем следующее рекуррентное соотношение первого порядка для положительных целых чисел n > 3 и k с базовыми случаями, описанными выше:
Теперь решение задачи Риты сводится к оценке рекуррентности P(n, k) для n = 6 и k = 4. Поскольку числа в этом случае относительно малы, мы можем выполнить оценку, расширив P(6, 4) следующим образом:
Используя выражение для базового случая P(3, k), обратите внимание, что:
Как результат:
Таким образом, у Риты есть ровно 732 способа раскрасить лепестки своих цветов, удовлетворяя заданным ограничениям.
Следующая функция Python (совместимая с версиями Python ≥ 3.9) реализует рекуррентность, позволяя нам быстро оценивать P(n, k) для больших входных значений:
def num_proper_colorings(n: int, k: int) -> int: «»» Итеративно вычисляет количество правильных раскрасок графа-цикла с n узлами и k цветами. Параметры: — n (int): Количество узлов в графе-цикле. — k (int): Количество доступных цветов. Возвращает: — int: Количество правильных раскрасок. «»» if n == 1: return k elif n == 2: return k * (k — 1) elif n == 3: return k * (k — 1) * (k — 2) # Инициализация базового случая num_proper_colorings(3, k) num_prev = k * (k — 1) * (k — 2) for i in range(4, n + 1): current = k * (k — 1)**(i — 1) — num_prev num_prev = current return num_prev
Раскраску графов также можно реализовать с помощью обратного поиска (backtracking) — полезного метода для исследования пространства решений различных типов задач науки о данных и постепенного построения потенциальных решений. Эта статья представляет собой наглядное введение в метод обратного поиска, а следующее видео демонстрирует, как обратный поиск может быть применен, в частности, к задачам раскраски графов:
Решение в закрытой форме
Итеративная функция Python, показанная выше, имеет временную сложность O(n) относительно числа узлов n в циклическом графе. Однако, если нам удастся найти аналитическое или аналитическое решение для P(n, k), мы сможем напрямую вычислить результат; соответствующая функция Python будет иметь временную сложность всего O(1), что обеспечит существенную экономию времени при значительном увеличении n. Временная сложность и преимущества аналитических решений подробно обсуждаются в этой статье, посвящённой алгоритмическому мышлению для специалистов по данным.
Чтобы найти упрощенное решение в замкнутой форме, давайте перепишем наше рекуррентное соотношение следующим образом:
В этом месте мы можем воспользоваться простым принципом линейной алгебры: общее решение линейного алгебраического уравнения f(x) = y равно сумме xh + xp общего решения xh его однородного аналога f(x) = 0 и частного решения xp уравнения f(x) = y. Чтобы напомнить себе, почему это работает, подставим xh + xp в f(x) = y, чтобы получить f(xh + xp) = y. Поскольку f(x) — линейная функция, то f(xh + xp) = f(xh) + f(xp) = y. Мы знаем, что f(xh) = 0 и f(xp) = y. Подстановкой получаем f(xh) + f(xp) = 0 + y = y. Уравнение y = y тривиально верно, что подтверждает, что xh + xp действительно является общим решением уравнения f(x) = y. Таким образом, наша задача теперь состоит в следующем:
- Найти общее решение xh однородного уравнения P(n, k) + P(n – 1, k) = 0
- Найдите частное решение xp для нашей рекуррентной формулы P(n, k) + P(n – 1, k) = k(k – 1)(n – 1)
- Объединяем xh и xp, чтобы получить общее замкнутое решение нашего рекуррентного уравнения.
Итак, начнем с решения следующего однородного уравнения:
Обратите внимание, что для простоты мы предположим:
Каждый член как будто отменяет предыдущий, поэтому он должен менять знак на каждом шаге, т.е. существует постоянный член C (который мы вскоре выведем), такой что:
Далее, поскольку правая часть исходного повторения кратна (k – 1)(n – 1), попробуем следующее частное решение P':
A — это постоянный член, который мы можем вывести, подставив P' в левую часть исходного повторения следующим образом:
Это означает, что A = 1, поэтому имеем:
Объединение частных и однородных решений дает нам:
Теперь мы можем использовать наш базовый случай для n = 3, чтобы вывести C:
Подстановка C обратно в объединенное решение дает нам следующее решение в замкнутой форме:
Мы можем убедиться, что это действительно дает нам правильное решение задачи конкурса Кэли:
Практические применения
Раскраска графа — фундаментальная задача теории графов, которая заключается в назначении меток (или «цветов») узлам графа таким образом, чтобы никакие два смежных узла не имели одинаковый цвет. По сути, раскраска графа пытается разбить граф на независимые множества, которые могут обрабатываться единообразно (т.е. всем элементам множества может быть назначен один и тот же цвет) без нарушения ограничений смежности. Такой подход к постановке задачи может применяться в широком спектре задач науки о данных, включая оптимизацию на основе ограничений и распределение ресурсов. Ниже мы рассмотрим некоторые из таких приложений.
Планирование и составление расписания
Раскрашивание графов может использоваться для решения задач планирования, где задачи или события должны быть организованы без конфликтов. Графы, используемые для моделирования таких сценариев, часто называются графами конфликтов.
Рассмотрим интуитивно понятный пример составления школьного расписания. Каждый класс можно представить узлом графа, а ребро соединяет два класса, если некоторые ученики посещают оба класса. Временные интервалы представлены цветами. Правильная раскраска графа, в которой соседние узлы не имеют одного цвета, гарантирует, что ни один ученик не столкнётся с необходимостью посещать два занятия одновременно. Случай с расписанием экзаменов представляет собой похожую проблему, поскольку экзамены должны быть распределены по временным интервалам таким образом, чтобы ни у одного ученика не возникало конфликтующих временных интервалов. Раскраска графа может быть использована для решения этой проблемы и минимизации общего количества необходимых временных интервалов.
Раскраска графов также может помочь в решении задач планирования с учётом ограничений в промышленных условиях. Например, сборка изделий на автомобильном заводе обычно включает в себя различные задачи, такие как покраска, подключение электроники, монтаж шасси и установка двигателей. Каждая задача требует специализированного инструмента, рабочих мест и квалифицированных рабочих, и могут существовать определённые ограничения на порядок выполнения задач. Покраска не должна производиться непосредственно перед подключением электроники, поскольку остаточные пары краски могут повредить чувствительную электронику. Установка двигателя и монтаж шасси могут потребовать использования одного и того же оборудования (например, подъёмников или стендов для регулировки), которое в дефиците и не может использоваться одновременно. Чтобы применить раскраску графов, мы можем смоделировать каждую задачу как узел в графе, где ребро соединяет два узла, если соответствующие задачи конфликтуют (т.е. задачи невозможно запланировать последовательно). Цвета представляют собой отдельные временные интервалы или этапы сборки. Правильная раскраска графов гарантирует, что конфликтующие задачи не будут запланированы друг за другом; это помогает оптимизировать производственный процесс, сократить время простоя и узкие места в ресурсах, а также предотвратить дорогостоящие ошибки.
Кластеризация и выбор признаков
В интеллектуальном анализе данных и машинном обучении (МО) алгоритмы кластеризации группируют точки данных на основе общих характеристик или взаимосвязей. Раскраска графов предлагает естественный подход к кластеризации, рассматривая данные как граф, где узлы представляют отдельные точки данных, а ребра указывают на некоторые взаимосвязи между соответствующими узлами (например, сходство, принадлежность к классу). Раскраска графов позволяет разбить данные на независимые множества (т. е. группы узлов, не связанных напрямую) для эффективного обнаружения кластеров; этот метод может быть особенно полезен в анализе социальных сетей, моделировании биологических данных и рекомендательных системах, где взаимосвязи между сущностями могут быть довольно сложными. Правильная раскраска графов помогает обеспечить внутреннюю связность каждого кластера, отличаясь при этом от других кластеров, обеспечивая четкую и интерпретируемую структуру для последующего анализа. Заинтересованные читатели могут ознакомиться с этой статьей и этой книгой, чтобы подробнее изучить теоретико-графовые представления данных для проектирования признаков.
Наконец, выбор признаков является важным фактором при построении эффективных и интерпретируемых моделей машинного обучения, особенно в контексте многомерных данных (например, как это наблюдается в таких областях, как геномика и финансы). Обучение модели на множестве признаков требует больших вычислительных затрат, а сильно коррелированные признаки, как правило, содержат избыточную информацию, что может привести к неэффективному обучению и переобучению. Раскраска графов предлагает элегантное решение: построить граф, где каждый узел представляет признак, а ребра соединяют пары сильно коррелированных признаков. Правильная раскраска такого графа гарантирует, что никаким двум сильно коррелированным признакам не будет присвоен один и тот же цвет, что позволяет выбрать один репрезентативный признак для каждого цвета. Этот метод снижает размерность, сохраняя при этом информационное разнообразие, что приводит к созданию более простых моделей, которые потенциально обладают лучшей обобщающей способностью.
Обертка
Раскраска графов, хотя и берёт начало в комбинаторной математике, имеет практическое значение, выходящее далеко за рамки теоретических головоломок. Взяв за основу задачу математического конкурса, связанную с лепестками цветов, мы вывели общие решения в открытой и замкнутой форме для правильной раскраски циклических графов и рассмотрели, как раскраска графов может быть применена к широкому спектру задач науки о данных. Ключ к такому практическому применению кроется в грамотной постановке задачи: если задача правильно представлена в виде графа – с тщательным учётом определения узлов, рёбер и ограничений раскраски – то подход к решению может стать очевидным. Как гласит цитата, часто (ошибочно) приписываемая Эйнштейну: «Если у вас есть час на решение задачи, [вам следует] потратить 55 минут на размышления о ней и 5 минут на размышления о её решениях». В конечном счёте, по мере развития науки о данных такие методы, как раскраска графов, вероятно, будут становиться всё более актуальными как в исследовательских, так и в прикладных задачах.
Источник: towardsdatascience.com
