I Complete Set Partitioning problem får vi en ändlig uppsättning element där varje delmängd är associerad med ett värde, och målet är att dela upp denna uppsättning i separata delmängder för att maximera summan av delmängd värden. Detta abstrakta problem fångar problemet Coalition Structure Generation i kooperativa spel i karakteristisk funktionsform, där varje undergrupp, eller koalition, av agenter kan göra en vinst när de arbetar tillsammans, och målet är att dela upp uppsättningen av agenter i koalitioner för att maximera den totala vinsten. Det fångar också det speciella fallet med Winner Determination problem i kombinatoriska auktioner, där budgivare lägger bud på alla möjliga bunt av varor, och målet är att hitta en tilldelning av varor till budgivare som maximerar vinsten för auktionsförrättaren. Det viktigaste bidraget i denna artikel är en omfattande teoretisk analys av sökområdet för problemet med fullständig uppsättning partitionering, vilket visar att två fundamentalt olika exakta algoritmer kan förbättras avsevärt när det gäller faktisk körtid. Dessa är (1) en dynamisk programmeringsalgoritm som kallas "DP" [48, 36] och (2) en trädsökningsalgoritm som kallas "IP" [32]. Vi börjar med att rita en länk mellan DP och en viss graf som beskriver strukturen på sökytan. Denna länk visar att många av DP:s verksamheter i själva verket är överflödiga. Följaktligen utvecklar vi ODP-en optimal version av DP som undviker all sin överflödiga verksamhet. Eftersom ODP och IP bygger på olika designparadigm har var och en sina egna styrkor och svagheter jämfört med den andra. Därför måste man byta bort fördelarna med den ena algoritmen mot fördelarna med den andra. Detta väcker följande fråga: Är denna kompromiss oundviklig? För att svara på denna fråga utvecklar vi en ny representation av sökytan, som länkar ihop båda algoritmerna, och gör det möjligt att kontrastera de tvås funktion. Detta visar att ODP och IP faktiskt kan kombineras, vilket leder till utvecklingen av ODP-IP-en hybridalgoritm som undviker begränsningarna i dess beståndsdelar, samtidigt som man behåller och avsevärt förbättrar fördelarna med varje del. Vi jämför vår algoritm mot Björklund et al. (2009) [8], som löper i O (2 n ) tid ges n agenter. Vi observerar att algoritmen för Björklund et al. bygger på att utföra aritmetiska operationer med mycket stora heltal, och antar att varje sådan operation har enhetskostnad. I praktiken är det dock dyrt att arbeta med stora heltal på en modern PC. Följaktligen, när den genomförs, vår O (3 n ) algoritm överträffar den av
Nyligen, Michalak m.fl. REF genomförde en omfattande analys av sökytan för CFGs och visade att genom att kombinera dynamisk programmering med en trädsökning, är det möjligt att förbättra sökningen i förhållande till metoder med endast dynamisk programmering eller endast trädsökning.
A hybrid exact algorithm for complete set partitioning
{'venue': 'Artif. Intell.', 'journal': 'Artif. Intell.', 'mag_field_of_study': ['Computer Science']}