مساله بسته بندی همبند: معرفی، مدلسازی و الگوریتم

مساله بسته بندی کلاسیک (BPP) به دلیل کاربردهای بسیار زیاد و ساختار ترکیبیاتی خوب آن به طور گسترده ای در ادبیات موضوع مورد توجه قرار گرفته است. روشهای حل دقیق و الگوریتم های تقریبی و ابتکاری زیادی برای آن ارائه گردیده است. از طرفی تعمیم های زیادی نیز برای مساله ارائه شده است. در بسیاری از کاربردهایی که با اشياء فضایی سرکار دارند ممکن است که برای قرار گرفتن اشیاء در کنار هم محدودیت مجاورت با همبندی ( مثل همبندی جغرافیایی نیز وجود داشته باشد. در این مقاله تعمیم جدیدی از مساله بسته بندی معرفی می شود که این حالت را نیز تحت پوشش قرار می دهد. در این مقاله بعد از معرفی دقیق مساله و مدلسازی ریاضی آن، یک الگوریتم تقریبی برای حل مساله وقتی گراف زمینه همیلتونی باشد ارائه می گردد. نشان داده می شود این الگوریتم دارای فاکتور تقریب ۲ بوده یک مثال نیز برای بسته بودن این فاکتور تقریب ارائه می شود

کلیدواژه ها:

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