[Algoritme] Zoek 'n algoritme voor een probleem.

[Verwijderd]

Hoi,

Ik ben op zoek naar een efficient algoritme voor het volgende probleem: Er zijn n personen die allemaal een bepaald percentage (p₁, p₂, ...,p_n) van een erfenis krijgen. Er zijn m objecten te verdelen met allen een bepaalde waarde(w₁, w₂, ...,w_m) . Bestaat er een algoritme om de ideale verdeling te vinden? Alle mogelijkheden nagaan is, als m en n een beetje groot worden, niet goed te doen. (Aantal mogelijke verdelingen is n^m)

(Btw: Er zijn verschillende manieren om de 'ideale verdeling' te definieren. Ik denk er zelf aan om de som van de absolute waarden van de procentuele afwijkingen te minimalizeren.)

Iemand 'n idee?

- sjoulibsky

[Creepy]

Dit is een redelijk "standaard" probleem waar genoeg informatie inclusief algoritmes voor te vinden zijn.

Dus: wat heb je zelf al gevonden? Denk je dat het nog beter kan dan wat je al hebt? Waarom?

[Verwijderd]

Het probleem dat alle percentages gelijk zijn (dus in n gelijke stukken verdelen) is voor zover ik weet al NP-compleet, dus zal dit het ook wel zijn.
Wil je echt de beste verdeling of een die er in de buurt komt?

gevonden: voor 2 gelijke stukken heet het "Integer Partition"

to partition the elements of S into two sets A and B such that the difference is as small as possible. Integer partition can be thought of as bin packing with two equal-sized bins or knapsack with a capacity of half the total weight, so all three problems are closely related and NP-complete.

[ Voor 53% gewijzigd door Verwijderd op 22-02-2005 22:28 ]

[Verwijderd]

Creepy schreef op dinsdag 22 februari 2005 @ 22:23:
Dit is een redelijk "standaard" probleem waar genoeg informatie inclusief algoritmes voor te vinden zijn.

Dus: wat heb je zelf al gevonden? Denk je dat het nog beter kan dan wat je al hebt? Waarom?

Nou, ik dacht dus ook dat 't een behoorlijk 'standaard' probleem was, maar googlen heeft nog niet zo erg veel opgeleverd... Maar dit onderwerp is ook behoorlijk nieuw voor me, dus misschien zoek ik op de verkeerde termen...

[Verwijderd]

Zoek maar 's op "traveling salesman".
Dit zijn idd. klassieke vraagstukken, en erg lastig om optimaal in een algorithme te proppen.
Er zijn bedrijven die daar kapitalen mee verdienen (yield management voor de vliegtuig- en hotelindustrie bijvoorbeeld)

[Macros]

Is dit niet een variant van Multiple Knapsack probleem?
Bestaan veel goede efficiente solvers voor die in de meeste gevallen polynomiaal zijn

[Verwijderd]

Macros schreef op dinsdag 22 februari 2005 @ 23:06:
Is dit niet een variant van Multiple Knapsack probleem?

Ik hoop 't. In ieder geval bedankt voor de terminologie enzo, dat googled een stuk makkelijker .

[Soultaker]

Misschien bin packing en stock cutting ook even meenemen; daar lijkt het me meer verband mee hebben dan traveling salesman. (In alle gevallen is een volledig algoritme waarschijnlijk niet efficiënt en kun je met een benadering met simulated annealing of iets dergelijks een heel eind komen.)

[Macros]

Ja, bin packing lijkt er ook erg op. Deze strakke NP complete problemen zijn vaak exact ook nog wel efficient omdat alleen speciale worst case gevallen exponentieel zijn.

[MrBucket]

Kun je eens een indicatie geven van "als m en n een beetje groot worden"? In welke orde van grootte moeten we denken?

Trouwens, is dit een algemeen vraagstuk waarvoor je voor alle instanties gewoon het asymptotisch optimale algoritme wil vinden, of zit je met een praktisch vraagstuk, waarvoor je maar 1 of enkele instanties hoeft op te lossen?

De reden waarom ik dit vraag is dat asymptotisch optimale algoritmen vaak niet optimaal hoeven te zijn voor minder dan belachelijk grote getallen. Plus dat de optimale algoritmen vaak ingewikkelder zijn dan minder optimale, en je dus uiteindelijk veel meer tijd kwijt bent in het uitwerken en debuggen ervan. Dus als je het slechts voor 1 of een paar instanties van het probleem hoeft uit te werken, kan het wel degelijk lonen om een minder-dan-optimaal algoritme toe te passen.

[Verwijderd]

MrBucket schreef op woensdag 23 februari 2005 @ 00:24:Trouwens, is dit een algemeen vraagstuk waarvoor je voor alle instanties gewoon het asymptotisch optimale algoritme wil vinden, of zit je met een praktisch vraagstuk, waarvoor je maar 1 of enkele instanties hoeft op te lossen?

De opdracht zelf geeft een voorbeeld van 7 personen en 32 objecten... Het leukste zou natuurlijk zijn om een algoritme te vinden/bedenken dat de optimale oplossing geeft, maar ik weet niet of dat haalbaar is.. Een heel goede benadering is denk ik ook al leuk.

[MrBucket]

Ok, off the top of my head _{en om 1 uur 's nachts...}:

Kies een constante C < 32, waarvoor je de objecten op een greedy manier gaat verdelen, de rest van de objecten wordt op alle mogelijke combinaties verdeeld. Zo kun je je zoekruimte (sterk) indammen.

Voor de objecten die je greedy gaat verdelen: sorteer ze op waarde, zodat degene met de hoogste waarde als eerste wordt behandeld, daarna die met de twee-na-hoogste waarde, enz. Laat de relatieve waarde W(p, o) van een object o voor een persoon p zodanig zijn dat het het verschil is tussen [zijn huidige procentuele waarde van alle bezittingen is die p is toegewezen] en [de beoogde procentuele waarde die p behoort te krijgen].

Plaats het gegeven object o bij die persoon, die de kleinste relatieve waarde voor die persoon tot gevolg heeft.