یک الگوریتم تقریبی چند جمله ای با ضریب تقریب 1/5 برای مسئله Bin Packing
Publish place: The Second National Conference on New Approaches in Computer and Electrical Engineering
Publish Year: 1395
نوع سند: مقاله کنفرانسی
زبان: Persian
View: 1,303
This Paper With 8 Page And PDF Format Ready To Download
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
BPJ02_056
تاریخ نمایه سازی: 11 آبان 1395
Abstract:
مسئله بسته بندی وزنه ها یکی از مهم ترین مسائل بهینه سازی تحقیق در عملیات است. که کاربردهای متفاوتی در زمینه های گوناگون دارد. در سال های اخیر، با توجه به ماهیت NP-hard این مسئله چندین الگوریتم تقریبی برای این مسئله ارائه شده اند. ثابت شده است که بهترین الگوریتم تقریبی ممکن برای مسئله بسته بندی وزنه ها ضریب تقریب 2/3 و مرتبه زمانی (n)O دارد مگر اینکه P=NP باشد. در این مقاله، یک الگوریتم تقریبی با مرتبه زمانی( O(nlogn و مرتبه حافظه ثابت مبنی بر ساختار درخت دودویی و یافتن میانه ارائه می شود. درنهایت، الگوریتم تقریبی پیشنهادی با سه الگوریتم تقریبی دیگر مبنی بر یک پایگاه داده استاندارد مقایسه می شوند. نتایج تجربی نشان می دهد که الگوریتم پیشنهادی عملکرد قابل قبولی دارد.
Keywords:
Authors
مهدیه فاریابی
گروه کامپیوتر، واحد بافت، دانشگاه آزاد اسلامی، بافت، ایران،
محسن فروغی نعمت الهی
گروه کامپیوتر، واحد بافت، دانشگاه آزاد اسلامی، بافت، ایران،
مراجع و منابع این Paper:
لیست زیر مراجع و منابع استفاده شده در این Paper را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود Paper لینک شده اند :