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

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

Keywords:

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