근사 보장·가치 스케일링·Knapsack FPTAS

근사 보장은 무엇을 약속할까?

특정 데이터에서 좋은 답을 얻는 것과 모든 허용 입력에 대한 품질을 보장하는 것은 다릅니다. 이 단원에서는 최대화 문제의 가능한 해가 주는 가치 A에 대해 다음 경계를 배웁니다.

$$A\ge(1-\epsilon)\mathrm{OPT},\qquad 0<\epsilon<1.$$

이 비율은 성공 확률이 아니라 해의 품질에 대한 하한입니다. 최소화에서는 보통 A≤(1+ε)OPT와 같이 반대 방향을 사용합니다. 문헌에 따라 1보다 큰 근사 계수를 쓰기도 하므로 어떤 부등식으로 정의했는지 확인해야 합니다. 손실 OPT−A와 관측 근사비 A/OPT도 다릅니다. OPT=0이면 비율을 정의할 수 없습니다.

화면은 무게가 2,3,4,5인 네 이진 물건, 020의 정수 가치, 014의 정수 용량을 사용합니다. 허용 오차는 0.1부터 0.9까지입니다. 작은 범위는 내부 계산을 살펴보기 위한 것이며 일반적인 보장은 열여섯 부분집합을 검사했다는 사실에서 나오지 않습니다.

그럴듯한 휴리스틱에도 별도의 증명이 필요하다

화면의 고정 무게와는 다른 이론적 사례를 생각해 봅시다. 용량이 M이고, 무게 1·가치 2인 물건과 무게 M·가치 M인 물건이 있습니다. M>2이면 가치/무게 greedy는 작은 물건부터 선택하고 큰 물건을 넣지 못합니다. 그 결과의 근사비 2/M은 M이 커지면 0에 가까워집니다. 국소적으로 합리적인 규칙이 자동으로 일정한 근사비를 보장하지는 않습니다.

Branch and Bound는 정확한 경계를 유지하여 최적값을 인증하지만 많은 가지를 탐색할 수 있습니다. 여기서는 가치의 손실을 제어하는 대신 DP의 점수 범위를 줄입니다. 원래 무게와 용량은 바꾸지 않으며 무게를 반올림하여 가능성을 느슨하게 만들지 않습니다.

가능한 단일 물건으로만 스케일을 정하기

먼저 무게가 용량보다 큰 물건을 제외합니다. 남은 단일 물건은 각각 가능한 해이므로 그 최대 가치 Vmax는 OPT 이하입니다. 화면의 n=4에서 다음을 정의합니다.

$$K=\frac{\epsilon V_{\max}}4,\qquad q_i=\left\lfloor\frac{v_i}{K}\right\rfloor.$$

ε=e/10이면 K=eVmax/40이고 q는 40v를 eVmax로 나눈 몫입니다. 분기 판단과 내림은 반올림된 그래프 소수가 아니라 정수로 계산합니다. 점수 배열에서 제외 물건의 0은 계산용 자리표시이며 그림에는 —로 구분합니다. 가능한 물건이 축소되어 얻은 0과 혼동하면 안 됩니다. 가능한 양의 가치가 없으면 모든 가능한 해의 가치가 0이므로 빈 해를 반환하고 K와 관측 비율을 사용 불가로 표시합니다.

K가 정의된 경우 물건마다 0≤v−Kq<K입니다. K보다 작은 양의 가치가 점수 0으로 지워질 수 있습니다. 그림의 파랑은 원래 가치, 주황은 Kq로 복원한 가치여서 같은 단위로 길이를 비교합니다. 별표는 근사 해가 선택한 물건을 나타냅니다.

정확 점수별 최소 무게를 저장하는 DP

D(i,s)를 앞 i개 물건으로 축소 점수 s를 정확히 얻을 때의 최소 원래 무게로 정의합니다. D(0,0)=0이며 다른 초기 상태는 도달 불가능입니다. 제외 물건의 행은 그대로 복사하고, 가능한 물건은 다음 두 선택을 비교합니다.

$$D(i,s)=\min\{D(i-1,s),\ w_i+D(i-1,s-q_i)\}.$$

두 번째 항은 점수가 음수이거나 원래 상태가 도달 불가능하면 없습니다. 두 선택 모두 이전 행을 참조해야 같은 물건을 여러 번 사용하는 오류를 막습니다. 현재 행의 새 상태를 다시 사용하면 이진 선택 문제가 무한 반복 선택 문제로 바뀔 수 있습니다.

유한한 최소 무게에는 물건 부분집합 mask도 함께 저장합니다. 무게가 동률이면 작은 mask를 선택하며, 같은 축소 점수에서 원래 가치를 최대화하는 표는 아닙니다. 마지막 행에서 최소 무게가 용량 이내인 가장 큰 점수를 선택합니다. 무게가 유한하지만 용량을 넘는 상태는 도달 가능하되 현재 용량에서는 사용할 수 없는 상태입니다.

창에는 조회 점수 주변 다섯 열과 다섯 개의 물건 prefix 행이 보입니다. —는 할당된 표 안에서 도달 불가능, ×는 할당한 점수 범위 밖입니다. 조회 수치에서 두 경우를 구분합니다. mask 비트 1,2,4,8은 물건 0,1,2,3을 뜻합니다.

버린 가치의 합으로 품질을 증명하기

원래 최적해를 O, 축소 DP가 선택한 해를 S라고 합시다. DP는 축소 점수를 최대화하므로 q(S)≥q(O)입니다. O에 들어가는 물건은 네 개 이하이고 각 물건에서 잃은 가치는 K 미만이므로 다음이 성립합니다.

$$v(S)\ge Kq(S)\ge Kq(O)\ge v(O)-4K =\mathrm{OPT}-\epsilon V_{\max} \ge(1-\epsilon)\mathrm{OPT}.$$

마지막 단계는 가능한 물건만으로 Vmax를 정했다는 가정을 사용합니다. 중간의 덧셈 손실 허용량 εVmax는 εOPT보다 더 작을 수도 있습니다. 이 증명은 비교용 부분집합 열거를 사용하지 않습니다. 작은 입력의 검산은 구현 오류를 찾는 근거이지만 모든 입력을 다루는 부등식의 증명을 대신하지 않습니다.

왜 FPTAS라고 부를까?

일반적인 물건 n개에서는 K=εVmax/n으로 둡니다. 각 가능한 점수는 n/ε 이하이고 전체 점수 Q는 n²/ε 이하입니다. 밀집 DP의 계산량은 O(nQ)=O(n³/ε) 산술 연산입니다. 화면은 검토를 위해 모든 행을 저장하고 그 셀 수를 셉니다. 값만 필요한 구현은 두 행만 유지하여 값 표의 작업 저장공간을 O(Q)로 줄일 수 있습니다.

PTAS는 ε를 고정했을 때 입력 크기에 대해 다항 시간입니다. FPTAS는 입력 크기와 1/ε 양쪽에 대해 다항 시간이어야 합니다. 원래 용량이나 가치 숫자 자체에 대한 다항 시간은 의사 다항 시간일 수 있습니다. 큰 수를 쓰는 데 필요한 비트 수는 그 숫자보다 훨씬 작기 때문입니다. 축소는 DP 셀 수가 원래 가치의 크기에 직접 비례하지 않게 하지만 정수 산술의 비트 비용까지 없애지는 않습니다. 할당한 셀, 유한한 도달 상태, 실제 실행 시간을 구분하세요.

손계산: 거친 축소와 더 작은 허용 오차

가치 (0,0,3,19), 용량 9, ε=0.7이면 Vmax=19, K=133/40입니다. 점수는 (0,0,0,5)이고 DP는 물건 3만 고릅니다. 원래 가치 19, 무게 5, mask 8입니다. 별도로 열거한 최적해는 물건 2와 3을 골라 가치 22, mask 12입니다. 관측비 19/22는 약 0.864이며 일반 보장 계수 0.3과 다릅니다. 손실 3은 허용량 13.3 이하입니다.

ε=0.1로 줄이면 K=19/40, 점수는 (0,0,6,40)입니다. DP는 점수 46에서 mask 12를 선택하여 가치 22를 얻습니다. 할당 셀은 5×6=30개에서 5×47=235개로 늘어납니다. 이번 관측비가 1이어도 모든 허용 입력에 대한 정리의 보장은 0.9입니다. 더 좋은 보장 하한은 각 입력의 정확한 출력값이 어떻게 바뀌어야 하는지까지 지정하지 않습니다.

곡선의 주황 값은 (1−ε)에 별도 열거한 OPT를 곱한 교육용 기준입니다. 이 작은 예제에서는 열여섯 부분집합으로 OPT를 알 수 있지만 실제 큰 문제에서는 보통 미리 알지 못합니다. 근사 알고리즘 자체는 비교용 OPT를 참조하지 않습니다.

연습 문제와 해설: 잘못된 스케일

문제: 가치 (1,0,0,20), 용량 2, ε=0.9를 사용하세요. 가치 20인 물건을 스케일을 정하기 전에 제외해야 하는 이유는 무엇인가요?

해설: 그 물건의 무게 5는 용량을 초과합니다. 가능한 Vmax는 1, K는 9/40이고 유일한 양의 가능한 물건의 점수는 4입니다. DP는 가치 1을 얻습니다. 불가능한 가치 20으로 계산했다면 K=4.5라서 가능한 가치 1도 점수 0이 되고, 최소 무게 동률 규칙으로 빈 해를 선택합니다. 그 가치 0은 보장값 0.1×OPT=0.1보다 작습니다. 스케일을 만드는 가정을 잘못 적용한 것입니다.

추가 문제: 모든 가치를 0으로 바꾸세요. 해설: 빈 해가 최적이고 K는 사용 불가이며 A/OPT는 0/0입니다. 비율 1을 임의로 표시하면 안 됩니다. 이어서 양의 점수가 있는 예제의 0행에서 그 점수를 조회하면 도달 불가 상태가 보이고, 거친 예제에서 점수 160을 조회하면 표 밖 상태가 보입니다.

AI 연구와 연결하기

학습한 점수, 실험에서 관측한 비율, 증명한 경계를 따로 보고해야 합니다. 목적함수를 바꾸거나 음의 가치를 허용하거나 제약을 반올림하거나 DP 전이를 바꾸면 보장도 다시 검토해야 합니다. 이 결정적 작은 실습은 임의의 비볼록 학습 목적함수에 대한 근사 스킴을 주장하지 않습니다.

정의는 MIT6.854 근사 알고리즘 노트, 가치별 DP와 스케일링은 Katherine Lai의 MIT18.434 노트와 MIT6.046J 문제9 해설을 참고할 수 있습니다. 네 물건 예제와 정확한 매개변수·조회 진단은 교재를 위해 직접 구성했습니다.