많은 관계가 복잡합니까?

나는 복잡한 데이터 구조를 가지고있는 프로젝트에서 어떻게 분석해야할지 모르겠다. 나는 솔루션을 만들려고 노력했지만 각 아이디어는 내가 100 %의 정확성을 갖지 못할 것이라는 느낌을 갖게한다. 이미 잘 알려지고 테스트 된 기존 방법이 있다면 그 것에 의존 할 수 있습니다.많은 관계가 복잡합니까?

각각 승진 그것이 다른 프로모션과 연결 할 수 있는지 여부의 자신의 명부이다가, 가게는 프로모션의 목록이 상상 : 그래서 여기

은 예입니다. 나는 서로 연결할 수있는 프로모션의 스택을 내놓을 필요가있다. 프로모션을 전혀 내놓지 않는다.

그래서 내가와 중복되는 프로모션 말해 목록을 얻을 것이다 프로모션, A, B, C, D.이 말할 수있는 프로모션 :

A -> B = S (스택)

A -> C = N (비 스택)

A -> D = 또한리스트와 D는리스트를 가질 것이다있을 것이다 S

B. 나는 N이 없다는 것이 쌓을 수 있다는 것을 의미 할 수는 없지만 S가 없다는 것은 쌓을 수 없다는 것을 의미한다고 생각할 수 있습니다. 1에서 무한 판촉까지 어디에서나있을 수 있습니다.

가능한 모든 프로모션 조합을 사용할 수 있도록해야합니다. 결국 모든 조합 (선호 고유 조합)의 배열이 필요하지만 모든 조합이 나열되어 있으면 고유하지 않은 것도 좋습니다. 이름으로 만 대답 할 수있는 문제의 이름을 아는 경우 내 질문을 편집 할 필요가 없습니다. 이름만으로도 Google에서 더 많이 검색 할 수 있습니다.

출처

2016-11-01 Samir

이것은 clique problem으로 공식화 될 수 있다고 생각합니다.

프로모션이 정점 인 그래프를 구성해야하며 프로모션을 쌓을 수있는 경우 두 정점 사이에 모서리가 있어야합니다. 가능한 승진은 완전한 서브 그래프 또는 클릭 (clique)입니다. 서브 그래프는 서브 그래프에서 각 정점이 서로 다른 정점에 연결되는 서브 그래프입니다.

이것은 NP 완성 문제이지만 시스템이 너무 크지 않으면 해결할 수 있어야합니다.

무차별 알고리즘은 아주 간단합니다. 두 가지 특수한 경우가 있습니다.

우선 정점 (단독 각 홍보) 두 정점은 파벌입니다 (이 프로모션의 목록) 나머지

k = 2 .. (number of vertices) 
    v in vertices 
    if (v.neighbors.size >= k) 
     s in distinct combination of k neighbors of v and v 
     if each vertex in s has a link to other vertices in s add s to the list

로에 대한 다음

연결

모든 가장자리 파벌이다 조합의 수가 기하 급수적으로 증가함에 따라 링크가 많으면 알고리즘이 느려집니다.

출처

2016-11-01 20:06:18

많은 관계가 복잡합니까?

답변

관련 문제