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

Question

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

Версия 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), размер клики, которую нужно найти. к

выход:Истина, если клика существует, в противном случае ложь.

Алгоритм:

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

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

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

Answer 1

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

• Вам нужно рассматривать только 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.

Answer 2

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

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

Answer 3

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

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

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

Answer 4

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

Answer 5

Удивительно, что ввод информации в виде вопроса покажет вам то, что вы только что написали.Эта строка:

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 — это просто массив каждой отдельной вершины без учета смежности.