یک الگوریتم مینیمال برای حل مساله ی کوله پشتی صفر و یک چندبعدی

سال انتشار: 1397
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 456

متن کامل این مقاله منتشر نشده است و فقط به صورت چکیده یا چکیده مبسوط در پایگاه موجود می باشد.
توضیح: معمولا کلیه مقالاتی که کمتر از ۵ صفحه باشند در پایگاه سیویلیکا اصل مقاله (فول تکست) محسوب نمی شوند و فقط کاربران عضو بدون کسر اعتبار می توانند فایل آنها را دریافت نمایند.

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این مقاله:

شناسه ملی سند علمی:

ICIORS11_057

تاریخ نمایه سازی: 30 دی 1397

چکیده مقاله:

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

کلیدواژه ها:

مساله کوله پشتی صفر و یک چندبعدی ، الگوریتم برنامه ریزی پویا ، ضرایب لاگرانژ ، هسته مینیمال

نویسندگان

علیرضا قنبری

دانشگاه پدافند هوایی خاتم الانبیاء(ص)، دانشکده علوم پایه، گروه ریاضی

امید طغرایی سمیرمی

دانشگاه پدافند هوایی خاتم الانبیاء(ص)، دانشکده علوم پایه، گروه ریاضی