Русская Википедия:Цветовое кодирование

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Цветовое кодирование — Шаблон:Нп5, которая полезна для обнаружения Шаблон:Не переведено 5. Например, она может быть использована для обнаружения простого пути длины Шаблон:Mvar в заданном графе. Традиционный алгоритм цветового кодирования является вероятностным, но решение может быть Шаблон:Не переведено 5 без существенного увеличения времени работы.

Цветовое кодирование также применяется для обнаружения циклов заданной длины и в более общем случае, как в задаче поиска изоморфного подграфа (NP-полная задача), где оно даёт алгоритмы полиномиального времени, если искомый подграф имеет ограниченную древесную ширину.

Метод цветового кодирования предложили и анализировали в 1994 году. Авторы - Нога Алон, Рафаэль Юстер и Юрий ЦвикШаблон:SfnШаблон:Sfn.

Результаты

Следующие результаты могут быть получены методом цветового кодирования:

Метод

Чтобы решить задачу нахождения подграфа <math>H = (V_H, E_H)</math> в данном графе <math>G = (V, E)</math>, где Шаблон:Mvar может быть путём, циклом или любым графом с ограниченной древесной шириной, а <math>|V_H| = O(\log V)</math>, метод цветового кодирования начинает со случайной раскраски каждой вершины в Шаблон:Mvar с помощью <math>k = |V_H|</math> цветов, а потом пытается найти полноцветную копию Шаблон:Mvar в раскрашенном Шаблон:Mvar. Здесь под полноцветным графом понимается граф, в котором каждая вершина раскрашена в свой цвет. Метод работает путём повторения (1) случайной раскраски графа и (2) нахождения полноцветной копии целевого подграфа. В конечном счёте целевой подграф может быть найден, если процесс повторять достаточное число раз.

Предположим, что копия Шаблон:Mvar в Шаблон:Mvar становится полноцветной с некоторой ненулевой вероятностью Шаблон:Mvar. Отсюда следует, что при повторении случайной раскраски <math>\tfrac{1}{p}</math> раз эта копия однажды встретится. Заметим, что даже когда вероятность Шаблон:Mvar мала, известно, что при <math>|V_H| = O(\log V)</math> вероятность Шаблон:Mvar лишь полиномиально мала. Предположим, что существует алгоритм, который для данного графа Шаблон:Mvar и раскраски, которая отображает каждую вершину Шаблон:Mvar в один из Шаблон:Mvar цветов, находит копию полноцветной копии Шаблон:Mvar, если она существует, за некоторое время Шаблон:Math. Тогда ожидаемое время поиска копии Шаблон:Mvar в Шаблон:Mvar, если она существует, равно <math>O(\tfrac{r}{p})</math>.

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

Пример

В качестве примера возьмём поиск простого цикла длины Шаблон:Mvar в графе <math>G = (V, E)</math>.

При применении метода случайной раскраски каждый простой цикл имеет вероятность <math>k!/k^k > e^{-k}</math> стать полноцветным, поскольку имеется <math>k^k</math> способов выкрасить Шаблон:Mvar вершин цикла, среди которых встречается <math>k!</math> вариантов полноцветной раскраски. Тогда алгоритм (описанный ниже) может быть использован для поиска полноцветных циклов в случайно раскрашенном графе Шаблон:Mvar за время <math>O(V^\omega)</math>, где <math>\omega</math> является константой умножения матриц. Тогда требуется полное время <math>e^k\cdot O(V^\omega)</math> для нахождения простого цикла длины Шаблон:Mvar в Шаблон:Mvar.

Алгоритм поиска полноцветного цикла сначала находит все пары вершин в Шаблон:Mvar, соединённые простым путём длины Шаблон:Math, а потом проверяет, соединены ли две вершины в каждой паре. Если задана функция раскраски <math>c\colon V\to \{1, \dots, k\}</math> для графа Шаблон:Mvar, перенумеруем все разбиения множества цветов <math>\{1, \dots, k\}</math> на два подмножества <math>C_1, C_2</math> размера примерно <math>k/2</math> в каждом. Для каждого такого разбиения пусть <math>V_1</math> будет множеством вершинам, выкрашенных цветами из <math>C_1</math>, а <math>V_2</math> будет множеством вершин, выкрашенных цветами из <math>C_2</math>. Пусть <math>G_1</math> и <math>G_2</math> обозначают подграфы, порожденные <math>V_1</math> и <math>V_2</math> соответственно. Рекурсивно находим полноцветные пути длины <math>k/2 - 1</math> в <math>G_1</math> и <math>G_2</math>. Представим, что булевы матрицы <math>A_1</math> и <math>A_2</math> представляют связь каждой пары вершин в <math>G_1</math> и <math>G_2</math> полноцветным путём соответственно, и пусть Шаблон:Mvar будет матрицей, описывающей смежность вершин <math>V_1</math> и <math>V_2</math>, тогда булево произведение <math>A_1BA_2</math> даёт все пары вершин в Шаблон:Mvar, соединённые полноцветным путём длины Шаблон:Math. Объединение матриц, полученных на всех разбиениях множества цветов, даёт <math>t(k) \leqslant 2^k\cdot t(k/2)</math>, что приводит ко времени работы <math>2^{O(k)}\cdot V^\omega = O(V^\omega)</math>. Хотя этот алгоритм находит только конечные точки полноцветного пути, может быть использован другой алгоритм Алона и НаораШаблон:Sfn, который и находит, собственно, полноцветный путь.

Дерандомизация

Шаблон:Не переведено 5 цветового кодирования вовлекает перечисление возможных раскрашиваний графа Шаблон:Mvar, так что рандомизация раскраски Шаблон:Mvar больше не нужна. Чтобы можно было обнаружить целевой подграф Шаблон:Mvar в Шаблон:Mvar, перечисление должно включать, по меньшей мере, один случай, где Шаблон:Mvar полноцветен. Чтобы это получить, достаточно перечислить Шаблон:Mvar-совершенное семейство Шаблон:Mvar хеш-функций из <math>\{1, \dots, |V|\}</math> в Шаблон:Math. По определению, функция Шаблон:Mvar Шаблон:Mvar-совершенна, если для любого подмножества Шаблон:Mvar множества <math>\{1, \dots, |V|\}</math>, где <math>|S| = k</math>, существует хеш-функция Шаблон:Mvar из Шаблон:Mvar, такая что <math>h\colon S \to \{1, \dots, k\}</math> является Шаблон:Не переведено 5. Другими словами, должна существовать хеш-функци в Шаблон:Mvar, которая раскрашивает заданные Шаблон:Mvar вершин в Шаблон:Mvar различных цвета.

Имеется несколько подходов к построению такого Шаблон:Mvar-идеального семейства хеша:

  1. Лучшее явное построение предложили Мони Наор, Леонард Дж. Шульман и Аравинд СринивасанШаблон:Sfn, в котором можно получить семейство размера <math>e^k k^{O(\log k)} \log |V|</math>. Это построение не требует, чтобы целевой подграф содержался в исходной задаче нахождения подграфа.
  2. Другое явное построение предложили Джанетта П. Шмидт и Алан СигельШаблон:Sfn даёт семейство размера <math>2^{O(k)}\log^2 |V|</math>.
  3. Ещё одно построение, которое появилось в исходной статье Нога Алона и др.Шаблон:Sfn, можно получить сначала путём построения Шаблон:Mvar-совершенного семейства, которое отображает <math>\{1, \dots, |V|\}</math> в <math>\{1, \dots, k^2\}</math>, с построением другого Шаблон:Mvar-совершенного семейства, которое отображает <math>\{1, \dots, k^2\}</math> в <math>\{1, \dots, k\}</math>. На первом шаге можно построить такое семейство с Шаблон:Math случайными битами, которое почти Шаблон:Math-независимоШаблон:SfnШаблон:Sfn, и пространство, необходимое для генерации этих случайных бит, может быть ограничено величиной <math>k^{O(1)}\log |V|</math>. На втором шаге, как показали Джанетта П. Шмидт и Алан Зигель Шаблон:Sfn, размер такого Шаблон:Mvar-идеального семейства может быть <math>2^{O(k)}</math>. Следовательно, составляя Шаблон:Mvar-идеальные семейства из обоих шагов, можно получить Шаблон:Mvar-совершенное семейство размера <math>2^{O(k)}\log |V|</math>, которое отображает из <math>\{1, \dots, |V|\}</math> в <math>\{1, \dots, k\}</math>.

В случае дерандомизации идеального раскрашивания, когда каждая вершина подграфа раскрашивается последовательно, требуется Шаблон:Mvar-идеальное семейство хэш-функций из <math>\{1, \dots, |V|\}</math> в <math>\{1, \dots,k!\}</math>. Достаточное Шаблон:Mvar-совершенное семейство, отображающее из <math>\{1, \dots, |V|\}</math> в <math>\{1, \dots, k^k\}</math>, может быть построено способом, подобным подходу 3 выше (первый шаг). В частности, это делается использованием <math>nk\log k</math> случайных бит, которые почти <math>k\log k</math> независимы, а размер получающегося Шаблон:Mvar-совершенного семейства будет равен <math>k^{O(k)}\log |V|</math>.

Дерандомизация метода цветового кодирования может быть легко распараллелена, что приводит к эффективным алгоритмам в классе NC.

Приложения

Недавно цветовое кодирование привлекло внимание ученых из области биоинформатики. Пример — определение сигнальных путей в сетях белок-белкового взаимодействия (ББВ). Другим примером является обнаружение и подсчёт числа Шаблон:Не переведено 5 в сетях ББВ. При изучении как сигнальных путей, так и Шаблон:Не переведено 5 позволяет более глубокое понимание похожести разницы многих биологических функций, процессов и структур в организмах.

Вследствие большого числа генетических данных, которые можно собрать, поиск путей или мотивов может занимать продолжительное время. Однако, используя метод цветового кодирования, мотивы и сигнальные пути с <math>k=O(\log n)</math> вершинами в сети Шаблон:Mvar с Шаблон:Mvar вершинами могут быть найдены очень эффективно за полиномиальное время. Это позволяет исследовать более сложные или больших размеров структуры в сетях ББВ.

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend

Литература для дальнейшего чтения

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ См. Алгоритм Копперсмита — Винограда. Экспонента <math>\omega</math> умножения матриц — это степень <math>\omega</math> размера матрицы <math>n</math> асимптотической сложности алгоритма умножения матриц.
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Цветовое_кодирование&oldid=11278740