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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

واقعیت ها:

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


منبع: packge-news.ir

Leave a reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>