Partitieprobleem

Het partitieprobleem is een probleem uit de combinatoriek.

Definitie

Bij dit probleem moet een gegeven verzameling getallen opgesplitst worden in twee deelverzamelingen op een zodanig manier dat het verschil van de sommen van hun elementen zo klein mogelijk is. De gegeven verzameling is in het algemeen een multiset, want eenzelfde getal mag meer dan eenmaal erin voorkomen.

Een formelere definitie is:

Gegeven een multiset $A$ van n positieve gehele getallen $a_{i},i=1\dots n.$ Maak een partitie van de elementen van $A$ in twee multisets $A_{1}$ en $A_{2}$ zodanig dat

$E:=\left|\sum _{a_{i}\in A_{1}}a_{i}-\sum _{a_{i}\in A_{2}}a_{i}\right|$

minimaal is. De waarde $E$ noemt men de afstand van de partitie. Wanneer $E=0$ spreekt men van een perfecte partitie. Dit is enkel mogelijk wanneer de som van de elementen van $A$ even is; wanneer de som oneven is, is $E=1$ het kleinst mogelijke verschil.

Dit is een optimaliseringsprobleem; het corresponderende beslissingsprobleem is: bestaat er een perfecte verdeling voor de gegeven verzameling van getallen?

Complexiteit

Het partitieprobleem, geformuleerd als beslissingsprobleem, is NP-volledig; het is een van de 21 klassieke NP-volledige problemen die Richard M. Karp in 1972 oplijstte. Stephan Mertens noemde dit het makkelijkste moeilijke probleem ("the easiest hard problem"). In de praktijk blijkt het namelijk in vele gevallen mogelijk om een exacte oplossing te vinden in een redelijke termijn.

Oplossingsmethoden

Het probleem kan met brute kracht aangepakt worden, door alle mogelijke partities te testen. De rekentijd stijgt echter exponentieel met het aantal getallen.

De eenvoudigste heuristiek is een gulzig algoritme (GA). Eerst worden de elementen van A gerangschikt in dalende volgorde. Men bouwt de multisets A₁ en A₂ op door het grootste getal uit A te nemen en te plaatsen in die multiset met de op dat moment kleinste som van haar elementen (als de sommen gelijk zijn maakt het niet uit in welke multiset het getal terechtkomt). Dit wordt herhaald totdat alle getallen verdeeld zijn.

De Karmarkar-Karp-(KK)-heuristiek is iets ingewikkelder. In plaats van het grootste getal uit A, worden de twee grootste getallen beschouwd. Gegeven A in dalende volgorde, worden de twee grootste getallen eruit vervangen door hun verschil, dat een nieuw element van A wordt. Dit wordt herhaald tot er een getal overblijft, dat het verschil van de sommen van de elementen uit de twee multisets A₁ en A₂ is. De KK-heuristiek berekent dus de afstand van de partitie maar niet de partitie zelf; die kan opgebouwd worden uit de opeenvolgende beslissingen van het algoritme met behulp van een graafkleuringsprocedure.

Noch het gulzige algoritme noch de KK-heuristiek geven in het algemeen de exacte, optimale oplossing. Bijvoorbeeld voor de verzameling A={8,7,6,5,4} levert het gulzig algoritme de partitie {{8,5,4},{7,6}} of {{8,5}{7,6,4}}, met afstand 4, terwijl er een perfecte partitie bestaat: {{8,7}{6,5,4}} met afstand 0. De KK-heuristiek geeft in dit voorbeeld achtereenvolgens de verzamelingen {6,5,4,1}, {4,1,1}, {3,1} en {2}; de afstand 2 correspondeert met de partitie {{8,6},{7,5,4}}.

De KK-heuristiek geeft wel de exacte minimumafstand wanneer A vier of minder getallen heeft.

KK kan evenwel ingebouwd worden in het zogenaamde complete anytime-algoritme van Richard E. Korf. Dit is een algoritme dat betere en betere oplossingen vindt naarmate het langer loopt, en dat uiteindelijk de optimale oplossing vindt. Het algoritme bouwt een binaire boom op. In elke knoop worden de twee grootste getallen a₁ ≥ a₂ uit de daar resterende multiset vervangen; in het linkerkind door hun verschil | a₁ − a₂|, en in het rechterkind door hun som a₁ a₂. Dit komt overeen met het toewijzen van de twee grootste getallen aan twee verschillende deelverzamelingen (zoals in de KK-heuristiek gebeurt), of aan dezelfde deelverzameling. Door dit n−1 keer te itereren bekomt men een boom met 2ⁿ⁻¹ bladeren. Dat zijn multisets met 1 element, die samen alle mogelijke geldige partitie-afstanden vormen.

Voor het bovenstaande voorbeeld geeft dit de volgende boom:

Het complete Karmarkar-Karp-(CKK)-algoritme zoekt deze boom af volgens een "diepte-eerst, links naar rechts"-strategie. De eerste oplossing (meest linkse terminale knoop) is die van de "gewone" KK-heuristiek; maar door verder te zoeken kan CKK betere oplossingen vinden.

Merk op dat bepaalde delen van de boom kunnen weggesnoeid worden. Dit is het geval wanneer in een knoop het verschil tussen het grootste getal in de multiset en de som van alle andere getallen groter is dan de tot dan toe gevonden kleinste partitie-afstand. In dat geval is er geen betere oplossing mogelijk in die vertakking van de boom. En wanneer er een terminale knoop gevonden wordt met een perfecte partitie, kan het algoritme stoppen. In het voorbeeld zijn de gedeelten van de boom die weggesnoeid zijn in stippellijn aangegeven. Er zijn nog andere aanpassingen mogelijk om de rekentijd te verkorten. Wanneer bijvoorbeeld een knoop vier of minder getallen bevat is het niet meer nodig de boom onder die knoop verder uit te werken; de KK-heuristiek geeft daarvoor immers de exacte minimale afstand.

Er zijn voorts diverse metaheuristieken toegepast op dit probleem, waaronder simulated annealing, genetische en memetische algoritmen en tabu search.

Varianten

Het gebalanceerde partitieprobleem is het verdelen van een multiset van getallen in twee deelverzamelingen, zodanig dat de som van de getallen in de twee deelverzamelingen zo klein mogelijk is maar waarbij tevens de cardinaliteiten van de twee deelverzamelingen ten hoogste met een eenheid verschillen.

In het partitieprobleem met kernels zijn twee elementen s₁, s₂ uit de multiset aangeduid die niet in dezelfde deelverzameling mogen terechtkomen. Deze "kernels" moeten aan verschillende deelverzamelingen van de partitie worden toegewezen.

Het partitieprobleem zoals hier beschreven wordt vaak aangeduid als het "tweewegs" partitieprobleem, omdat men een partitie in twee multisets zoekt. Een veralgemening ligt voor de hand naar een "meerwegs" partitie in meer dan 2 multisets, waarbij het verschil tussen de grootste en de kleinste som van de elementen in de multisets minimaal moet zijn.

Toepassingen

Het partitieprobleem komt ook in praktische problemen voor. Een voorbeeld is het verdelen van een gegeven aantal rekentaken, waarvan de uitvoeringstijd bekend is, over twee computers of twee processors, zodanig dat de rekenlast zo gelijk mogelijk verdeeld is.

Bronnen, noten en/of referenties