Разработка алгоритма задачи Клика

Question

Одним из заданий в моем классе алгоритмов является разработка исчерпывающего алгоритма поиска для решения проблемы клика. То есть, учитывая график размера n , алгоритм должен определить, существует ли полный подграф размера k . Я думаю, что получил ответ, но я не могу не думать, что он может быть улучшен. Вот что у меня есть:

Версия 1

input : График, представленный массивом A [0, ... n -1], размер k подграфа для поиска.

output : 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

input : Матрица смежности размером 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

К счастью, я поговорил со своим профессором, прежде чем отправлять задание. Когда я показал ему псевдокод, который я написал, он улыбнулся и сказал мне, что я выполнил way слишком много работы. Во-первых, мне не нужно было отправлять псевдокод; Я просто должен был продемонстрировать, что понял проблему. И во-вторых, он хотел , чтобы получить решение о грубой силе. То, что я сдал, выглядело примерно так:

вход : график G = (V, E), размер клики для поиска k

output : True, если клика существует, иначе false

Алгоритм

1. Найдите декартово произведение V ^k .
2. Для каждого кортежа в результате проверьте, связана ли каждая вершина с любой другой. Если все подключены, верните true и выйдите.
3. Вернуть false и выйти.

ОБНОВЛЕНИЕ : Добавлена ​​вторая версия. Я думаю, что это становится лучше, хотя я не добавлял никакого необычного динамического программирования (о котором я знаю).

ОБНОВЛЕНИЕ 2 : Добавлено еще несколько комментариев и документации, чтобы сделать версию 2 более читабельной. Это, вероятно, будет той версией, которую я представляю сегодня. Спасибо всем за помощь! Я хотел бы принять более одного ответа, но я принял ответ человека, который помог мне больше всего. Я дам вам, ребята, знать, что думает мой профессор.

Answer 1

Некоторые комментарии:

• Вам нужно учитывать только n-choose-k комбинаций вершин, а не все k-кортежи (n ^ k из них).
• connected(tuple) выглядит неправильно. Вам не нужно сбрасывать unconnected внутри цикла?
• Как и предполагали другие, существуют более эффективные способы грубого принуждения. Рассмотрим следующее рекурсивное отношение: A (k + 1) -подграф является кликой, если первые k вершин образуют клику и вершина (k + 1) смежна с каждой из первых k вершин. Вы можете применить это в двух направлениях:
  • Начните с 1-клики и постепенно расширяйте клику, пока не получите желаемый размер. Например, если m является самой большой вершиной в текущей клике, попробуйте добавить вершину {m + 1, m + 2, ..., n-1}, чтобы получить клику, которая на одну вершину больше. (Это похоже на обход дерева в глубину, где потомками узла дерева являются вершины, которые больше, чем самая большая вершина в текущей клике.)
  • Начните с подграфа нужного размера и проверьте, является ли он кликой, используя рекурсивное отношение. Настройте таблицу памятка для хранения результатов по пути.
• (предложение по реализации) Используйте матрицу смежности (0-1) для представления ребер в графе.
• (начальная обрезка) Удалите все вершины со степенью меньше k.

Answer 2

Алгоритм «для каждого k-го набора вершин, если это клика, а затем вернуть true» работает наверняка. Тем не менее, это грубая сила, которая, вероятно, не то, что ищет курс алгоритмов. Вместо этого рассмотрим следующее:

1. Каждая вершина является 1-кликой.
2. Для каждой 1-клики каждая вершина, которая соединяется с вершиной в 1-клике, вносит вклад в 2-клику.
3. Для каждой 2-клики каждая вершина, которая соединяется с каждой вершиной в 2-клике, вносит вклад в 3-клику.
4. ...
5. Для каждого (k-1) -клика каждая вершина, которая соединяется с каждой вершиной в (k-1) клике, вносит вклад в k-клику.

Эта идея может привести к лучшему подходу.

Answer 3

Я однажды реализовал алгоритм, чтобы найти все максимальные клики в графе, что аналогично вашей проблеме. То, как я это сделал, основывалось на этой статье: http://portal.acm.org/citation.cfm?doid=362342.362367 - в ней описывалось решение по возврату, которое я нашел очень полезным в качестве руководства, хотя я довольно сильно изменился по сравнению с этим документом. Для этого вам понадобится подписка, но я полагаю, что в вашем университете она будет доступна.

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

Answer 4

Возможно, попробуйте метод динамического программирования .

Answer 5

Удивительно, что если вы напишете вопрос в виде вопроса, вы увидите, что вы только что написали. Эта строка:

P = A x A x A  //Cartesian product

должно быть так:

P = A ^k // Декартово произведение

Что вы подразумеваете под A ^ k? Вы принимаете матричный продукт? Если да, является ли матрица смежности (вы сказали, что это массив из n + 1 элементов)?

В нотации setbuilder это будет выглядеть примерно так:

P = {(x0, x1, ... xk) | x0 ∈ A и x1 ∈ A ... и xk ∈ A}

В основном это декартово произведение А, взятое k раз. На бумаге я записал это как k как верхний индекс A (я только что понял, как это сделать, используя уценку).

Плюс, A - это просто массив каждой отдельной вершины без учета смежности.