Clique 문제 알고리즘 설계

StackOverflow https://stackoverflow.com/questions/509808

문제

내 알고리즘 클래스의 과제 중 하나는 Clique 문제를 해결하기 위해 철저한 검색 알고리즘을 설계하는 것입니다. 즉, 크기의 그래프가 주어졌습니다 N, 알고리즘은 크기의 완전한 하위 그래프가 있는지 확인해야합니다. 케이. 나는 답을 얻었다고 생각하지만 도울 수는 없지만 개선 될 수 있다고 생각합니다. 다음은 다음과 같습니다.

버전 1

입력: 배열 a [0, ...N-1], 크기 케이 찾을 수있는 서브 그래프의.

산출: subgraph가 존재하는 경우 true 그렇지 않으면 false입니다

연산 (파이썬 유사 의사 코드에서) :

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는 찾을 수있는 서브 그래프의 크기

산출: 크기 k의 모든 완전한 서브 그래프.

연산 (이번에는 기능적/파이썬 의사 코드에서) :

//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), 찾을 수있는 도둑의 크기 케이

산출: True Clique가 존재하는 경우, 그렇지 않으면 False

연산:

  1. 직교 제품 v케이.
  2. 결과의 각 튜플에 대해 각 정점이 서로 연결되어 있는지 테스트하십시오. 모두 연결된 경우 True를 반환하고 종료하십시오.
  3. 거짓을 반환하고 종료하십시오.

업데이트: 두 번째 버전이 추가되었습니다. 멋진 동적 프로그래밍을 추가하지는 않았지만 이것이 더 좋아지고 있다고 생각합니다 (내가 알고있는).

업데이트 2: 버전 2를 더 읽기 쉽게 만들기 위해 더 댓글과 문서를 추가했습니다. 이것은 아마도 내가 오늘 제에 켜는 버전 일 것입니다. 모두의 도움에 감사드립니다! 나는 하나 이상의 답변을 받아 들일 수 있기를 바랍니다. 그러나 나는 나를 가장 많이 도울 수있는 사람의 답을 받아 들였습니다. 내 교수의 생각을 알려 드리겠습니다.

도움이 되었습니까?

해결책

몇 가지 의견 :

  • 당신은 모든 k- 튜플 (n^k)이 아니라 정점의 n-choose-k 조합 만 고려하면됩니다.
  • connected(tuple) 제대로 보이지 않습니다. 재설정 할 필요가 없습니다 unconnected 루프 내부?
  • 다른 사람들이 제안한 바와 같이, 이것을 무차별 한 방법이 더 나은 방법이 있습니다. 다음과 같은 재귀 관계를 고려하십시오. a (k+1) -subgraph는 첫 번째 k 정점이 Clique를 형성하고 정점 (k+1)이 각각의 첫 번째 k 정점에 인접한 경우 클릭입니다. 이것을 두 방향으로 적용 할 수 있습니다.
    • 1- 클릭으로 시작하여 원하는 크기를 얻을 때까지 도둑을 점차 확장하십시오. 예를 들어, m이 현재 파벌에서 가장 큰 정점 인 경우, 정점 {m+1, m+2, ..., n-1}을 추가하여 하나의 정점이 더 큰 클릭을 얻으십시오. (이것은 트리 노드의 어린이가 현재의 파벌에서 가장 큰 정점보다 큰 정점이있는 깊이 우선 트리 횡단과 유사합니다.)
    • 원하는 크기의 하위 그래프로 시작하여 재귀 관계를 사용하여 파벌인지 확인하십시오. 설정 a 메모 화 길을 따라 결과를 저장하는 테이블.
  • (구현 제안) 인접 행렬 (0-1)을 사용하여 그래프의 가장자리를 나타냅니다.
  • (초기 가지 치기) k보다 적은 모든 정점을 버리십시오.

다른 팁

나는 한때 그래프에서 모든 최대 클리케를 찾기위한 알고리즘을 구현했는데, 이는 당신과 비슷한 문제입니다. 내가 한 방식은이 논문을 기반으로 한 것입니다. http://portal.acm.org/citation.cfm?doid=362342.362367 - 백로에서 많은 것을 바꾸었지만 가이드로 매우 유용한 역 추적 솔루션을 설명했습니다. 그래도 구독이 필요하지만, 나는 당신의 대학에서 하나를 사용할 수 있다고 가정합니다.

그래도 그 논문에 대한 한 가지 점은 나는 그들이 "이미 고려 된 세트"를 "세트"라는 이름을 지정해야한다고 생각한다는 것입니다. 그렇지 않으면 너무 혼란 스럽기 때문입니다.

알고리즘은 "각각의 k- 튜플에 대한, 그것이 파괴 인 경우, 진정한"반환 "은 확실히 작동합니다. 그러나, 그것은 무차별 인 힘이며, 아마도 알고리즘 과정이 검색하는 것이 아닐 것입니다. 대신 다음을 고려하십시오.

  1. 모든 정점은 1- 클릭입니다.
  2. 1- 클릭마다 1- 클릭의 정점에 연결되는 모든 정점은 2- 클릭에 기여합니다.
  3. 2- 클릭마다, 2- 클리크의 각 정점에 연결되는 모든 정점은 3- 클릭에 기여합니다.
  4. ...
  5. 모든 (k-1)-클리크에 대해, (k-1) clique의 각 정점에 연결되는 모든 정점은 k- 클릭에 기여합니다.

이 아이디어는 더 나은 접근 방식으로 이어질 수 있습니다.

아마도 시도해 볼 것입니다 동적 프로그래밍 기술.

질문으로 물건을 타이핑하는 것이 방금 작성된 내용에 대해 보여줄 것이 놀랍습니다. 이 라인 :

P = A x A x A  //Cartesian product

이것이어야합니다 :

p = a 케이 // Cartesian 제품

a^k 란 무엇을 의미합니까? 매트릭스 제품을 복용하고 있습니까? 그렇다면 인접 행렬 (N+1 요소의 배열이라고 말했음)입니까?

SetBuilder 표기법에서는 다음과 같은 것처럼 보일 것입니다.

p = {(x0, x1, ... xk) | x0 ∈ A 및 x1 ∈ A ... 및 xk ∈ A}

기본적으로 K Times의 직교 제품 일뿐입니다. 종이에, 나는 k가 A의 슈퍼 스크립트 인 것으로 썼다 (나는 이제 Markdown을 사용하여 그것을하는 방법을 알아 냈다).

또한 A는 인접성에 관계없이 각 개별 정점의 배열 일뿐입니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top