1. #1

    Registered
    20/11/13
    Location
    Keerbergen
    Posts
    1
    iTrader
    0
    Mentioned
    0 Post(s)
    Reputation
    0/0

    Question 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
    no votes  

  2. #2
    Racemaniac's Avatar
    Registered
    27/07/02
    Location
    Merksem
    Posts
    3,397
    iTrader
    0
    Mentioned
    0 Post(s)
    Reputation
    0/3
    Quote Originally Posted by joranh View Post
    This quote is hidden because you are ignoring this member. Show
    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.
    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
    Quote Originally Posted by joranh View Post
    This quote is hidden because you are ignoring this member. Show
    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
    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 .
    Carmageddon 0wn4ge!!!!
    steun de virtuele perpetuum mobile part 1-10(dood ) part B --|-- Expert op gebied van Rode Blokskes
    all ph33r teh mighty strijksmiley --|-- zo herkent ge een echte TNG'er --|-- help ons de wereld te veroveren!
    no votes  

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  

Log in

Log in