The pakki sérfræðingar frá Mainz: Heimurinn númer eitt
Mainz University slá heimsmet fyrir bestu fyrirkomulag hringlaga diskur - útgáfu í Physical Review E
Eins og ég hlaða bíl, þannig að allt passar? Hvernig get ég sett pakka þannig að það er vel fyllt? Hversu mikið borðbúnaður kemur í eldhús skáp? Þegar það kemur að pökkun, eru Mainz vísindamenn ósigrandi. Heimurinn færslur sem settar hafa verið upp í alþjóðlegri samkeppni um bestu lausn fyrir tiltekna pökkun vandamál, gætu þeir stilla eða berja alla.„Við höfum unnið um nokkurt skeið í þverfaglegu verkefni milli fræðilegrar eðlisfræði og tölvunarfræði við að þróa bestu mögulegu tölvureiknirit fyrir pökkunarvandamál,“ útskýrir Dr. Johannes Josef Schneider frá nýstofnaðri áherslu á tölvustuddar rannsóknaraðferðir í náttúruvísindum við Johannes Gutenberg háskólann í Mainz. Þegar vísindamennirnir komust að samkeppninni skömmu áður en henni lauk gátu þeir aðeins sett eitt heimsmet, annars var árangur sumra annarra hópa aðeins betri. Drifin áfram af metnaðinum til að sigra bestu hópa heims, sem sumir höfðu unnið að slíkum vandamálum í mörg ár, þróuðu þeir tölvualgoritma sína enn frekar og gátu nú slegið undir heimsmetin sem sett voru í keppninni og að mestu leyti verulega. Verkið var birt í hinu virta tímariti fyrir tölfræðilega eðlisfræði Physical Review E.
Keppnin snerist um að raða hringlaga diskum af mismunandi stærðum í hring svo þeir taki sem minnst pláss. Radíus stóra hringsins sem smærri hringdiskunum er pakkað í ætti því að vera eins lítill og mögulegt er. 155 hópar frá 32 löndum tóku þátt í keppninni og lögðu fram lausnir sínar. Fyrir vandamálin með 24 að hámarki 50 hringlaga diska af mismunandi stærðum, Schneider, prófessor Dr. Elmar Schömer frá tölvunarfræðistofnun og framhaldsneminn André Müller fundu langbestu lausnirnar. Fyrir minni vandamálin með 23 hringlaga diska og færri voru þau á pari við bestu lausnirnar hingað til - sem bendir til þess að það geti ekki verið enn betri lausn. „Við höfum því þróað bestu pökkunaralgoritma heims fyrir þetta vandamál með hringlaga diska af mismunandi stærðum“, dregur Schneider saman.
Vísindamennirnir íhuga ekki aðeins slík vísindaleg vandamál, heldur flytja einnig reiknirit þeirra yfir í hagnýt forrit. Til dæmis er hópurinn að kanna bestu leiðina til að mæla rúmmál skottinu fyrir stóran þýskan bílaframleiðanda. Samkvæmt staðlinum sem Evrópusambandið tilgreinir verður Tetrapaks af ákveðinni stærð að vera pakkað í tiltekinn skottinu svo að rýmið fyllist sem best. „Hingað til höfum við reynt að setja sem flesta Tetrapaks með trékubbum,“ útskýrir Schneider. Í Bandaríkjunum þyrfti hins vegar að pakka ferðatöskusettum fyrir ofurríku sem best í skottinu og þess vegna passa upplýsingar um hversu mikið pláss er í skottinu ekki nákvæmlega milli þýskra og amerískra auglýsingabæklinga. Byggt á samanburðinum við samkeppnisúrslitin geta vísindamennirnir nú verið vissir um að reiknirit þeirra getur einnig leyst þessi vandamál með farangurspökkun best.
En slíkar hagræðingarreiknirit geta einnig verið notaðar við allt aðrar spurningar. Til dæmis er hægt að fínstilla ferðir mjólkurverksmiðju til bæjanna þannig að vegalengdir sem vörubílar fara til að safna mjólk séu eins stuttir og mögulegt er - allt eftir því í hvaða röð er nálgast búin. Annað dæmi úr bílaiðnaðinum er lokasamsetning ökutækja: Með hjálp tölvunnar er hægt að ákvarða í hvaða röð þarf að koma einstökum forsmíðuðum aðilum á færibandið svo hægt sé að framkvæma sem hagkvæmastan hátt. Einnig er keppt um slík vandamál, sum eru jafnvel skipulögð af fyrirtækjum. Sem doktorsnemi í Regensburg náði Schneider fjórða sætinu einum í keppni sem bílaframleiðandi Bæjaralands hafði tilkynnt fyrir nokkrum árum og lét eftir sig fyrirtæki sem eru stofnuð á sviði hagræðingar og ráða heilu hópa starfsmanna í keppnina .
Vísindamenn Mainz finna bestu lausnaraðferðina með því að nálgast lausnina. Í þessum tilgangi eru hermdir tilviljanakenndir í tölvunni með Monte Carlo eftirlíkingum - nefndar eftir hverfi Mónakó með hinu fræga spilavíti. „Þetta er eins og í spilavítinu, þar sem talan tólf gerist af handahófi á rúllettuborðinu, þannig að tölvan myndar handahófi fyrirkomulag,“ útskýrir Schneider. Í dæminu með hringlaga diskana færir tölvan síðan annan diskinn einhvers staðar og ber þessa nýju lausn saman við þann fyrri. Þessari breytingu er snúið við ef umfang versnunarinnar er of mikið, annars er nýja lausnin eftir. „Á þennan hátt breytir þú fyrirkomulagi hringlaga diskanna skref fyrir skref þar til lokaniðurstaðan liggur fyrir.“
Það er áberandi að mismunandi lausnir sem eru næstum eins góðar og besta lausnin eiga oft eitthvað sameiginlegt. Samkvæmt Schneider eru til mannvirki sem oft finnast. Í hringlaga diskakeppninni, til dæmis með góðu lausnunum, eru stærstu hringlaga diskarnir oft nálægt sér. Hvað nákvæmlega góðu lausnirnar og besta lausnin eiga sameiginlegt er rannsakað af vísindamönnunum í eigin pappír, sem einnig mun birtast í Physical Review E innan skamms.
Áherslan á tölvustuddar rannsóknaraðferðir í náttúruvísindum var nýstofnað af Johannes Gutenberg háskólanum til að styðja betur við framúrskarandi stöðu náttúruvísindanna í Mainz með skilvirkum og nýstárlegum tölvufræði.
Original rit:
André Müller, Johannes J. Schneider, Elmar Schömer Pökkun á margdreifu harðdiskkerfi í hringlaga umhverfi Physical Review E, 79. bindi, númer 021102, 2. febrúar 2009
Heimild: Mainz [JGU]
