어떤 부분 집합을 적용하지하기 위해 세트에서 가능한 한 적은 수의 요소를 제거 :알고리즘 : 내가 해결하는 방법을 모르는 문제가있어
나는 세트 A = {A_1, A_2, ..., A_n}의 세트가 나는 세트가를 B .
이제 타겟은 모든 1 <= i <= n위한 요소를 제거한 후,이 A_i하지B'의 일부가되도록, B은 (B'를 만드는)에서 가능한 한 적은 요소를 제거하는 것이다.
예를 들어 A_1 = {1,2}, A_2 = {1,3,4}, A_3={2,5} 및 B={1,2,3,4,5} 인 경우, B에서 1과 2를 제거하십시오 (이는 B'={3,4,5}이며, A_i 중 하나의 수퍼 세트는 아닙니다).
제거 할 요소의 최소 수를 결정하는 알고리즘이 있습니까?
최소 hitting set이 A 인 것을 B에서 제거하고 싶습니다 (이것은 정점 커버 문제와 밀접하게 관련되어 있음).
일부 세트 세트에 대한 타격 세트 A은 그 자체로 각 세트의 적어도 하나의 요소가 A (각 세트에 "히트")으로 포함되는 세트입니다. 최소 타격 세트는 가장 작은 타격 세트입니다. 따라서 세트 세트에 대한 MHS가 A 인 경우 각 세트의 요소는 A입니다. 이것을 B에서 제거하면 A에 no가 설정되고 B의 부분 집합이 될 수 있습니다.
당신이해야 할 모든이의 MHS를 계산이다 (하는 ...에서 N), 다음 B에서 그것을 제거합니다. 불행히도, MHS를 찾는 것은 완전한 NP 문제입니다. 하지만, 당신은 몇 가지 옵션이 있음을 알고 :
나는이 세트에서 최소 길이를 찾아서이 세트에있는 이들 요소를 삭제해야한다고 생각합니다.
그냥 근사값이 필요하면 A에서 가장 작은 집합으로 시작하고 B에서 하나의 요소를 제거하십시오. (임의로 하나를 잡아 내거나 A에 가장 많은 요소가 있는지 확인하십시오. 얼마나 빨리, 얼마나 빨리 필요합니까?)
이제 A에서 가장 작은 세트는 B의 서브 세트가 아닙니다. 거기에서 계속 이동하십시오. 그러나 검사중인 세트가이 부분 집합인지 여부를 먼저 확인하십시오 포인트 또는 아닙니다.
이것은 꼭지점 문제를 생각 나게하고, 이것과 비슷한 비슷한 근사 알고리즘을 기억합니다.
@ davit-datuashvili : Chris의 답변이 자리하고 있으므로 읽어 보시기 바랍니다. –