Разработка алгоритма задачи клики
-
21-08-2019 - |
Вопрос
Одно из заданий моего курса по алгоритмам — разработать алгоритм исчерпывающего поиска для решения проблемы клики.То есть, учитывая график размера н, алгоритм должен определить, существует ли полный подграф размера к.Думаю, я получил ответ, но не могу не думать, что его можно улучшить.Вот что у меня есть:
Версия 1
вход:Граф, представленный массивом A[0,...н-1], размер к подграфа, который нужно найти.
выход:True, если подграф существует, False в противном случае
Алгоритм (в псевдокоде типа Python):
def clique(A, k):
P = A x A x A //Cartesian product
for tuple in P:
if connected(tuple):
return true
return false
def connected(tuple):
unconnected = tuple
for vertex in tuple:
for test_vertex in unconnected:
if vertex is linked to test_vertex:
remove test_vertex from unconnected
if unconnected is empty:
return true
else:
return false
Версия 2
вход:Матрица смежности размера n на n и k — размер подграфа, который необходимо найти.
выход:Все полные подграфы в A размера k.
Алгоритм (на этот раз в функциональном псевдокоде/Python):
//Base case: return all vertices in a list since each
//one is a 1-clique
def clique(A, 1):
S = new list
for i in range(0 to n-1):
add i to S
return S
//Get a tuple representing all the cliques where
//k = k - 1, then find any cliques for k
def clique(A,k):
C = clique(A, k-1)
S = new list
for tuple in C:
for i in range(0 to n-1):
//make sure the ith vertex is linked to each
//vertex in tuple
for j in tuple:
if A[i,j] != 1:
break
//This means that vertex i makes a clique
if j is the last element:
newtuple = (i | tuple) //make a new tuple with i added
add newtuple to S
//Return the list of k-cliques
return S
Есть ли у кого-нибудь какие-либо мысли, комментарии или предложения?Сюда входят ошибки, которые я мог пропустить, а также способы сделать это более читабельным (я не привык использовать много псевдокода).
Версия 3
К счастью, я поговорил со своим профессором, прежде чем сдать задание.Когда я показал ему написанный мной псевдокод, он улыбнулся и сказал, что я это сделал. способ слишком много работы.Во-первых, мне не нужно было отправлять псевдокод;Мне просто нужно было продемонстрировать, что я понимаю проблему.И во-вторых, он был желая решения грубой силы.То, что я сдал, выглядело примерно так:
вход:Граф G = (V,E), размер клики, которую нужно найти. к
выход:Истина, если клика существует, в противном случае ложь.
Алгоритм:
- Найдите декартово произведение Vк.
- Для каждого кортежа в результате проверьте, соединена ли каждая вершина друг с другом.Если все подключены, верните true и выйдите.
- Верните false и выйдите.
ОБНОВЛЯТЬ:Добавлена вторая версия.Я думаю, что ситуация становится лучше, хотя я не добавил никакого причудливого динамического программирования (о котором я знаю).
ОБНОВЛЕНИЕ 2:Добавлены дополнительные комментарии и документация, чтобы сделать версию 2 более читабельной.Вероятно, это будет та версия, которую я сдам сегодня.Спасибо всем за помощь!Мне хотелось бы принять более одного ответа, но я принял ответ человека, который помог мне больше всего.Ребята, я сообщу вам, что думает мой профессор.
Решение
Некоторые комментарии:
- Вам нужно рассматривать только n-выбрать-k комбинаций вершин, а не все k-кортежи (n^k из них).
connected(tuple)
выглядит не так.Разве вам не нужно сбрасыватьunconnected
внутри цикла?- Как предположили другие, есть лучшие способы грубого применения этого.Рассмотрим следующее рекурсивное отношение:(k+1)-подграф называется кликой, если первые k вершин образуют клику и вершина (k+1) смежна с каждой из первых k вершин.Вы можете применить это в двух направлениях:
- Начните с клика 1 и постепенно расширяйте клик, пока не получите желаемый размер.Например, если m — самая большая вершина в текущей клике, попробуйте добавить вершину {m+1, m+2, ..., n-1}, чтобы получить клику на одну вершину больше.(Это похоже на обход дерева в глубину, где потомками узла дерева являются вершины, большие, чем самая большая вершина в текущей клике.)
- Начните с подграфа желаемого размера и проверьте, является ли он кликой, используя рекурсивное отношение.Настройте мемоизация таблица для хранения результатов по пути.
- (предложение по реализации) Используйте матрицу смежности (0-1) для представления ребер в графе.
- (начальное сокращение) Отбросить все вершины со степенью меньше k.
Другие советы
Однажды я реализовал алгоритм поиска всех максимальных клик в графе, и это аналогичная ваша проблема.То, как я это сделал, было основано на этой статье: http://portal.acm.org/citation.cfm?doid=362342.362367 - там описывалось решение с возвратом, которое я нашел очень полезным в качестве руководства, хотя я многое изменил по сравнению с этим документом.Для этого вам понадобится подписка, но я предполагаю, что в вашем университете она есть.
Однако в этой статье есть одна вещь: я действительно думаю, что им следовало назвать «не установленное» «уже рассматриваемым набором», потому что в противном случае это слишком сбивает с толку.
Алгоритм «для каждого k-кортежа вершин, если это клика, вернуть true» работает наверняка.Однако это грубая сила, а это, вероятно, не то, что ищут в курсе алгоритмов.Вместо этого рассмотрите следующее:
- Каждая вершина является 1-кликой.
- Для каждой 1-клики каждая вершина, которая соединяется с вершиной в 1-клике, вносит вклад в 2-клику.
- Для каждой 2-клики каждая вершина, соединяющаяся с каждой вершиной 2-клики, вносит вклад в 3-клику.
- ...
- Для каждой (k-1)-клики каждая вершина, которая соединяется с каждой вершиной в (k-1)-клике, вносит вклад в k-клику.
Эта идея может привести к лучшему подходу.
Возможно, попробуйте метод динамического программирования.
Удивительно, что ввод информации в виде вопроса покажет вам то, что вы только что написали.Эта строка:
P = A x A x A //Cartesian product
должно быть это:
Р = А к //Декартово произведение
Что вы подразумеваете под А^к?Вы принимаете матричный продукт?Если да, то является ли A матрицей смежности (вы сказали, что это массив из n+1 элементов)?
В нотации setbuilder это будет выглядеть примерно так:
Р = {(х0, х1, ...XK) | x0 ∈ A и x1 ∈ A ...и xk ∈ A}
По сути, это просто декартово произведение A, взятое k раз.На бумаге я записал это как k, являющееся верхним индексом A (я только сейчас понял, как это сделать, используя уценку).
Плюс ко всему, A — это просто массив каждой отдельной вершины без учета смежности.