Задача нахождения максимальной клики - Программирование, компьютеры и кибернетика курсовая работа
Главная
Программирование, компьютеры и кибернетика
Задача нахождения максимальной клики
Модификация алгоритма RPC таким образом, чтобы он не требовал входного параметра, но сохранил свою гибкость при решении задачи нахождения максимальной клики для разных графов. Метод ветвей и границ. Построение функции-классификатора. Листинг алгоритма.
посмотреть текст работы
скачать работу можно здесь
полная информация о работе
весь список подобных работ
Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
1. Метод ветвей и границ для решения ЗМК
5. Построение функции-классификатора
Приложение 1. Листинг алгоритма, основанного на методе ветвей и границ для решения ЗМК
Приложение 2. Листинг алгоритма RPC
Приложение 3. Предлагаемое изменение в алгоритме RPC
Задача нахождения максимальной клики в простом неориентированном графе G =( V , E ) является классической задачей теории графов. Кликой (или полным подграфом ) графа G называется такое подмножество его вершин, что любые две вершины подмножества соединены ребром. Клика, которая не содержится в клике большего размера, называется максимальной по включению . Задача нахождения максимальной клики (ЗМК) состоит в том, что для заданного графа G необходимо найти клику максимального размера (мощности).
Задача нахождения максимальной клики является NP-трудной и находит применение в самых разных областях. В частности, она возникает в (тут будет, где она возникает)
В настоящее время предложено множество алгоритмов для решения ЗМК, которые можно разделить на точные и приближённые. Точные алгоритмы находят гарантированно оптимальное решение, но при этом имеют экспоненциальную сложность, поэтому в некоторых случаях их использование потребует слишком много времени. Приближённые алгоритмы работают, как правило, быстрее, однако не могут гарантировать точности найденного решения. В рамках этой работы будут рассматриваться только точные алгоритмы.
Среди точных алгоритмов есть отдельный класс, основанный на методе ветвей и границ. Отличительной особенностью этого класса является использование в качестве границы количество цветов в раскраске графа. При этом алгоритмы этого класса отличаются лишь выбором эвристики для получения раскраски. В этом классе можно выделить алгоритм MCS [1], использующий в качестве границы количество цветов, полученное при использовании жадной раскраски с перекраской.
Идея комбинировать использование разных алгоритмов раскраски в методе ветвей и границ была использована в алгоритме RPC [2], использующем раскраску, полученную жадной раскраской с перекраской, а также повторное использование раскраски. Как показали эксперименты, этот алгоритм находит для большинства из тестовых графов оптимальное решение быстрее, чем прочие точные алгоритмы. Однако алгоритм RPC требует на вход параметр, и в зависимости от выбора этого параметра эффективность алгоритма сильно варьируется. В то же время, на данный момент не существует метода выбора оптимального значения параметра для конкретного графа.
Целью этой работы является модификация алгоритма RPC таким образом, чтобы он не требовал входного параметра, но при этом сохранил свою гибкость при решении ЗМК для разных графов.
1. Метод ветвей и границ для решения ЗМК
В рамках данной работы будут рассматриваться алгоритмы, основанные на методе ветвей и границ и использующие в качестве границы вершинную раскраску рассматриваемого графа. Вершинной раскраской графа G = ( V , E ) называется такая функция , что для любых двух вершин . Множество вершин, покрашенных в цвет i , будем обозначать . Следующее утверждение связывает кликовое число (число вершин в максимальной клике графа G ), с количеством цветов вершиной раскраски графа G .
Утверждение 1 . Если граф G = ( V , E ) может быть раскрашен в k цветов, то , причем в максимальную клику входит не более одной вершины из каждого цвета.
Утверждение 1 можно легко доказать, пользуясь методом от противного и определением вершинной раскраски. При этом задача нахождения раскраски с минимальным числом цветов является NP-трудной задачей. По этой причине на практике для нахождения вершинной раскраски графа часто пользуются приближенными алгоритмами.
Псевдокод примера алгоритма, использующего метод ветвей и границ, представлен в приложении 1.
Для хранения текущей рассматриваемой клики и текущей максимальной клики используются две глобальные переменные и соответственно.
Опираясь на утверждение 1, алгоритм использует проверку неравенства , как условие отсечения (приложение 1, строка 7). Другими словами, если условие выполняется, то все ветки рассматриваемой подзадачи отбрасываются, так как текущую клику невозможно увеличить. Иначе, вершина v с максимальным цветом добавляется в текущую рассматриваемую клику Q . После чего поиск макcимальной клики происходит среди вершин, соединённых с вершиной v (будем обозначать N ( v )) из множества вершин U (приложение 1, строка 11).
Алгоритм продолжает работу до тех пор, пока в множестве U не остаётся вершин. После этого в переменной Q m ax остаётся список вершин, входящих в максимальную клику.
Алгоритм RPC был предложен в [2]. Его псевдокод представлен в приложении 2. Этот алгоритм основан на методе ветвей и границ, а его отличительная особенность состоит в том, что он использует не один алгоритм раскраски для всех подзадач. Для некоторых подзадач используется алгоритм жадной раскраски с перекраской, для некоторых - повторное использование родительской раскраски. Также в алгоритме RPC исходный граф проходит предобработку, состоящую из двух шагов.
Первый шаг предобработки состоит в переименовании вершин. Для уменьшения размера дерева поиска в начале работы алгоритма используется упорядочение вершин (приложение 2, строка 55). В алгоритме RPC вершины упорядочиваются по принципу, который был предложен Матулой в [3]. Сначала во всем графе G ищется вершина v с наименьшей степенью. Далее вершина v становится вершиной с номером n . После чего вершина v удаляется из графа G и в полученном графе ищется вершина с наименьшей степенью. Найденная вершина перенумеруется в ( n-1 )-ую вершину и процедура повторяется.
Второй шаг предобработки - нахождение вершинной раскраски всего графа. Для этого используется жадный алгоритм раскраски (процедура GCH). В результате применения жадной раскраски получаем раскраску всех вершин графа , где - -ый цвет и .
Далее алгоритм RPC работает по принципу, представленному в главе 1. Существенное отличие заключается в получении раскраски подзадачи.
Алгоритм принимает на вход параметр - целое неотрицательное число. При алгоритм RPC совпадает с алгоритмом MCS ([2]), так как для всех подзадач для вычисления верхней границы используется жадная раскраска с перекрашиванием (метод GCH_R). Подробное описание этого алгоритма можно найти в [1]. При жадная раскраска с перекрашиванием будет применяться для некоторых подзадач, в то время как для других - повторное использование родительской раскраски (метод ROC).
Рис. 1 Повторное использование родительской раскраски
Рассмотрим применение метода ROC на следующем примере. Пусть , , и рассматриваемый подграф представлен на рис. 1 (слева). На рис. 1 для каждой вершины указан номер, а также цвет (в скобках). Первый шаг метода ROC состоит в повторном использовании родительской раскраски. Так как в первую очередь алгоритм RPC рассматривает вершину с наибольшим цветом то вершина 9 добавляется в текущую рассматриваемую клику Q . После чего рассматривается подграф, порожденный вершинами, смежными вершине 9. Для этого подграфа метод ROC не ищет новую раскраску, а повторно использует родительскую раскраску (приложение 2, строки 3-8). Результат повторного использования родительской раскраски представлен на рис. 1 (справа).
Рис. 2 Увеличение качества раскраски и сортировка цветов
Далее метод ROC пытается увеличить качество раскраски, то есть уменьшить количество используемых цветов (приложение 1, строки 10-27). В начале метод находит цвет, содержащий только одну вершину w . После чего вершину w пытаются перекрасить в другой цвет. В данном примере вершина 5, которая была покрашена в цвет 1 (рис. 2), может быть перекрашена в цвет 2. После этого преобразования не осталось вершин, окрашенных в первый цвет, поэтому его можно удалить и перенумеровать цвета. Результат применения увеличения качества раскраски представлен на рис. 2 (по центру).
Затем, для уменьшения размера дерева поиска, этот метод сортирует цвета по убыванию количества вершин, окрашенных в каждый цвет и перенумерует их.
Напомним, что алгоритм должен быть изменён таким образом, чтобы не требовать на вход параметр, но при этом так же использовать разные алгоритмы раскрасок. Одним из решений является автоматический выбор значения параметра для каждого входного графа с помощью методов машинного обучения. Однако этот метод неэффективен, т.к. значение параметра влияет исключительно на способ раскраски при вычислении границы в методе ветвей и границ. Соответственно, имеет смысл выбирать метод раскраски отдельно для каждого подграфа, образующегося при ветвлении. Также отметим, что эти подграфы часто сильно отличаются друг от друга по конфигурации (см. пример на рис. 1), поэтому решение выбирать метод раскраски разных подграфов независимо друг от друга выглядит обоснованным. Таким образом, алгоритм предлагается дополнить решением задачи классификации. Соответственно, при выборе метода раскраски функция-классификатор, принимающая на вход подграф, возвращает значение, соответствующее выбранной раскраске. Классические методы машинного обучения работают не с графами, а с числовыми векторами, поэтому на вход классификатору будет подаваться не сам граф, а вектор его признаков, которые будут определены ниже.
Отметим, что при таком подходе мы не ограничены только двумя методами раскраски, как в случае с числовым параметром. В данной работе к жадной раскраске с перекрашиванием и повторному использованию родительской раскраски добавлена жадная раскраска без перекрашивания.
Предлагаемые изменения представлены в приложении 3. Предполагается, что уже построена функция predict ( args ) , которая на основе параметров подзадачи возвращает номер класса, к которому принадлежит подзадача. Принадлежность подзадачи к тому или иному классу отражает, какой алгоритм раскраски лучше использовать для соответствующей подзадачи: класс 1 - жадная раскраска с перекраской, класс 2 - повторное использование родительской раскраски, класс 3 - жадная раскраска.
Подграфы, образующиеся в ходе работы алгоритма, обладают специфической конфигурацией, т.к. представляют из себя графы, из которых удалены одна или несколько вершин. Поэтому графы для обучающей выборки не генерируются классическими методами генерации графов. Вместо этого с помощью модели Эрдёша-Реньи генерируются графы, для которых запускается алгоритм RPC. Для генерации графов с помощью модели Эрдеша-Реньи необходимо задать два параметра n и p , где n - число вершин в генерируемом графе, а p - вероятность того, что любые две вершины и будут соединены ребром независимо от всех остальных пар вершин. В таблице 2 представлены значения параметров сгенерированных графов.
Получение обучающей выборки происходило следующим образом: сгенерированные графы подаются на вход алгоритма RPC. На третьем и четвёртом уровне дерева метода ветвей и границ образуются подзадачи, которые будут использованы в обучающей выборке. Для этих подзадач поочерёдно запускаются разные алгоритмы раскрасок и исследуется, сколько ветвей будет отсечено на следующем уровне. Затем элементы обучающей выборки классифицируются следующим образом:
1) Если один из методов раскраски отбрасывает все дочерние ветки, а остальные - нет, то выбирается тот метод, который отбрасывает все ветки.
2) Если ни один из методов не отбросил все ветки, выбирается тот метод, для которого количество дочерних веток подграфа минимально.
3) Если несколько методов отбрасывают все ветки или несколько методов породили минимальное количество дочерних веток, выбирается метод, наименее затратный с точки зрения вычислительной сложности. Отметим, что метод повторного использования родительской раскраски занимает линейное время, жадной раскраски - квадратичное, метод жадной раскраски с перекраской - в худшем случае кубическое.
Таким образом, для каждого сгенерированного графа будет получено множество элементов обучающей выборки, представляющих из себя вектор параметров подзадачи, и номер класса, к которому относится подзадача.
Были выбраны следующие параметры подзадачи:
1) Раскраска, использованная в родительском узле
2) Количество вершин в родительском узле
3) Количество цветов в родительском узле
5) Размер найденной максимальной клики
6) Разница между размером найденной максимальной клики и текущей клики
7) Количество вершин в рассматриваемом узле .
5. Построение функции-классификатора
Для решения задачи классификации был выбран метод деревьев решений, так этот метод легко анализируется и быстро работает. Отметим, что среди определяющих переменных есть дискретный неупорядоченный признак (Раскраска, использованная в родительском узле), принимающий три значения. Он был интерпретирован, как три бинарных признака. Подзадачи обучающей выборки распределились следующим образом:
Рис. 3. Распределение подзадач из обучающей выборки
Подзадачи, порождающие одинаковое количество ветвей в дочернем узле, в рамках нашей задачи относятся к классу, соответствующему повторному использованию, так как при одинаковом количестве ветвей в дочернем узле используется наименее затратная с точки зрения сложности раскраска.
Классификатор был построен с помощью пакета rpart среды R, и в дальнейшем интегрирован в код алгоритма RPC.
Отметим, что классификатор использовал только признаки 1, 5 и 7.
Предлагаемый алгоритм был протестирован на графах библиотеки DIMACS. Всего было рассмотрен 21 граф из этой библиотеки, для каждого из них решалась задача поиска максимальной клики с помощью предложенного алгоритма (модифицированный RPC), и алгоритмов RPC с параметрами 0, 1, 2 и 3. Время работы каждого из алгоритмов представлено в таблице 3.
Время работы рассматриваемых алгоритмов на графах из библиотеки DIMACS.
Отметим, что предложенный алгоритм в большинстве случаев работает быстрее алгоритма, использующего только один тип раскраски (RPC, ), но в среднем медленнее, чем алгоритм RPC с другими параметрами. Однако для практического использования необходим метод выбора оптимального значения параметра для конкретного графа. Однако на данный момент этого метода не существует. Таким образом, предложенный алгоритм более пригоден для практического использования, так как показывает приемлемые результаты, но при этом не требует на вход параметр.
В рамках представленной работы была предложена модификация алгоритма RPC, использующая машинное обучение вместо использования параметра. Модифицированный алгоритм был обучен при помощи сгенерированных по модели Эрдёша-Реньи графов и испытан на образцах из библиотеки DIMACS. Предложенный алгоритм показал себя достаточно эффективным, а, учитывая отсутствие входного параметра, ещё и пригодным для практического использования.
1. Tomita E., Seki, T. An efficient branch and bound algorithm for finding a maximum clique. Lecture Notes in Computer Science, 2731, 2003, 278-289
2. Nikolaev A., Batsyn M., San Segundo P. Reusing the same coloring in the child nodes of the search tree for the maximum clique problem. Lecture Notes in Computer Science, 8994, 2015, 275-280
3. Matula D.W., Marble G., Isaacson J.D. Graph Coloring Algorithms. Graph Theory and
Computing, Academic Press, New York, 1972, 109-122
Листинг алгоритма, основанного на методе ветвей и границ для решения ЗМК
17: maxColor номер максимального цвета в C
18: v вершина с номером цвета maxColor
1: function ROC ( v , C , maxColor , newC )
12: w вершина, принадлежащая цвету
29: Сортируем цвета по убыванию мощности и перенумеруем их
35: maxColor номер максимального цвета в C
36: v вершина с номером цвета maxColor
44: ROC( v , C , maxColor , newC )
55: Упорядочение и перенумерация вершин
Предлагаемые изменения в алгоритме RPC
Постановка и решение дискретных оптимизационных задач методом дискретного программирования и методом ветвей и границ на примере классической задачи коммивояжера. Этапы построения алгоритма ветвей и границ и его эффективность, построение дерева графов. курсовая работа [195,5 K], добавлен 08.11.2009
Задачи, решаемые методом динамического программирования. Основные этапы нахождения деревянного алгоритма решения задачи. Выполнение алгоритма Прима. Построение Эйлерового цикла. Решение задач средствами Excel. Алгоритм основной программы - Derevo. курсовая работа [586,3 K], добавлен 04.04.2015
Моделирование передвижения муравьев. Метод ветвей и границ, ближайшего соседа. Ограничения, накладываемые на агента в стандартной постановке задачи коммивояжера. Использование графа видимости в алгоритме муравья. Структура данных алгоритма муравья. дипломная работа [1,7 M], добавлен 07.02.2013
Концептуальная модель операции. Математическая постановка задачи. Описание метода ветвей и границ, прямого перебора. Проектирование сценария диалога. Описание структур данных. Ручная реализация решения задачи с помощью алгоритма Литла и перебора. курсовая работа [202,6 K], добавлен 14.12.2013
Этапы нахождения хроматического числа произвольного графа. Анализ примеров раскраски графа. Характеристика трудоемкости алгоритма раскраски вершин графа Мейниеля. Особенности графов, удовлетворяющих структуру графов Мейниеля, основные классы графов. курсовая работа [1,1 M], добавлен 26.06.2012
Описание методов нахождения и построения эйлеровых циклов в графах при раскрытии содержания цикломатических чисел и фундаментальных циклов. Изучение алгоритма решения задачи "Китайского почтальона" и разработка программы, решающей задачу на языке Си. курсовая работа [924,3 K], добавлен 09.01.2011
Сущность и особенности выполнения метода динамического программирования. Решение математической задачи, принцип оптимальности по затратам, ручной счёт и листинг программы. Применение метода ветвей и границ, его основные преимущества и недостатки. курсовая работа [38,9 K], добавлен 15.11.2009
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .
© 2000 — 2021
Задача нахождения максимальной клики курсовая работа. Программирование, компьютеры и кибернетика.
Сочинение 2022 20
Реферат На Тему Уход За Больным
Умный Транспорт Реферат
Реферат: Промышленность Дании
Курсовая Работа На Тему Рабство В Вавилонии
Реферат На Тему История Социальной Защиты России В Xx Веке
Реферат: История развития метрологии
Маркетинговой Курсовая
Реферат: Производство по пересмотру судебных актов Арбитражных судов
Демоверсия Контрольной Работы По Биологии 9
Реферат: Если бы я был руководителем Западно-Сибирского района
Дипломные Работы Брянск
Реферат по теме Взрослая болезнь кривизны
Эссе Деген Не
Курсовая работа по теме Комплексна характеристика Київської області
Эссе Любимая Работа
Лекция по теме Эффективность управления
Альберт Эйнштейн Реферат По Физике
Курсовая работа по теме Сравнительный анализ букварей
Реферат: Prostate Cancer Essay Research Paper The prostate
База данных MySQL - Программирование, компьютеры и кибернетика курсовая работа
Затраты и издержки - синонимы? - Бухгалтерский учет и аудит реферат
Энтеровирусная инфекция (ЭВИ) - Медицина презентация