Archief - Circle Packing (CPLEX/Mathlab?)

Hallohallo,

Ben volledig nieuw op dit forum, doorwezen door een vriend, en hoop hier iemand te vinden die me wat kan helpen bij een probleem.

Het probleem gaat als volgt;
Je hebt 1 grote 'container cirkel' met straal 215.
Vervolgens krijg je 50 kleinere cirkels gaand van straal 1 tot 50.
De bedoeling is een zo groot mogelijk oppervlak te bedekken met de 50 cirkels zonder dat deze overlappen of uit de container cirkel treden.

Heb hier ondertussen al wat opzoekingswerk over verricht;
Het is een NP-hard probleem wat betekent dat een optimale oplossing niet bestaat.
Je kan verschillende papers vinden die heuristieken aanraden maar ik zie niet hoe deze te coderen.

Is iemand vertrouwd met dit probleem? Of heeft iemand even tijd om met mij de heuristieken te bekijken? Op codeervlak heb ik vrij spel gekregen (of het nu Mathlab, CPLEX, Python... is), maar ik ken geen van deze programma's goed genoeg om dit te realiseren.
Op hoop van zege!

Mvg,
Joran

joranh zei:

Hallohallo,

Ben volledig nieuw op dit forum, doorwezen door een vriend, en hoop hier iemand te vinden die me wat kan helpen bij een probleem.

Het probleem gaat als volgt;
Je hebt 1 grote 'container cirkel' met straal 215.
Vervolgens krijg je 50 kleinere cirkels gaand van straal 1 tot 50.
De bedoeling is een zo groot mogelijk oppervlak te bedekken met de 50 cirkels zonder dat deze overlappen of uit de container cirkel treden.

Heb hier ondertussen al wat opzoekingswerk over verricht;
Het is een NP-hard probleem wat betekent dat een optimale oplossing niet bestaat.

Klik om te vergroten...

Ehm nee, dat betekent gewoon dat de moeilijkheid om op te lossen exponentieel groeit, en dat ge voor een groot probleem gewoon onmogelijk veel bewerkingen nodig hebt om de ideale oplossing te bekomen.

En hoe zijt ge er op uit gekomen dat het NP hard is? deel ons de informatie die ge al hebt, dat we niet al uw werk moeten overdoen

joranh zei:

Je kan verschillende papers vinden die heuristieken aanraden maar ik zie niet hoe deze te coderen.

Is iemand vertrouwd met dit probleem? Of heeft iemand even tijd om met mij de heuristieken te bekijken? Op codeervlak heb ik vrij spel gekregen (of het nu Mathlab, CPLEX, Python... is), maar ik ken geen van deze programma's goed genoeg om dit te realiseren.
Op hoop van zege!

Mvg,
Joran

Klik om te vergroten...

en m'n eerste instinct bij zo'n soort problemen zou zijn kijken of er niet een ander gekend probleem is waar al goede heuristieken/benaderende oplossing voor bestaan die ge kunt herleiden tot een oplossing voor dit probleem. voor veel klassieke np harde / np complete problemen zijn er al goede dingen beschikbaar. als dat voor uw probleem niet is, maar ge kunt een ander soort np hard/compleet probleem maken waarvan ge de oplossing makkelijk kunt omzetten naar uw probleem, dan zijt ge veel met de heuristieken die er voor dat probleem al zijn .