가장 큰 차이점 보관 방법

컴퓨터 과학에서 가장 큰 차이점 분석 방법은 파티션 문제와 다중 방향 번호 분할을 해결하기 위한 알고리즘입니다.그것은 또한 발명가인 Narendra Karmarkar와 Richard M. ^[1]Karp의 이름을 따서 Karmarkar-Karp 알고리즘이라고도 불린다.많은 경우 ^[2]LDM으로 약칭됩니다.

알고리즘

알고리즘에 대한 입력은 숫자 집합 S와 파라미터 k입니다.필요한 출력은 S를 k개의 서브셋으로 분할하여 서브셋의 합계가 가능한 한 동일하도록 하는 것입니다.알고리즘의 주요 단계는 다음과 같습니다.

1. 숫자를 큰 것부터 작은 것 순으로 정렬합니다.
2. 가장 큰 숫자와 두 번째로 큰 숫자를 차이로 바꿉니다.
3. 2개 이상의 번호가 남아 있는 경우는, 순서 1로 돌아옵니다.
4. 역추적을 사용하여 파티션을 계산합니다.

양방향 파티셔닝

k=2의 경우 주 단계(2)는 다음과 같이 작동합니다.

• S에서 가장 큰 두 숫자를 추출하여 S에서 제거한 다음 차이를 삽입합니다(이는 각 숫자를 다른 부분 집합에 넣기로 결정함).
• 하나의 번호가 남을 때까지 이 방법으로 진행합니다.이 단일 숫자는 두 부분 집합 간의 합계의 차이입니다.

예를 들어, S = {8,7,6,5,4}인 경우 가장 큰 두 숫자 {8,7}을(를) 뺀 후 차이 8-7=1을 다시 삽입한 후 결과 차이 집합이 {6,5,4,1}이 됩니다. 이 단계를 반복하면 {4,1,1}이(가) 생성됩니다.

스텝 3에서는 파티션 내의 서브셋을 백트래킹으로 구축합니다.마지막 단계는 {2},{}에 해당합니다.그런 다음 2가 한 집합에서 3으로 대체되고 다른 집합에서 1로 대체됩니다. {3},{1}, {4},5}, {1,6}, {4,7,5}, {8,6}은(는) 실제로 2입니다.

이 알고리즘의 런타임 복잡성은 O(n log n)가 걸리는 스텝1(Sorting)에 의해 좌우됩니다.

이 파티션은 최적이 아닙니다. 파티션 {8,7}, {6,5,4}에서 합계 차이는 0입니다.다만, 「정상적인」파티션이 제공되고 있는 것은 다음과 같습니다.

• 수치가 [0,1]로 균일하게 분포되어 있는 경우, 2개의 합계 사이의 예상 차이는${\displaystyle {}^{}}n{\displaystyle {}^{}}$ -${\displaystyle {\mathrm{\Omega }}^{}}$ ( ${\displaystyle {\log }^{}}$display ( ${\displaystyle n^{}}$ )$}$ { $displaystyle$ n^ { - \ $Theta$( \$log$ ($n$ ) }$$。이는 최대합과 최적합 사이의 $예상비$가 1${\displaystyle }$+${\displaystyle {}^{}}$ -${\displaystyle {\mathrm{display}}^{}}$ ( log$$ + 1 ( ${\displaystyle {\log }^{}}$ ${\displaystyle {）}^{}}$ （ $log$ ） ）$$。$Theta (\log(n))}}:$^[3]
• 항목이 최대 4개일 경우 LDM은 최적의 파티션을 반환합니다.
• LDM은 항상 최대 합계가 ^[4]최적치의 7/6배인 파티션을 반환합니다.5개 이상일 때는 ^[2]빠듯합니다.
• 랜덤 인스턴스에서는 이 근사 알고리즘이 그리디 번호 분할보다 훨씬 뛰어난 성능을 발휘합니다.그러나 집합의 크기가 ^[5]기하급수적으로 큰 경우에는 여전히 좋지 않습니다.

멀티웨이 파티션

임의의 k≤ 2에 대해서, 알고리즘은 다음과 같이 일반화 ^[2]할 수 있다.

• 처음에 S의 각 숫자 i에 대해 하위 집합의 k-튜플을 구성합니다. 여기서 한 하위 집합은 {i}이고 다른 k-1 하위 집합은 비어 있습니다.
• 각 반복에서 최대합과 최소합 사이의 차이가 가장 큰 두 k-튜플 A와 B를 선택하고 크기 역순으로 결합합니다. 즉, A에서 가장 작은 서브셋과 B에서 두 번째로 작은 서브셋입니다.
• 단일 파티션이 남아 있을 때까지 이 방법으로 진행합니다.

예:

• S = {8,7,6,5,4} 및 k=2인 경우 초기 파티션은 {8}, {7}, {}, {6}, {}, {5}, {}, {4}, {}입니다.첫 번째 단계 후에 ({6}, {}), ({5}, {}), ({4}, {}), ({8}, {7})이 표시됩니다.그런 다음({4},{}),({8},{7}),({6},{5}).그런 다음({4,7},{8}),({6},{5}), 마지막으로({4,7,5},{8,6}) 합계가 2입니다. 이 파티션은 위에서 설명한 것과 동일합니다.
• S = {8,7,6,5,4} 및 k=3인 경우 초기 파티션은 ({8},{}), ({7},{}), ({6},{}), ({5},{}), ({4},{})입니다.첫 번째 단계 이후에는 ({8},{7},{6},{}),({5},{}),({4},{})가 표시됩니다.그런 다음({5},{}),({4},{}),({8},{7},{6}).그런 다음({5},{4},{8},{7},{6}), 마지막으로({5,6},{4,7},{8}) 합계가 3입니다.
• S = {5,5,4,4,3,1,k=3이면 7회 반복하면 파티션({4,5},{1,4,5},{3,5})^[2]이 생성됩니다.이 솔루션은 최적이 아닙니다. 더 나은 파티셔닝은 그룹화({5,5}, {3,3,4}, {1,4,5})를 통해 제공됩니다.

LDM의 ^[2]퍼포먼스가 우수하다는 증거가 있습니다.

• 시뮬레이션 실험에 따르면, [0,1]에서 숫자가 균일하게 랜덤일 때, LDM은 항상 탐욕스러운 숫자 분할보다 더 나은 성능을 발휘합니다(즉, 더 작은 최대 합계를 가진 파티션을 생성합니다).항목 수 n이 충분히 클 경우 멀티비트 알고리즘보다 성능이 우수합니다.[o, o+1]의 수치가 균일하게 랜덤한 경우, 일부 o>0부터 LDM의 퍼포먼스는 안정된 상태로 유지되며, o가 증가할수록 멀티핏의 퍼포먼스는 저하된다.o>0.2에서는 LDM의 퍼포먼스가 향상됩니다.
• f*를 최적의 최대합으로 합니다.모든 수치가 f*/3보다 클 경우 LDM은 최적의 솔루션을 반환합니다.그렇지 않으면 LDM은 최대합과 최소합 사이의 차이가 최대 f*/3인 솔루션을 반환합니다.
• k+2 항목이 많아야 LDM이 최적입니다.
• 항목 수 n이 k+2 ~ 2k 사이일 경우 LDM 파티션의 최대 합계는 $최대{\displaystyle \frac{\mathrm{}}{}}$ ${\displaystyle \frac{4}{}3\frac{\mathrm{}}{}}$ - 1${\displaystyle \frac{3}{}}$ (${\displaystyle \frac{n}{}}$- ${\displaystyle \frac{\mathrm{k}}{}}$ -${\displaystyle \frac{}{}}$1 $){${$frac$ { $4 }$ - { \$frac${ 3 ( $n$- k - 1$$}}}입니다.
• 어느 경우든 LDM 파티션의 최대 합계는 $(\$이며, $최소{\displaystyle \frac{\mathrm{}}{}\frac{4-3-1\mathrm{}(\mathrm{k}}{}}$- 1$)(\$}{$3}-k})$인 경우가 있습니다.
• 양방향 분할에서는 입력이 균등하게 분포된 랜덤 변수일 경우 최대합과 최소합 사이의 예상 차이는${\displaystyle {}^{}}$n -${\displaystyle {\mathrm{\Omega }}^{}}$ ( ${\displaystyle {\log n}^{}}$n $){$ $displaystyle$ n^ { - \ $Theta$( \ $log$n )$$^[3]} 입니다.

균형 잡힌 양방향 파티셔닝

모든 서브셋이 같은 카디널리티(최대 1)를 가져야 하는 균형잡힌 번호 분할 문제를 위해 여러 종류의 LDM이 개발되었습니다.

PDM(Paired Differencing Method)은 다음과 ^[6]같이 동작합니다.

1. 숫자를 큰 것부터 작은 것 순으로 정렬합니다.
2. #1과 #2는 차이, #3과 #4는 차이 등으로 대체한다.
3. 2개 이상의 번호가 남아 있는 경우는, 순서 1로 돌아옵니다.
4. 역추적을 사용하여 파티션을 계산합니다.

PDM의 평균 속성은 LDM보다 나쁩니다.양방향 파티셔닝에서는 입력이 균등하게 분포된 랜덤 변수일 경우 최대합과 최소합 사이의 예상 차이는${\displaystyle }\delta {\displaystyle \mathrm{}}$ ${\displaystyle (1}$/ n$$) \$displaystyle \Theta (1/n$ 입니다.

RLDM(Restricted Migest Differencing Method)은 다음과 ^[7]같이 동작합니다.

1. 숫자를 큰 것부터 작은 것 순으로 정렬합니다.
2. #1과 #2는 차이, #3과 #4는 차이 등으로 대체한다.
3. 큰 것부터 작은 것까지 n/2 차이 목록을 정렬합니다.
4. 각 쌍을 서로 다른 집합에 차례로 할당합니다. 즉, 쌍에서 가장 큰 쌍은 가장 작은 합계의 집합에 할당하고 쌍에서 가장 작은 쌍은 가장 큰 합계가 큰 집합에 할당합니다.

쌍방향 분할에서는 입력이 균등하게 분포된 랜덤 변수인 경우 최대합과 최소합 사이의 예상 차이는 O${\displaystyle (\log n}$n / $)\displaystyle$ O$(\log {n}/n^{2$입니다.

BLDM(Balanced Migest Differencing Method)은 다음과 ^[3]같이 동작합니다.

1. 숫자를 큰 것부터 작은 것 순으로 정렬합니다.
2. #1과 #2는 차이, #3과 #4는 차이 등으로 대체한다.
3. 차이에 따라 LDM을 실행합니다.

BLDM의 평균 속성은 LDM과 비슷합니다.양방향 분할에서는 입력이 균등하게 분포된 랜덤 변수일 경우 최대합과 최소합 사이의 예상 차이는${\displaystyle {}^{}}$n -${\displaystyle {\mathrm{\Omega }}^{}}$ ( ${\displaystyle {\log n}^{}}$n $){$ $displaystyle$ n^ { - \ $Theta$( \ $log$n )$$^[3]} 입니다.

다방향 분할의 경우, c=120(n/k) 및 각 k개의 서브셋이 천장(n/k) 또는 바닥(n/k) 항목 중 하나를 포함해야 하는 경우, 최소 총합에 대한 BLDM의 근사 비율은 c=3의 경우 정확히 4/3, c=4의 경우 19/12, c=5의 경우 103/3/360의 경우, c=25의 경우 460의 경우 정확히 460이다.이 비율은 혼합 정수 선형 프로그램을 풀어서 구했습니다.일반적으로(임의의 c에 대해) 근사비는 $최소{\displaystyle \mathrm{}}$2 -${\displaystyle \underset{\mathrm{\mu j}}{\overset{}{}}}$ ${\displaystyle \underset{0}{\overset{}{=}}}$ ${\displaystyle \frac{}{}}$ -${\displaystyle \frac{}{}}$1 j${\displaystyle \frac{}{}}$! c $!\$ _${j=0}^{c-1}{\frac {j!$$}{c!}},$ $최대$ 2-1c-1({displaystyle 2-${\frac$ {1$}{c-1$입니다.3,4,5,6,7에 대한 MILP 결과는 하한에 해당합니다.파라미터가 서브셋의 수(k)인 경우 근사비는 $({$^[8]입니다.

최소-최대 후속 문제

min-max sequence 문제에서 입력은 n개의 숫자와 정수 파라미터 k의 멀티셋이며, 목표는 인접한 k개 숫자의 각 블록의 최대합이 가능한 한 작아지도록 숫자의 순서를 정하는 것이다.비디오 서버의 ^[9]설계로 문제가 발생.이 문제는 k=2의 경우 폴리타임으로 해결할 수 있지만 k≥3의 경우 NP-hard이다.이 ^[10]문제에는 차분 보관 방법의 편차를 적용할 수 있습니다.

정확한 알고리즘

완전한 Karmarkar-Karp 알고리즘(CKK)은 $!\displaystyle$ k$!\}$의 트리를 생성하여 최적의 솔루션을 찾습니다.

• k=2인 경우, 각 수준은 한 쌍의 숫자에 해당하며, 두 가지는 차이를 취하거나(즉, 서로 다른 집합에 넣거나), 합을 취하거나(즉, 같은 집합에 넣음) 이에 해당한다.
• 일반적인 k의 경우, 각 레벨은 k-튜플 쌍에 대응하며${\displaystyle ,}$ k$!\displaystyle$ k$!}$의 브랜치는 이러한 튜플의 서브셋을 조합하는 다른 방법에 대응합니다.

k=2의 경우, CKK는 무작위 인스턴스에서 완전 탐욕 알고리즘(CGA)보다 상당히 빠르게 실행됩니다.이는 두 가지 이유로 인해 발생합니다.등분할이 존재하지 않는 경우 CKK는 종종 CGA보다 더 많은 트리밍을 허용합니다.등분할이 존재하는 경우 CKK는 종종 훨씬 더 빨리 검출하여 조기 종료를 허용합니다.Korf에 따르면 CKK는 약 3시간 내에 15자리 배정밀 번호 40개를 최적 분할할 수 있으며, CGA는 약 9시간이 소요됩니다.실제로 k=2의 경우 숫자가 최대 12개의 유효 자릿수를 가지면 임의의 크기의 문제를 CKK로 해결할 수 있다. k=3의 경우 최대 6개의 유효 ^[11]자릿수를 가질 수 있다.

CKK는 임의의 알고리즘으로서도 실행할 수 있습니다.KK 솔루션을 먼저 찾은 후 시간이 허락하면 점진적으로 더 나은 솔루션을 찾습니다(최악의 ^[12]경우 최적성에 도달하려면 기하급수적인 시간이 필요할 수 있습니다).

CKK와 Balanced-LDM Algorithm(BLDM; 균형잡힌 LDM 알고리즘)을 조합하면 균형잡힌 파티션 ^[13]문제를 해결하기 위한 완전한 임의의 알고리즘이 생성됩니다.

앞서 말한 내용

나흐마니데스와 조셉 이븐 하비브가 고대 유대교 법률 문헌에서 카르마르카르-카르프의 차이점 발견과 동등한 알고리즘이 언급되어 있다.이 알고리즘은 동일한 ^[14]대출에 대한 다양한 증언을 결합하기 위해 사용됩니다.

실장

• Python: Prtpy 라이브러리에는 Karmarkar-Karp 알고리즘과 완전한 Karmarkar-Karp 알고리즘이 구현되어 있습니다.

레퍼런스