많은 수의 파티셔닝

컴퓨터 과학에서 그리디 번호 분할은 멀티웨이 번호 분할을 위한 그리디 알고리즘의 클래스입니다.알고리즘에 대한 입력은 숫자 집합 S와 파라미터 k입니다.필요한 출력은 S를 k개의 서브셋으로 분할하여 서브셋의 합계가 가능한 한 동일하도록 하는 것입니다.탐욕 알고리즘은 숫자를 순차적으로 처리하여 다음 숫자를 현재 숫자의 합계가 가장 작은 빈에 삽입합니다.

근사 알고리즘

가장 간단한 그리디 파티셔닝 알고리즘은 리스트 스케줄링이라고 불립니다.입력이 도착하는 순서에 관계없이 처리됩니다.항상 최대 합계가 최적(최소) 최대 ^[1]합계의 $최대{\displaystyle \mathrm{}}$ - 1 k(\$displaystyle 2-{\frac {1}{k})$인 파티션을 반환합니다.이 경험적 접근법은 항목이 도착하는 순서를 제어할 수 없는 경우 온라인 알고리즘으로 사용할 수 있습니다.

개량된 그리디 알고리즘은 LPT 스케줄링이라고 불립니다.큰 것부터 작은 것까지 가치의 내림차순으로 입력을 처리합니다.입력 순서를 미리 지정해야 하므로 오프라인 알고리즘으로만 사용할 수 있습니다.최대 합계가 $최적{\displaystyle \frac{\mathrm{}}{}}$(최소) 최대 합계의 $({$$}{3k$${\displaystyle \frac{\})}{}}$배이고 최소 합계가 최적$최대)$ 최소 합계의 $({$배임을$$ 보장한다.자세한 내용은 LPT 예약을 참조하십시오.

완전 탐욕 알고리즘

완전 탐욕 알고리즘(CGA)은 정확한 알고리즘입니다. 즉, 항상 최적의 솔루션을 찾습니다.다음과 같은 방법으로 동작합니다.LPT와 같이 내림차순으로 번호를 정렬한 후 k-ary 트리를 만듭니다.각 레벨은 숫자에 대응하고, 각 k개의 브랜치는 현재 숫자를 넣을 수 있는 다른 세트에 대응합니다.트리를 깊이 우선 순서로 이동하려면 O(n) 공간만 필요하지만 O(kⁿ) 시간이 걸릴 수 있습니다.실행 시간은 탐욕적 휴리스틱을 사용하여 개선할 수 있습니다. 각 레벨에서 가장 작은 합으로 현재 숫자를 집합에 넣는 분기를 먼저 개발하십시오.이 알고리즘은 먼저 탐욕(LPT) 솔루션을 찾지만 더 나은 솔루션을 찾습니다.

런타임 개선을 위해 몇 가지 추가 ^[2]휴리스틱을 사용할 수 있습니다.

• 전류차이가 적어도 나머지 모든 숫자의 합인 노드에서는 나머지 숫자를 최소합 서브셋에 넣을 수 있다.
• 합계 차이가 0 또는 1인 리프에 도달하면 알고리즘이 최적이기 때문에 종료할 수 있습니다.
• 현재 노드에서 두 개 이상의 서브셋 합계가 동일한 경우, 이러한 서브셋 중 하나에 현재 수를 넣을 수 있으므로 서브트리의 크기를 절반 이상 줄일 수 있습니다.
• 마지막 숫자는 합계가 작은 부분 집합에만 할당할 수 있습니다.

일반화

공정항목 배분 문제에는 n개의 항목과 k명의 사람이 있으며, 각 항목마다 다른 가치를 할당할 수 있다.목표는 가능한 한 공평하게 아이템을 분할하는 것이다.그리디 번호 분할 알고리즘의 자연스러운 일반화는 envy-graph 알고리즘입니다.최대 1개 항목(EF1)까지 할당이 부러움 없이 이루어지도록 보장합니다.또한 인스턴스가 주문된 경우(모든 에이전트가 동일한 순서로 항목의 순위를 매기면), 결과는 EFX가 되며 각 에이전트에 대해 최대 점유율의 $(\$style$\frac$ {$2n}{3n-1})$을 보장합니다.항목이 허드렛일 경우 유사한 알고리즘으로 $(\$ MMS가$$ ^[3]$보증$됩니다.

실장

• Python: Prtpy 라이브러리에는 탐욕 알고리즘과 완전한 탐욕 알고리즘의 구현이 포함되어 있습니다.

레퍼런스

추가 정보

• Graham, R. L. (November 1966). "Bounds for certain multiprocessing anomalies". The Bell System Technical Journal. 45 (9): 1563–1581. doi:10.1002/j.1538-7305.1966.tb01709.x.