1
그래프 (E, V)가 있습니다. 각각의 에지 (i, j)에 대해, 양수, 0 또는 음수 일 수있는 지불 P [i, j]가있다. 꼭지점을 클러스터로 나눕니다. 두 개의 이웃 꼭짓점 v1과 v2가 다른 클러스터에 속할 때마다 지불 P [v1, v2]를받습니다. 총 지불액을 극대화하는 방법은 무엇입니까? 이 문제는 NP 하드입니까?최적의 클러스터 화
A
답변
0
클러스터링을 수행하지 말고 컷을으로 지정하십시오.
가장자리 절단의 무게를 최대화하는 것을 일반적으로 "최대 절단"이라고합니다. 더 일반적인 문제는 최소 컷이며, mincut 문제로 표현 된 클러스터링 알고리즘이 있습니다. 절단은 또한 흐름 네트워크와 관련이 있습니다.
주석에서 언급했듯이 몇 가지 경계 조건을 지정해야합니다. 예를 들어 점을 두 개의 레이블로 잘라야하고 다른 레이블이있는 가장자리 만 잘라야합니다.
예, 이러한 종류의 절단은 일반적으로 NP 하드입니다.
당신은 [멀티 컷]을 찾고 있습니다 (http://www.cs.cmu.edu/~anupamg/adv-approx/lecture18.pdf). –
추가 제한 사항이없는 경우 (예 : 주어진 M의 개수에 따라 결과 클러스터 수), 가장자리에서 반복하고 긍정적 인 지불로 모든 것을 중단하게하는 것은 무엇입니까? 사실, 여전히 연속적인 그래프 (파티셔닝 없음)가 될 수 있지만, 문제가 제한을 두지 않으므로 단일 클러스터를 결과로 허용 할 수 있습니까? 그렇습니다. –
@Adrian Colomitchi 우리는 임의의 가장자리를 자르고 다른자를자를 수 없습니다. 다른 클러스터의 가장자리 만 잘라낼 수 있습니다. 우리가 A-B를 자르고 B-C를 자르지 않으면 우리도 A-C를 자른다. – user31264