Set-cover 문제에 대한 최소 크기 세트 표지를 찾는 알고리즘

Question

Set Covering 문제에서 | U | = n이되도록 우주 U가 주어지고 S1, ..., Sk가 세트 커버는 S1, ......, Sk의 집합체 중 하나 인 집합체 C이며, 그 집합체는 전체 우주 U입니다.

나는 최소 수를 발견 할 수있는 알고리즘을 고안하려고합니다. 세트 커버를위한 욕심 많은 알고리즘이 때때로 더 많은 세트를 찾는다는 것을 보여줄 수 있도록 커버를 설정하십시오.

다음은 내가 생각해 낸 것입니다.

각 세트에 대해 반복하십시오. 1. 커버 < -Seti (i = 1 ,,, n) 2. 세트가 다른 세트의 서브 세트가 아니면 커버 세트로 가져갑니다.

하지만 일부 인스턴스에서는 작동하지 않습니다. 최소 세트 커버를 찾는 알고리즘을 찾아 내도록 도와주세요.

나는이 알고리즘을 온라인으로 찾는 데 여전히 문제가 있습니다. 누구든지 어떤 제안이 있습니까?

Answer 1

세트 커버는 NP 하드이므로 세트의 가능한 모든 조합을보고 각 조합이 커버인지 확인하는 것보다 훨씬 더 효율적인 알고리즘은 없을 것입니다.

기본적으로 1 세트, 2 세트 등 모든 조합을보고 표지가 될 때까지 살펴보십시오.

편집

이는 예시적인 의사 코드이다. 나는 이것이 효율적이라고 주장하지 않는다. 간단히 말해서 나는 (정말 멋진 뭔가가 발견되지 않는 한 알고리즘이 다항식 시간보다 더 나쁜 것) 훨씬 더 효율적인 알고리즘이 아니라고 주장

for size in 1..|S|: 
    for C in combination(S, size): 
      if (union(C) == U) return C 

곳 combination(K, n) 반환 요소 K에서 오는 크기 n의 모든 가능한 세트. 당신이 최소를 찾는 알고리즘을 필요로하는 이유

편집

그러나, 나는 너무 확실하지 않다. 질문에서 세트 커버링에 대한 욕심 많은 알고리즘이 때로는 더 많은 세트를 찾는다는 것을 보여주고 싶다고 말합니다. 그러나 이것은 반례문을 통해 쉽게 달성 할 수 있습니다. (그리고 반례는 위키 피 디아에 나와 있습니다. 그래서 나는 매우 당혹 스럽다.

편집

combination(K, n)의 가능한 구현은 다음과 같습니다

는

if n == 0: return [{}] //a list containing an empty set 
r = [] 
for k in K: 
    K = K \ {k} // remove k from K. 
    for s in combination(K, n-1): 
     r.append(union({k}, s)) 
return r 

그러나 커버 문제와 함께, 하나는 아마도 기본 케이스 n == 0 대신에서 범위의 테스트를 수행하고자합니다. 잘.