Yr arbenigwyr pecynnu o Mainz: rhif un ledled y byd
Curodd gwyddonwyr Mainz recordiau'r byd am y trefniant gorau o ddisgiau crwn - Cyhoeddiad yn Adolygiad Corfforol E.
Sut mae llwytho car fel bod popeth yn ffitio i mewn? Sut alla i bacio pecyn fel ei fod wedi'i lenwi'n iawn? Faint o lestri sy'n mynd mewn cabinet cegin? O ran pacio, mae gwyddonwyr Mainz yn ddiguro. Roeddent i gyd yn gallu gosod neu guro'r recordiau byd a osodwyd mewn cystadleuaeth ryngwladol i gael yr ateb gorau i broblem pacio arbennig."Rydyn ni wedi bod yn gweithio ers cryn amser mewn prosiect rhyngddisgyblaethol rhwng ffiseg ddamcaniaethol a gwyddoniaeth gyfrifiadurol i ddatblygu'r algorithm cyfrifiadurol gorau posib ar gyfer problemau pacio," eglura Dr. Johannes Josef Schneider o'r ffocws newydd ei sefydlu ar ddulliau ymchwil gyda chymorth cyfrifiadur yn y gwyddorau naturiol ym Mhrifysgol Johannes Gutenberg Mainz. Pan ddaeth y gwyddonwyr i wybod am y gystadleuaeth ychydig cyn iddi ddod i ben, dim ond un record byd y gallent ei gosod, fel arall roedd canlyniadau rhai grwpiau eraill ychydig yn well. Wedi'u gyrru gan yr uchelgais i guro grwpiau gorau'r byd, yr oedd rhai ohonynt wedi bod yn gweithio ar broblemau o'r fath ers blynyddoedd lawer, fe wnaethant ddatblygu eu algorithmau cyfrifiadurol ymhellach ac roeddent bellach yn gallu tanseilio cofnodion y byd a osodwyd yn ystod y gystadleuaeth, ac ar y cyfan yn sylweddol . Cyhoeddwyd y gwaith yn y cyfnodolyn enwog am ffiseg ystadegol Physical Review E.
Roedd y gystadleuaeth yn ymwneud â threfnu disgiau crwn o wahanol feintiau mewn cylch fel eu bod yn cymryd cyn lleied o le â phosib. Felly dylai radiws y cylch mawr y mae'r disgiau crwn llai yn cael ei bacio ynddo fod mor fach â phosib. Cymerodd 155 o grwpiau o 32 gwlad ran yn y gystadleuaeth a chyflwyno eu datrysiadau. Ar gyfer y problemau gyda 24 i uchafswm o 50 disg crwn o wahanol feintiau, Schneider, yr Athro Dr. Daeth Elmar Schömer o'r Sefydliad Cyfrifiadureg a'r myfyriwr graddedig André Müller o hyd i'r atebion gorau o bell ffordd. Ar gyfer y problemau llai gyda 23 o ddisgiau crwn a llai, roeddent yn cyfateb â'r atebion gorau hyd yn hyn - sy'n awgrymu na ellir cael datrysiad gwell fyth. "Rydym wedi datblygu algorithm pacio gorau'r byd ar gyfer y broblem hon gyda'r disgiau crwn o wahanol feintiau," mae'n crynhoi Schneider.
Fodd bynnag, mae'r gwyddonwyr nid yn unig yn ystyried problemau gwyddonol o'r fath, ond hefyd yn trosglwyddo eu algorithmau i gymwysiadau ymarferol. Er enghraifft, mae'r grŵp yn ymchwilio i'r ffordd orau o fesur cyfaint cefnffordd ar gyfer gwneuthurwr ceir mawr o'r Almaen. Yn ôl y safon a bennir gan yr Undeb Ewropeaidd, rhaid pacio Tetrapaks o faint penodol mewn cefnffordd benodol fel bod y gofod yn cael ei lenwi cystal â phosibl. "Hyd yn hyn, rydyn ni wedi ceisio rhoi cymaint o Tetrapaks â phosib yn eu lle gyda blociau pren," eglura Schneider. Yn UDA, ar y llaw arall, byddai'n rhaid pacio setiau cês dillad ar gyfer yr uwch-gyfoethog mor optimaidd â phosibl yn y gefnffordd, a dyna pam nad yw'r wybodaeth ar faint o le sydd yn y gefnffordd yn cyfateb yn union rhwng yr Almaen a'r Americanwr. pamffledi hysbysebu. Yn seiliedig ar y gymhariaeth â chanlyniadau'r gystadleuaeth, mae gan y gwyddonwyr bellach y sicrwydd y gall eu algorithm hefyd ddatrys y problemau pacio cefnffyrdd hyn yn y ffordd orau bosibl.
Gellir defnyddio algorithmau optimeiddio o'r fath hefyd ar gyfer cwestiynau hollol wahanol. Er enghraifft, gellir optimeiddio teithiau ffatri laeth i'r ffermydd fel bod y pellteroedd y mae'r tryciau yn eu gorchuddio i gasglu llaeth mor fyr â phosibl - yn dibynnu ar y drefn yr eir at y ffermydd. Enghraifft arall o'r diwydiant modurol yw'r cynulliad terfynol o gerbydau: gellir defnyddio'r cyfrifiadur i bennu'r drefn y mae'n rhaid dod â'r cyrff parod unigol i'r llinell ymgynnull fel y gellir cynhyrchu mor gost-effeithiol â phosibl. Mae yna hefyd gystadlaethau ar gyfer problemau o'r fath, ac mae cwmnïau'n trefnu rhai ohonynt hyd yn oed. Fel myfyriwr doethuriaeth yn Regensburg, cymerodd Schneider y pedwerydd safle ar ei ben ei hun mewn cystadleuaeth yr oedd gwneuthurwr ceir Bafaria wedi’i hysbysebu ychydig flynyddoedd yn ôl, gan adael cwmnïau sydd wedi’u sefydlu ym maes optimeiddio a chyflogi grwpiau cyfan o weithwyr ar gyfer y gystadleuaeth ymhell ar ôl.
Mae'r gwyddonwyr Mainz yn dod o hyd i'r dull datrysiad gorau trwy fynd at yr ateb. At y diben hwn, efelychir digwyddiadau ar hap ar y cyfrifiadur gydag efelychiadau Monte Carlo - a enwir ar ôl ardal Monaco gyda'r casino enwog. "Mae fel yn y casino, lle mae'r rhif deuddeg yn digwydd ar hap ar y bwrdd roulette, felly mae'r cyfrifiadur yn creu trefniant ar hap," eglura Schneider. Yn yr enghraifft gyda'r disgiau crwn, mae'r cyfrifiadur wedyn yn symud un o'r disgiau i rywle ac yn cymharu'r datrysiad newydd hwn â'r un blaenorol. Mae'r newid hwn yn cael ei wrthdroi os yw maint y dirywiad yn rhy fawr, fel arall mae'r datrysiad newydd yn parhau. "Yn y modd hwn rydych chi'n newid trefniant y disgiau crwn gam wrth gam, nes bod y canlyniad terfynol ar gael."
Mae'n amlwg bod gan atebion gwahanol sydd bron cystal â'r datrysiad gorau rywbeth yn gyffredin. Yn ôl Schneider, mae yna strwythurau sydd i'w cael yn aml. Yn y gystadleuaeth disg gylchol, er enghraifft, gyda'r datrysiadau da, mae'r disgiau crwn mwyaf yn aml yn agos at ei gilydd. Ymchwilir i'r union atebion da a'r ateb gorau yn gyffredin gan y gwyddonwyr yn eu papur eu hunain, a fydd hefyd yn ymddangos yn Adolygiad Corfforol E yn fuan.
Sefydlwyd y ffocws ar ddulliau ymchwil gyda chymorth cyfrifiadur yn y gwyddorau naturiol o'r newydd gan Brifysgol Johannes Gutenberg er mwyn cefnogi safle rhagorol y gwyddorau naturiol ym Mainz yn well trwy wyddoniaeth gyfrifiadurol effeithlon ac arloesol.
gwaith gwreiddiol:
André Müller, Johannes J. Schneider, Elmar Schömer Pacio system amlddisgyblaethol o ddisgiau caled mewn amgylchedd crwn Adolygiad Ffisegol E, Cyfrol 79, Rhif 021102, 2 Chwefror, 2009
Ffynhonnell: Mainz [JGU]
