یک الگوریتم تقریبی چند جمله ای با ضریب تقریب 1/5 برای مسئله Bin Packing
سال انتشار: 1395
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 1,272
فایل این مقاله در 8 صفحه با فرمت PDF قابل دریافت می باشد
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
BPJ02_056
تاریخ نمایه سازی: 11 آبان 1395
چکیده مقاله:
مسئله بسته بندی وزنه ها یکی از مهم ترین مسائل بهینه سازی تحقیق در عملیات است. که کاربردهای متفاوتی در زمینه های گوناگون دارد. در سال های اخیر، با توجه به ماهیت NP-hard این مسئله چندین الگوریتم تقریبی برای این مسئله ارائه شده اند. ثابت شده است که بهترین الگوریتم تقریبی ممکن برای مسئله بسته بندی وزنه ها ضریب تقریب 2/3 و مرتبه زمانی (n)O دارد مگر اینکه P=NP باشد. در این مقاله، یک الگوریتم تقریبی با مرتبه زمانی( O(nlogn و مرتبه حافظه ثابت مبنی بر ساختار درخت دودویی و یافتن میانه ارائه می شود. درنهایت، الگوریتم تقریبی پیشنهادی با سه الگوریتم تقریبی دیگر مبنی بر یک پایگاه داده استاندارد مقایسه می شوند. نتایج تجربی نشان می دهد که الگوریتم پیشنهادی عملکرد قابل قبولی دارد.
کلیدواژه ها:
نویسندگان
مهدیه فاریابی
گروه کامپیوتر، واحد بافت، دانشگاه آزاد اسلامی، بافت، ایران،
محسن فروغی نعمت الهی
گروه کامپیوتر، واحد بافت، دانشگاه آزاد اسلامی، بافت، ایران،
مراجع و منابع این مقاله:
لیست زیر مراجع و منابع استفاده شده در این مقاله را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود مقاله لینک شده اند :