알고리즘 :

Question

을 감안할 때 몇 세트 전체 도메인을 포함하는 세트의 최소 수와 수 (n) 찾기 : 이제 우리는 단지 b 및 c 우리가 0으로 전체 범위를 얻을 걸릴 경우

Here assume n is 5: 
a - (0,1,2) 
b - (0,1,2,3) 
c - (1,3,4,5) 
d - (0,1,2,4) 
e - (2,3,4,5) 
f - (3,5) 

을 5

나는 탐욕스러운 접근 방식을 생각하고 있었지만 여기에는 적합하지 않은 것으로 보인다.

Answer 1

이것은 set cover problem이며 가능한 모든 해결책을 고려하고 최소값을 선택해야합니다.

Answer 2

가능한 모든 하위 집합을 확인하면 최소 집합 수를 얻는 가장 좋은 방법이지만 k이 집합 수이면 2^k이됩니다.

그래프를 작성하고 깊이가 1,2,3 인 DFS를 실행하여 전체 커버리지를 얻을 수 있습니다.

런타임과 최적의 솔루션 간의 거래가 있습니다. 는 최소 실행 시간보다 적은 옵션을 수용하지 않습니다.

Answer 3

BFS 검색은이 문제를 쉽게 해결할 수 있습니다. 난에서 검색

min = 0 

function bfs(i, visited sets) 
    if i > m 
     n = the number of the visited sets without duplicates 
     if n < min 
      min = n 
     end 
     return 
    end 

    if no set contains i 
     return 
    end 

    for each set that contains i 
     bfs(i+1, visited sets + this set) 
    end 
end 

시작 = 0 빈 방문 세트

bfs(0, empty set) 

그런 다음 min는 세트의 최소 수있을 것입니다.