집합 커버(그리디 vs 최적) 계산기

덮어야 할 원소 전부를 가장 적은 개수의 부분집합으로 덮는 문제입니다. 예를 들어 모든 과목을 맡을 선생님을 최소 인원으로 뽑거나, 모든 지역에 닿도록 기지국을 최소 개수만 세우는 일이 그대로 이 문제입니다. NP-난해로 알려져 있어 다항시간에 최적을 내는 방법은 P = NP가 아닌 한 없습니다.

있습니다. 이 계산기의 기본 예가 그것입니다. U = {1,…,6}에 A = {1,2,3,4}, B = {1,2,5}, C = {3,4,6}이 있으면 그리디는 가장 큰 A를 먼저 집고 남은 5와 6 때문에 B와 C를 더 골라 3개가 듭니다. 그런데 A를 버리고 B·C만 고르면 2개로 끝납니다. 한 걸음 앞만 보는 판단이 나중의 선택지를 망친 것입니다.

최적의 H(k) ≤ 1 + ln n 배를 넘지 않습니다. n은 원소 수, k는 가장 큰 부분집합의 크기, H는 조화수입니다. 매 단계에서 남은 원소의 최소 1/OPT만큼을 덮기 때문에 이 보장이 성립합니다. 원소가 100개라면 최악이라도 최적의 5.6배 안입니다.

사실상 없습니다. P ≠ NP를 가정하면 (1−ε)·ln n보다 나은 근사비를 다항시간에 보장하는 알고리즘은 존재할 수 없다는 것이 증명되어 있습니다. 허술해 보이는 그리디가 이 문제에서는 이론적 한계에 닿아 있는 셈입니다.

부분집합 20개까지 전수 탐색으로 구합니다. 고르는 방법이 2^m가지라 20개면 약 105만 가지지만 40개면 1조 가지가 되어 브라우저에서 끝나지 않습니다. 20개를 넘으면 그리디 해만 내고 최적은 «접었다»고 표시합니다.

앞에 적힌 것을 고릅니다. 동점을 무작위로 깨면 새로고침할 때마다 답이 달라져 계산기 노릇을 못 하기 때문입니다. 그래서 줄 순서를 바꿔 넣으면 그리디의 답이 달라질 수 있는데, 그것 자체가 그리디의 성질입니다. 최적 해는 순서와 무관합니다.

전체를 덮을 수 없다고 알려 주고 그 원소를 짚어 줍니다. 그럴 때는 그리디도 최적도 «완전한 덮개»를 낼 수 없으므로, 덮을 수 있는 데까지 고른 결과만 보여 줍니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지고 넣은 값은 이 기기에만 남습니다.