Best-fit bin packing
بیسٹ فٹ بن پیکنگ کے لیے ایک آن لائن الگورتھم ہے۔ اس کا ان پٹ مختلف سائز کی اشیاء کی فہرست ہے۔ اس کی پیداوار ایک پیکنگ ہے-اشیاء کو مقررہ گنجائش کے ڈبوں میں تقسیم کرنا، اس طرح کہ ہر ڈبے میں موجود اشیاء کے سائز کا مجموعہ زیادہ سے زیادہ گنجائش پر ہو۔ مثالی طور پر، ہم زیادہ سے زیادہ کم ڈبے استعمال کرنا چاہیں گے، لیکن ڈبوں کی تعداد کو کم کرنا ایک این پی سخت مسئلہ ہے۔ بہترین فٹ الگورتھم مندرجہ ذیل ہیورسٹک کا استعمال کرتا ہے: یہ کھلے ڈبوں کی فہرست رکھتا ہے، جو ابتدائی طور پر خالی ہوتا ہے۔ جب کوئی آئٹم آتا ہے، تو اسے زیادہ سے زیادہ بوجھ والا ڈبہ ملتا ہے جس میں آئٹم فٹ ہو سکتا ہے، اگر کوئی ہو۔ اگر ایسا ڈبہ مل جائے تو نئی چیز اس کے اندر رکھی جاتی ہے۔ ورنہ، ایک نیا ڈبہ کھولا جاتا ہے اور آنے والی چیز کو اس کے اندر رکھا جاتا ہے۔ تخمینہ تناسب بی ایف (ایل) کے ذریعے بیسٹ فٹ کے ذریعے استعمال ہونے والے ڈبوں کی تعداد اور او پی ٹی (ایل) کے ذریعے فہرست ایل کے لیے ممکنہ ڈبوں کی زیادہ سے زیادہ تعداد کو ظاہر کرتا ہے۔ بی ایف (ایل) کا تجزیہ کئی مراحل میں کیا گیا تھا۔ پہلی اوپری باؤنڈ 1971 میں المین نے ثابت کی تھی۔ گیری، گراہم اور المین، جانسن اور ڈیمرز نے ایک بہتر اوپری باؤنڈ ثابت کیا۔ اس کے بعد، اس میں گیری، گراہم، جانسن، المین، یاؤ اور چی-چی نے بہتری لائی۔ آخر کار اس باؤنڈ کو ڈوسا اور سگل نے بہتر بنایا۔ وہ ایک مثال ان پٹ لسٹ بھی پیش کرتے ہیں، جس کے لیے اس باؤنڈ سے میل کھاتا ہے۔ بدترین فٹ سب سے زیادہ فٹ ہونے کے لیے ایک "دوہری" الگورتھم ہے: یہ اگلی چیز کو کم سے کم بوجھ کے ساتھ ڈبے میں ڈالنے کی کوشش کرتا ہے۔ یہ الگورتھم نیکسٹ فٹ کی طرح برا برتاؤ کر سکتا ہے، اور اس کے لیے بدترین کیس کی فہرست میں ایسا کرے گا۔ اس کے علاوہ، یہ اس کو برقرار رکھتا ہے. چونکہ ورسٹ فٹ ایک اینی فٹ الگورتھم ہے، اس لیے ایک اینی فٹ الگورتھم موجود ہے۔ حوالہ جات بن پیکنگ