بهترین روش برای برش کوکی های کریسمس چیست؟ – ScienceDaily


در برهه ای از زندگی ، اکثر مردم بالای یک صفحه نورد کوکی ایستاده اند و فکر کرده اند که چگونه می توان با کمترین زباله ، کوکی ها را برش داد. اکنون حتی ریاضیدانان برای یافتن یک الگوریتم رایانه برای پاسخگویی به این نوع مسئله هندسی منصرف شده اند.

چگونه می توانیم خمیر را در حین برش کوکی های کریسمس به حداکثر برسانیم؟ چگونه می توان چمدان را بست یا کابینت آشپزخانه را پر کرد و از فضا بهترین استفاده را کرد؟ ممکن است کسی فکر کرده باشد ، “برای این کار باید بهترین راه وجود داشته باشد.” به نظر می رسد فکر زیاد در مورد چنین مسائلی اتلاف وقت کامل است. اکنون علم برای حمایت از این واقعیت در دسترس است که در حال حاضر نمی توان فهمید که برای بیش از چهار یا پنج نوع شیرینی زنجفیلی تند یا درختان کریسمس بهترین نتیجه را دارد.

استادیار میکل آبراهامسن از دپارتمان علوم کامپیوتر و دو محقق محقق کشف کردند که انتخاب روش بهینه برای بسته بندی اشیا in در دو بعد بدون همپوشانی چقدر دشوار است ، رمز و رازی که دانشمندان علوم رایانه برای دهه ها از آن استقبال کرده اند.

“در حالی که الگوریتم ها به ما امکان حل جدی مشکلات پیچیده را می دهند ، این موردی است که برای رایانه های امروزی بیش از حد باقی مانده است. هنوز بسته بندی بهینه بیش از 5-10 شی yet امکان پذیر نیست. و ، نتیجه ما نشان می دهد که این تعداد احتمالاً هنوز در دسترس نیست. میکل آبراهامسن توضیح می دهد.

بسته بندی بهینه وسایل فقط یک مشکل تصادفی در خانه نیست ، بلکه در صنایع مختلفی از جمله تولید لباس و فلزکاری است. در هر صورت ، مهم است که مواد را با حداقل ضایعات تا حد ممکن برش دهید. در حمل و نقل ، این مربوط به بسته بندی ظروف است.

فقط چهار شیرینی زنجفیلی

ما اندازه کوچکترین ظرف مربعی را می دانیم که می توانیم در آن 10 پالت مربع 1×1 متر بسته بندی کنیم. اما فقط افزودن یک پالت اضافی محاسبه اندازه بهینه ظرف را غیر ممکن می کند. آبراهامسن توضیح می دهد:

“با افزودن پالت های بیشتر ، زمان محاسبات به طور تصاعدی افزایش می یابد. حتی بهترین رایانه ها نیز از پس این کار بر نمی آیند. از لحاظ تئوری امکان پذیر است. اما براساس سرعت افزایش قدرت محاسبات ، میلیون ها سال قبل از آن طول می کشد ما می توانیم پردازش چندین شی additional اضافی را بهینه کنیم. “

بعلاوه ، اگر کسی با اشکال پیچیده تری مانند نان شیرینی زنجفیلی به شکل درخت کریسمس کار کند ، میکل آبراهامسن می گوید که امروزه فقط برای چهار سایت می توان راه حل های بهینه را یافت.

تعداد بی نهایت گزینه

چه چیزی آن را دشوار می کند؟ آبراهامسن توضیح می دهد که این مسئله شبیه حل معادلات درجه پنج یا بالاتر و با بسیاری از ناشناخته ها است. در اینجا شناخته شده است که چنین راه حلی را همیشه نمی توان با کمک عملیات منظم حساب ثبت کرد.

“تحقیقات ما ثابت می کند که این مسئله دارای ویژگی است که ما در ریاضیات آن را پیوسته می نامیم – که به طور خلاصه بدان معنی است که فرد باید تمام مختصاتی را که می توان کوکی ها را در آن قرار داد و تمام زوایای چرخش آنها را بشناسد.” آبراهامسن توضیح می دهد.

از آنجا که ترکیب های احتمالی بی پایان هستند ، راهی برای ایجاد لیستی از تمام مکان های مورد نیاز برای آزمایش برای یافتن راه حل بهینه بسته بندی وجود ندارد. در عوض ، الگوریتم هایی که به طور بهینه مشکلات بسته بندی را حل می کنند ، باید تجزیه و تحلیل بیشتری داشته باشند که این کار زمان بر است. این در تضاد با بسیاری از مشکلات الگوریتمی شناخته شده دیگر است ، که در آن می توان تعداد محدودی ترکیب را قبل از یافتن یک ترکیب بهینه امتحان کرد. به این ترتیب ، مشکلات بسته بندی بسیار دشوارتر است.

بنابراین در واقع هیچ راه حلی بهتر از آنچه ما انسان ها تصور می کنیم برای مشکلات بسته بندی وجود ندارد.

وی گفت: “هم در صنعت و هم در پیشخوان آشپزخانه ، ما باید همچنان از راه حل های بهینه خود خوشحال باشیم و اطمینان حاصل كنیم كه ما انسان ها هنوز در این نوع كارها بهتر از رایانه هستیم – در حال حاضر.” میکل آبراهامسن.

واقعیت ها:

  • در علوم کامپیوتر و ریاضیات ، مشکلات بسته بندی دسته ای از مشکلات بهینه سازی است که شامل تلاش برای بسته بندی تعدادی از اشیا as در نزدیکترین زمان ممکن در دو یا سه بعد است. ریاضیدانان صدها سال است که با مشکلات بسته بندی دست و پنجه نرم می کنند.
  • با نتیجه جدید ، مشکل بسته بندی دو بعدی به یک طبقه بالاتر از پیچیدگی محاسباتی تبدیل شده است که ∃ℝ نشان داده می شود. پیش از این تصور می شد که این موضوع متعلق به کلاس NP باشد ، همراه با شناخته شده “مشکل فروشنده سفر” ، که مربوط به محاسبه کوتاهترین تور برای بازدید از تمام شهرهای موجود در یک لیست مشخص است.
  • این مطالعه توسط میکل آبراهامسن از مرکز BARC در دانشگاه کپنهاگ ، گروه علوم کامپیوتر انجام شد. تیلمن میلتسوف از دانشگاه اوترخت در هلند و ناجا سیفرت از دانشگاه آزاد برلین در آلمان. بودجه مطالعه ، از جمله بنیاد VILLUM بود.
  • این مطالعه در کنفرانس FOCS 2020 (سمپوزیوم IEEE در مبانی علوم کامپیوتر) ، که از 16 تا 19 نوامبر برگزار می شود ، ارائه شد.


منبع: khabar-erfan.ir

دیدگاهتان را بنویسید

Comment
Name*
Mail*
Website*