Практическое применение раскраски графов

Привет, сегодня поговорим про применение раскраски графов, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое применение раскраски графов , настоятельно рекомендую прочитать все из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика..

Раскраска графов практически применяется (постановка задачи различных раскрасок здесь обсуждаться не будет) для:

Задача раскраски карт

минимальным числом красок

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

Теорема. Для оптимальной раскраски планарных графов достаточно четырех цветов. (1977, K. Appel, W. Haken, J. Koch) Решение путем сведения к задаче о кратчайшем покрытии. Данная задача сводится к поиску минимального числа максимальных пустых подграфов, которые в своей совокупности содержат все вершины заданного графа. Утверждение. Вершины, которые не принадлежат пустому подграфу, должны покрывать все ребра заданного графа (действительно, иначе обе вершины непокрытого ребра должны принадлежать этому подграфу, что невозможно). На основании приведенного утверждениия построение пустого подграфа можно свести к поиску подмножества вершин покрывающего все ребра заданного графа.

Составление расписаний

• расписания для образовательных учреждений (обзор — );
• расписания в спорте (обзор — );
• планирование встреч, собраний, интервью;
• расписания транспорта, в том числе — авиатранспорта ;
• расписания для коммунальных служб ;
• и прочие.

Вероятно, любому конкретному виду раскраски найдется применение в составлении расписаний.

Распределение регистров в микропроцессорах

См. : Распределение регистров

Заметную роль в быстродействии программ на компьютере играет время обращения микропроцессора к данным. А именно, процессор может обращаться (перечислим устройства в порядке убывания быстродействия и увеличения объема) к:

• регистрам процессора,
• кэшу,
• оперативной пямяти,
• прочим устройствам.

Далее, рассмотрим оптимизации программ, связанные с распределением данных в этих устройствах.

Стандартный подход Хайтина

Первыми важными работами, заложившими основы применения метода раскраски графов в распределении регистров, были , — последующие же не добавили ничего революционного, внимание в них было сконцентрировано на ускорении работы алгоритма, уменьшении памяти, новых эвристиках по определению стоимостиоткачки регистров (введем определение далее) и выбору регистров для откачки; обзор этих методов можно найти в .

Далее, рассмотрим способ, предложенный в .

Распределение регистров (англ. register allocation) микропроцессора обычно производится на этапе компиляции.

На вход процедуры распределения подается некий внутренний код (англ. IL, intermediate language, internal language), который рассчитан на виртуальную машину с неограниченным числом регистров — будем называть их виртуальными регистрами.

На выходе процедуры обращения к виртуальнам регистрам переводятся либо в обращения к реальным регистрам процессора, либо, если первого нельзя сделать по причине того, что все регистры уже заняты, — в обращения к оперативной памяти путем введения дополнительного кода. Этот код называют кодом откачки (англ. spillcode), а сам процесс — откачкой (spilling). Отметим, что при обращении к оперативной памяти так же иногда используются реальные регистры (для тех команд процессора, которые в качестве аргумента не могут принимать адрес в памяти).

Для примера, количество регистров общего назначения в большей части процессоров Intel, соответствующих архитектуре:

• IA-32 — 8 шт.,
• Intel 64[www 1] — 16 шт.

(Однако, даже не все из них могут быть использованы в нашей процедуре распределения регистров, поскольку уже могут быть заняты — но это уже тонкие вопросы реализации.) Оперативная память же можеть хранить очень большое число «откачанных» «регистров» — ограничения на ее объем рассматривать не будем.

Перед выполнением самой процедуры распределения, стоит сделать:

• Оптимизацию обращений к виртуальным регистрам.
• Определение того, является ли переменная в данный момент «значимой», для каждого места программы. «Значима» переменная тогда, когда далее в программе происходит чтение записанного в ней в данный момент значения.

Сам алгоритм распределения регистров состоит из следующих шагов:

• Построение графа — назовем его графом несовместимостей (англ. interfernce graph, conflict graph). Вершины данного графа — регистры. Вершины смежны, если соответствующие переменные «значимы» одновременно (по-другому: одна из переменных определена тогда, когда другая уже «значима»).
• «Склейка» переменных (subsumption, variable propagation): если до копирования одной переменной в другую, 2-я еще не «значима», а 1-я не «значима» после копирования — мы можем опустить ненужную операцию перемещения и стянуть («склеить») соответствующие данным переменным узлы графа.
• И, наконец, самый интересный нам этап: нахождение n-раскраски графа, где n - количество вышеупомянутых реальных переменных. Решением этой задачи раскраски и является оптимальное распределение регистров. Раскрашивать будем так:

1. Для вершин со степенью меньше n — назначим цвет, если можно.
2. Для нераскрашенных вершин (либо их степень не меньше n, либо — цвета закончились) — «откачиваем» переменные; удаляем эти вершины из графа. Соответствнно, у соседних им вершин степень уменьшается — и имеет смысл снова сделать шаг 1. (Не стоит забывать, что при откачке также возможно введение новой переменной — ее надо добавить в граф.)

Практика показывает, что алгоритм сходится довольно быстро.

Раскраска графа применяется во многих известных компиляторах, например:

• В GCC версии 4.4 появился новый распределитель регистров[www 2] — англ. integrated register allocator, который применяет т.н. раскраску «Хайтина-Бриггса».
• Раскраска «Хайтина-Бриггса» применяется и в (по крайней мере, его ранних версиях) компиляторе от Intel для архитектуры IA-64.[www 1]

Учет параллелизма на уровне команд

Процессоры, способные одновременно и независимо выполнять несколько команд, находят все более широкое применение; о них говорят, что те поддерживаютпараллелизм на уровне команд (англ. Об этом говорит сайт https://intellect.icu . Instruction-level parallelism, ILP). Назовем их ILP-процессорами. Класс ILP-процессоров включает в том числе процессоры с очень длинным командным словом - VLIW (Very Large Instruction Word, к числу которых относятся, в частности, многие модели цифровых процессоров обработки сигналов (ЦПОС). Самой известной коммерчески успешной реализацией концепции параллелизма на уровне отдельных инструкций является семейство микропроцессоров Itanium компании Intel. Также стоит отметить архитектуру E2K, разработанную российской компанией МЦСТ.

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

Распределение исполняемого кода по кэшу

Был предложен также и алгоритм для распределения часто используемых областей кода в кэше[10] — т. н. англ. cache line coloring.

Граф несовместимости здесь такой: вершины — некие «блоки» кода (можно, например, брать процедуры), ребра существуют тогда, когда из одного «блока» ввызывается другой. Как видно, мы концентрируемся на т. н. конфликтах первого поколения (first-generation cache conflicts) — между «блоком» и ее вызывающим/вызываемым. Но стоит отметить, что задача раскраски решается не алгоритмами общего назначения, а специальным эвристическим, который, к тому же, дает решение, которое удовлетворяет неким дополнительным условиям.

Достоинство этого метода — в том, что учитываются и размеры кэша, строки кэша, «блоков» кода, и ассоциативность кэша. Метод удачно комбинируется с другими оптимизациями и inline-функциями[10][11]. Надо отметить, что он может реализовываться оптимизатором — но не оптимизатором компилятора, а оптимизаторомкомпоновщика.

Распределение частот

(англ. Spectrum management, англ. frequency allocation)

Хорошей работой, классифицирующей такие задачи и систематически излагающей их решения, является [12].

Термин «распределение частот» объединяет разные типы задач, которые зачастую имеют разные цели и модели. Эти задачи включают в себя:

• Планировку моделей распределения (лицензирования, регулирования) радиочастот, максимизирующих использование всего радиоспектра.
• Учет того, что надо отвести диапазоны и для мобильной, наземной (англ. point-to-point) и спутниковой связи, радио- и телетрансляций.
• Алгоритмы, динамически распределяющие частоты одной конкретной сети между пользователями. Особо интересна тут сотовая связь, в области которой проделан очень большой объем исследований.

Общее между задачами — это то, что они все производят оптимальное распределение ограниченного набора ресурсов радиоспектра между пользователями, количество коих в современных условиях все время растет.

Два основных направления оптимизации тут:

• максимизация пропускной способности каналов при сохранении определенного минимального уровня интерференции (помех);
• минимизация интерференции для достижения фиксированной пропускной способности.

В ходе рассмотрения подходящих моделей, в [12] возникают задачи не намного сложнее T-раскраски (англ. T-coloring) мультиграфа, списочной T-раскраски (англ. set T-coloring).

Как пример работы над реальной сотовой сетью, результаты коей были далее применены оператором в своей практической деятельности — [13] (Проведено оператором E-Plus ( (англ.) en:E-Plus) — 3-м по величине в Германии (на 2010)).

Распараллеливание численных методов

Обобщенно представим задачу так: объекты — некие вычисления, между которыми надо разделить вычислительные ресурсы (процессоры, компьютеры…), могущие работать параллельно друг другу. Какие-то вычисления могут выполняться в параллели друг другу, какие-то — нет. Соответственно, вершинная раскраска графа несовместимости вычислений и представляет собой искомое распределение.

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

Разложение Холецкого для метода сопряженных градиентов с предопределением

Вау!! 😲 Ты еще не читал? Это зря!: en:Conjugate gradient method#The preconditioned conjugate gradient method

[14] Этот метод является одним из лучших итерационных методов для решения систем линейных алгебраических уравнений (СЛАУ) с большими, разреженными,симметричными, положительно определенными матрицами.

Метод Гаусса—Зейделя в применении к разреженным матрицам

Тоже итерационный метод решения СЛАУ.

Этот, в свою очередь, хорош, например, для расчета энергораспределительных электросетей: такие сети могут быть представлены графами, вершины которых — это потребители и источники электроэнергии, а ребра — линии электропередач; далее, строится СЛАУ, в матрице которой диагональным элементам соответствуют узлы вышеупомянутого графа, а ненулевым недиагональным — ребра.[15]

Также, метод может служить т.н. сглаживателем (англ. iterative smoother) для многосеточных методов решения задач методом конечных элементов. (англ. multigrid methods of finite element problems). Оптимизация метода Гаусса—Зейделя, используемого в сглаживании, с помощью т.н. англ. sparse tiling для такого случая его использования рассмотрена в [16].

Методы с использованием адаптивно уточняемой сетки

(англ. Adaptive mesh refinement)

[17] Они, в свою очередь , полезны в решении дифференциальных уравнений в частных производных (ДУЧП). Принцип уточнения здесь такой: в местах, где ожидается наибольшая локальная погрешность — где решение меняется быстрее всего, плотность сетки выбирается большей.

Метод координатной релаксации

(англ. Method of coordinate relaxation)

[18] Удачно применяется в нахождении экстремальных собственных значений очень больших разреженных симметричных матриц. Иногда таких больших, что их практичнее генерировать на лету, чем хранить в памяти. Такие задачи часто встают в квантовой механике.

Предопределение неполным LU-разложением

(Preconditioning by ILU, Incomplete LU-factorization)

Для решения СЛАУ с использованием подпространств Крылова.[19]

Вычисление производных

Вычисление матриц производных (якобианов и гессианов) в том случае, когда они разреженные, можно серьезно ускорить с помощью раскраски графов. Существует проект «Graph Coloring for Computer Derivatives», сайт — [www 3]. На сайте представлены публикации по теме, а также — программный пакет, в который оформили участники проекта свои достижения. Для введения в предмет можно посмотреть, одну из презентаций, относящихся к проекту, — [20].

Для простого случая, когда «уплотнение» производной ограничивается уменьшением количества столбцов, приведем алгоритм :

Вход: функция от вектора — Выход: производная — якобиан или гессиан 1. Исследуем структуру разреженности производной (саму производную вычислять не будем). 2. Составим матрицу уменьшения количества столбцов — англ. seed matrix; составим так, чтобы стало наименьшим. 3. Вычислим значения уплотненной ; вычислять будем не по этой формуле, а иным способом. Тут видно, что уменьшенное раньше — количество столбцов 4. И теперь, восстановим значения по (можно некими прямыми методами, можно — решением уравнений).

Место раскраски графа здесь — в вычислении . В простых случаях надо вычислять обычную вершинную (англ. distance-1); distance-2 раскраску (которая, в том числе сводится к distance-1 раскраске square graph); в более сложных, требуются небольшие дополнительные ограничения:

• звездная раскраска (star coloring) — вершинная distance-1, но с дополнительным ограничением: для любого пути из 4-х вершин используется не менее 3-х цветов;
• ациклическая раскраска (acyclic coloring) — вершинная distance-1 + каждый цикл использует не менее 3-х цветов.

В рамках вышеуказанного проекта были проведены вычисления для технических производственных задач:

• процесс хромотографического разделения (из области химии, химической технологии) посредством техники англ. Simulated Moving Bed;
• решение задачи оптимального энергетического потока (optimal power flow) (электроэнергетика).

Цифровые водяные знаки

Электронные водяные знаки наносятся на программное обеспечение с целью защиты
интеллектуальной собственности. Суть их состоит не в добавлении какого либо кода в программу, а в переводе подписи автора в множество дополнительных ограничений, которые добавляются в
оригинал ПО. Так как такая подпись основана на добавлении ограничений, то возможно некоторое ухудшение качества самого ПО. Поэтому необходимо держать баланс между степенью надежности защиты и степенью снижения качества ПО.

Раскраска графов применяется в так называемой constraint-based (основанной на ограничениях)
технологии нанесения электронного водяного знака. Исследования показали, что даже огромный
объем информации водяного знака может быть внедрен в граф, и при этом хроматическое число
графа, с водяным знаком будет отличаться не более, чем на 1. И даже практически все графы с
большим дополнительным объемом информации о водяном знаке могут быть раскрашены в
известное число цветов оригинального графа, без увеличения временных затрат.
Далее будут изложены три различных подхода к кодированию электронной подписи с помощью
алгоритмов раскраски графа.

Технология цифровых водяных знаков (англ. digital watermarking) позволяет вместе с данными (будь то медиафайлы, исполняемые файлы и прочие) передать некое скрытое сообщение («водяной знак», Watermark). Такое скрытое сообщение может быть применено в защите авторских прав для идентификации владельца данных.

Это важно, например, для установления источника их распространения нелегальным образом. Или же для подтверждения прав на данные , например — программное обеспечение систем на кристалле (system-on-chip).

Сообщение можно закодировать в том числе и в графе. Одну из таких техник предложили Qu и Potkonjak (поэтому ее иногда называют QP-алгоритмом) в [21].

Состоит она вот в чем: допустим, у нас есть граф G, раскраска которого используется в программе — причем, используется так, что допустимо поменять содержимое графа с небольшим увеличением его хроматического числа. Что важно, одним из таких примеров является граф несовместимости распределения регистров процессора, о котором говорилось выше, — а значит, мы сможем закодировать послание в программном продукте с помощью распределения регистров.

Извлечь его можно путем сравнения полученного графа с исходным; существуют и способы удостовериться в том, было ли некое сообщение закодировано в графе без использования исходного — подробнее извлечение описано, например, в [22].

Развитие и уточнение мыслей Qu и Potkonjak, попытки улучшения алгоритма происходит в работах [23], [24], [22].

Отметим, что в [23], [24] есть ссылки на программный пакет SandMark, в котором исполнены алгоритмы такого рода; доступен для скачивания на [www 4].

Прочие применения

• Классическая задача о раскраске карт: вершины — страны; ребра — общие границы. Такой граф , соответствующий карте, планарен, — а значит, по теореме о 4-х красках, всегда χ ≤ 4.
• Расчет сетей ОКС-7 (некое обобщение телефонных сетей); а именно, раскраска мультиграфа с некоторыми ограничениями нужна при маршрутизации пакетов с учетом равномерной нагрузки [25]. Вообще, РУДН и в том числе автор [25], работавший там, принимал активное участие в расчете междугородной сети ОКС-7 России[26] — что означает надежность источника.
• Кластерный анализ (разделение объектов на т. н. кластеры; в рамках кластера объекты имеют похожие свойства и/или кластеры имеют отчетливые различия)[27].
• Решение судоку: 9 цифр судоку — 9 цветов. Вершины графа несовместимости — клетки таблицы. Ребра между и проводим тогда и только тогда, когда:
  • , или,
  • , или,
  • и .
• Конструирование устройств, где провода, соединенные в одном узле, должны для удобства различения иметь разные цвета.

Вау!! 😲 Ты еще не читал? Это зря!

• раскраска графов , алгоритм раскраски графа , практическое применение раскраски графов ,

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

Ответы на вопросы для самопроверки пишите в комментариях, мы проверим, или же задавайте свой вопрос по данной теме.