Pakar pembungkusan dari Mainz: Nombor satu di seluruh dunia

Para saintis Mainz mengalahkan rekod dunia untuk susunan cakera bulat terbaik - penerbitan dalam Kajian Fizikal E

Bagaimanakah saya memuatkan kereta supaya semuanya sesuai? Bagaimanakah saya boleh membungkus bungkusan supaya ia diisi dengan baik? Berapa banyak pinggan mangkuk yang terdapat di dalam almari dapur? Apabila bercakap tentang pembungkusan, saintis Mainz tidak dapat dikalahkan. Mereka semua menyamai atau menewaskan rekod dunia yang ditetapkan dalam pertandingan antarabangsa untuk penyelesaian terbaik kepada masalah pembungkusan tertentu.

"Kami telah mengusahakan projek antara disiplin antara fizik teori dan sains komputer untuk beberapa waktu untuk membangunkan algoritma komputer terbaik untuk masalah pembungkusan, " jelas Dr. Johannes Josef Schneider daripada fokus yang baru diasaskan pada kaedah penyelidikan berbantukan komputer dalam sains semula jadi di Universiti Johannes Gutenberg di Mainz. Apabila saintis kemudian mengetahui tentang pertandingan itu sejurus sebelum ia berakhir, mereka hanya mampu mencipta rekod dunia, jika tidak keputusan beberapa kumpulan lain lebih baik sedikit. Didorong oleh cita-cita untuk menewaskan kumpulan terbaik dunia, sebahagian daripada mereka telah mengusahakan masalah sedemikian selama bertahun-tahun, mereka mengembangkan lagi algoritma komputer mereka dan kini mampu mengatasi rekod dunia yang ditetapkan semasa pertandingan, dan dalam kebanyakan kes dengan ketara. Kerja itu diterbitkan dalam jurnal fizik statistik terkenal Physical Review E.

Pertandingan ini adalah mengenai menyusun cakera bulat dengan saiz yang berbeza dalam bulatan sedemikian rupa sehingga mereka mengambil sedikit ruang yang mungkin. Jejari bulatan besar di mana cakera yang lebih kecil dibungkus oleh itu hendaklah sekecil mungkin. 155 kumpulan dari 32 negara mengambil bahagian dalam pertandingan itu dan menyerahkan penyelesaian mereka. Bagi masalah dengan 24 hingga maksimum 50 cakera bulat dengan saiz yang berbeza, Schneider, Prof. Dr. Elmar Schömer dari Institut Sains Komputer dan pelajar siswazah André Müller menemui penyelesaian terbaik setakat ini. Untuk masalah yang lebih kecil dengan 23 cakera dan kurang, mereka setanding dengan penyelesaian terbaik setakat ini - yang menunjukkan bahawa tidak ada penyelesaian yang lebih baik. "Untuk masalah ini dengan cakera bulat bersaiz berbeza, kami telah membangunkan algoritma pembungkusan terbaik dunia," meringkaskan Schneider.

Walau bagaimanapun, para saintis bukan sahaja mempertimbangkan masalah saintifik sedemikian, tetapi juga memindahkan algoritma mereka kepada aplikasi praktikal. Sebagai contoh, kumpulan itu sedang menyiasat bagaimana isipadu batang boleh diukur dengan terbaik untuk pengeluar kereta Jerman yang besar. Mengikut piawaian yang ditetapkan oleh Kesatuan Eropah, Tetrapaks dengan saiz tertentu mesti dibungkus ke dalam batang tertentu sedemikian rupa sehingga ruang diisi sebanyak mungkin. "Sehingga kini, blok kayu telah digunakan untuk cuba menampung seberapa banyak Tetrapak yang mungkin," jelas Schneider. Di Amerika Syarikat, sebaliknya, set beg pakaian daripada orang kaya perlu dibungkus seoptimum mungkin di dalam bagasi, itulah sebabnya maklumat tentang berapa banyak ruang yang terdapat di dalam bagasi itu tidak sepadan antara Jerman dan Amerika. risalah pengiklanan. Berdasarkan perbandingan dengan keputusan pertandingan, para saintis kini mempunyai kepastian bahawa algoritma mereka juga boleh menyelesaikan masalah pembungkusan batang ini secara optimum.

Tetapi algoritma pengoptimuman sedemikian juga boleh digunakan untuk soalan yang sama sekali berbeza. Sebagai contoh, perjalanan dari kilang tenusu ke ladang boleh dioptimumkan supaya jarak yang dilalui trak untuk mengambil susu adalah sesingkat mungkin - bergantung pada susunan ladang didekati. Satu lagi contoh daripada industri automotif ialah pemasangan akhir kenderaan: Dengan bantuan komputer, ia boleh ditentukan mengikut susunan badan pasang siap individu perlu dibawa ke barisan pemasangan supaya pengeluaran dapat dijalankan secara kos efektif. yang mungkin. Terdapat juga pertandingan untuk masalah sedemikian, malah ada yang dianjurkan oleh syarikat. Sebagai pelajar kedoktoran di Regensburg, Schneider sahaja menduduki tempat keempat dalam pertandingan yang diadakan oleh pengeluar kereta Bavaria beberapa tahun lalu, meninggalkan syarikat yang ditubuhkan dalam bidang pengoptimuman dan menggaji seluruh kumpulan orang untuk pertandingan itu jauh di belakang .

Para saintis Mainz mencari kaedah penyelesaian terbaik dengan mendekati penyelesaian dengan mendekatinya. Untuk tujuan ini, acara rawak disimulasikan pada komputer dengan simulasi Monte Carlo - dinamakan sempena daerah Monaco dengan kasino terkenal. "Ia berfungsi seperti di kasino, di mana nombor dua belas secara rawak muncul di meja rolet, dan komputer secara rawak menjana susunan," jelas Schneider. Dalam contoh dengan cakera bulat, komputer kemudian memindahkan salah satu cakera ke suatu tempat dan membandingkan penyelesaian baharu ini dengan yang sebelumnya. Perubahan ini akan ditarik balik jika tahap kemerosotan terlalu tinggi, jika tidak, penyelesaian baharu akan kekal. "Dengan cara ini, anda menukar susunan cakera bulat langkah demi langkah sehingga anda mendapat keputusan akhir."

Adalah menarik perhatian bahawa penyelesaian berbeza yang hampir sama baik dengan penyelesaian terbaik selalunya mempunyai persamaan. Menurut Schneider, terdapat struktur yang biasa. Dalam pertandingan cakera bulat, sebagai contoh, cakera bulat terbesar selalunya berdekatan dalam penyelesaian yang baik. Apa sebenarnya persamaan penyelesaian yang baik dan penyelesaian terbaik ialah perkara yang sedang disiasat oleh saintis dalam kerja mereka sendiri, yang tidak lama lagi akan turut diterbitkan dalam Kajian Fizikal E.

Tumpuan untuk kaedah penyelidikan berbantukan komputer dalam sains semula jadi baru ditubuhkan oleh Universiti Johannes Gutenberg untuk menyokong kedudukan cemerlang sains semula jadi di Mainz dengan sains komputer yang berkuasa dan inovatif.

kerja asal:

André Müller, Johannes J. Schneider, Elmar Schömer Membungkus sistem cakera keras berbilang serakan dalam persekitaran bulat Kajian Fizikal E, Jilid 79, Nombor 021102, 2 Februari 2009

Sumber: Mainz [ JGU ]