C은 {c1,c2,c3....cn} 컨테이너 집합을 말하며, 각 컨테이너에는 유한 집합의 정수 {i1,i2,i3...im}이 포함되어 있다고 가정합니다. 또한 정수가 둘 이상의 컨테이너에 존재할 수 있다고 가정합니다. 유한 정수 집합 S{s1,s2,s3...sz}이 주어진 경우 S에 모든 정수를 포함하는 C의 가장 작은 하위 집합의 크기를 찾습니다.주어진 모든 요소를 포함하는 컨테이너의 최소 수
수백 개의 정수가 포함 된 수천 개의 컨테이너가있을 수 있습니다. 그러므로이 문제를 해결하려면 무차별 한 힘이 느리다.
나는 Greedy 알고리즘을 사용하여 문제를 해결하려고했습니다. 즉, S 집합의 정수가 가장 큰 컨테이너를 선택할 때마다 실패했지만 실패했습니다!
누구든지이 문제에 대한 빠른 알고리즘을 제안 할 수 있습니까?
이것은 잘 알려진 set cover problem입니다. NP-hard - 실제로 결정판은 표준 NP 완전 문제 중 하나였으며 Karp's 1972 paper에 포함 된 21 개 문제 중 하나였으며 효율적인 알고리즘은 알려져 있지 않습니다. 문제에 대한 특별한 특수 구조를 식별 할 수없는 한 대략적인 결과, 즉 합집합에 S가 포함되어 있지만 반드시 이 가장 작은 C의 하위 집합과 같은 하위 집합 인 C의 하위 집합에 만족해야합니다.
아마도 greedy algorithm 일 가능성이 있습니다. 가장 작은 것의 크기보다 O (log | C |) 배 이상 큰 집합을 찾습니다.
욕심 많은 알고리즘을 작동시키지 못했다고합니다. 나는 이것이 아마도 제대로 구현하지 못했기 때문이라고 생각합니다. 이 같은 알고리즘을 설명 :
내가 설정 S
에서 정수의 최대 수 있지만, 보통의 욕심 알고리즘의 규칙 컨테이너를 선택할 때마다 각 단계에서 선택하는 것입니다 S 에있는 정수 중 가장 많은 수의 컨테이너는 지금까지 선택된 컨테이너에 포함되어 있지 않습니다..
아마도 여기에 누락 된 것이 있습니다. S = {1,2,3,4,5,6} 이고 3 개의 컨테이너가 있다고 가정하면 c1 = {1,3,4,6}, c2 = {1,2,3}, c3 = {4,5,6} 욕심 많은 알고리즘을 구현하는 중 ... 첫 번째 단계 c1에서 피킹 된 요소가 가장 많기 때문에 선택하겠습니다 .... 이후에는 c2를 걸고 c3. 이것은 분명히 올바른 해결책이 아닙니다. 왜냐하면 저는 c2와 c3만을 취할 수 있기 때문에 .... 당신은 어떻게 생각합니까? –
문제는 NP 완료이므로 합리적인 시간 내에 가장 작은 표지를 계산할 수는 없습니다. 그리 디 알고리즘은 * approximate 알고리즘 *입니다 : * a * 커버를 계산하지만, 항상 * 가장 작은 커버는 아닙니다. 가장 작은 표지를 찾는 것이 중요하다면 운이 없어집니다. –
Gareth Rees에게 감사드립니다. –
알고리즘은 생물 정보학과 어떤 관련이 있습니까? –
이것은 잘 알려진 [표지 문제] (http://en.wikipedia.org/wiki/Set_cover_problem)입니다. 이것은 NP 완성이므로 효율적인 알고리즘은 알려져 있지 않습니다. 욕심 많은 알고리즘은 수행 할 수있을뿐만 아니라 수행합니다 (P = NP가 아니면). –
나는 모든 주어진 유전자를 포함하는 GO 용어의 가장 작은 창 크기를 찾으려고 노력하고있다 .... 단순화를 위해 정수와 컨테이너를 사용했다. –