Next-fit bin packing
نیکسٹ فٹ بن پیکنگ کے لیے ایک آن لائن الگورتھم ہے۔ اس کا ان پٹ مختلف سائز کی اشیاء کی فہرست ہے۔ اس کی پیداوار ایک پیکنگ ہے-اشیاء کو مقررہ گنجائش کے ڈبوں میں تقسیم کرنا، اس طرح کہ ہر ڈبے میں موجود اشیاء کے سائز کا مجموعہ زیادہ سے زیادہ گنجائش پر ہو۔ مثالی طور پر، ہم زیادہ سے زیادہ کم ڈبے استعمال کرنا چاہیں گے، لیکن ڈبوں کی تعداد کو کم کرنا ایک این پی سخت مسئلہ ہے۔ نیکسٹ فٹ الگورتھم مندرجہ ذیل ہیورسٹک کا استعمال کرتا ہے: یہ ایک موجودہ ڈبے کو رکھتا ہے، جو ابتدائی طور پر خالی ہوتا ہے۔ جب کوئی آئٹم آتا ہے، تو یہ چیک کرتا ہے کہ آیا آئٹم موجودہ ڈبے میں فٹ بیٹھتا ہے یا نہیں۔ اگر یہ فٹ بیٹھتا ہے تو اسے اس کے اندر رکھا جاتا ہے۔ ورنہ، موجودہ ڈبے کو بند کر دیا جاتا ہے، ایک نیا ڈبے کو کھولا جاتا ہے اور آنے والی چیز کو اس نئے ڈبے کے اندر رکھا جاتا ہے۔ نیکسٹ فٹ ایک باؤنڈڈ اسپیس الگورتھم ہے-اسے کسی بھی وقت کھولنے کے لیے صرف ایک جزوی طور پر بھرا ہوا ڈبے کی ضرورت ہوتی ہے۔ الگورتھم کا مطالعہ ڈیوڈ ایس جانسن نے 1973 میں اپنے ڈاکٹریٹ کے مقالے میں کیا تھا۔ رن ٹائم نیکسٹ فٹ کے رننگ ٹائم کو اس سے محدود کیا جا سکتا ہے کہ فہرست میں آئٹمز کی تعداد کہاں ہے۔ تخمینہ تناسب این ایف (ایل) کے ذریعہ نیکسٹ فٹ کے ذریعہ استعمال ہونے والے ڈبوں کی تعداد، اور او پی ٹی (ایل) کے ذریعہ فہرست ایل کے لیے ممکنہ ڈبوں کی زیادہ سے زیادہ تعداد کو ظاہر کرتا ہے۔ پھر، ہر فہرست کے لیے، ثبوت کا انترجشتھان درج ذیل ہے۔ اس الگورتھم کے ذریعہ استعمال ہونے والے ڈبوں کی تعداد ڈبوں کی زیادہ سے زیادہ تعداد سے دوگنا سے زیادہ نہیں ہے۔ دوسرے لفظوں میں، 2 ڈبوں کا زیادہ سے زیادہ آدھا بھرا ہونا ناممکن ہے کیونکہ اس طرح کے امکان سے یہ ظاہر ہوتا ہے کہ کسی وقت بالکل ایک ڈبہ زیادہ سے زیادہ آدھا بھرا ہوا تھا اور زیادہ سے زیادہ سائز کی چیز کو ایڈجسٹ کرنے کے لیے ایک نیا کھولا گیا تھا۔ لیکن چونکہ پہلے والے میں کم از کم ایک جگہ ہے، الگورتھم کسی بھی آئٹم کے لیے نیا ڈبہ نہیں کھولے گا جس کا سائز زیادہ سے زیادہ ہو۔ بن سے زیادہ بھرنے کے بعد ہی یا اگر اس سے بڑی سائز کی کوئی چیز آتی ہے تو الگورتھم ایک نیا بن کھول سکتا ہے۔ اس طرح اگر ہمارے پاس ڈبے ہوں تو کم از کم ڈبے آدھے سے زیادہ بھرے ہوتے ہیں۔ اس لیے۔ کیونکہ زیادہ سے زیادہ قیمت کی کم حد ہے، ہم اسے حاصل کرتے ہیں اور اسی وجہ سے۔ زیریں باؤنڈ ہر ایک کے لیے، ایک فہرست موجود ہے جیسے کہ اور۔ فہرستوں کا وہ خاندان جس کے لیے اس کے پاس ہے جو ساتھ کے ذریعہ دیا گیا ہے۔ اس فہرست کے لیے بہترین حل میں ڈبے ہوتے ہیں جن میں سائز کے ساتھ دو آئٹمز ہوتے ہیں اور ایک ڈبے میں سائز کے ساتھ آئٹمز ہوتے ہیں (یعنی کل ڈبے)، جبکہ این ایف کے ذریعے تیار کردہ حل میں ڈبے ہوتے ہیں جن میں ایک آئٹم سائز کی اور ایک آئٹم سائز کی ہوتی ہے۔ باؤنڈڈ آئٹم سائز اگر کسی آئٹم کا زیادہ سے زیادہ سائز ہے، تو اسمپٹوٹک تخمینہ تناسب مطمئن ہوتا ہے: سب کے لیے ؛ سب کے لیے۔ دیگر خصوصیات نیکسٹ فٹ ایک فہرست اور اس کے الٹا کو اسی تعداد میں ڈبوں میں پیک کرتا ہے۔ نیکسٹ-کے-فٹ (این کے ایف) نیکسٹ-کے-فٹ نیکسٹ-فٹ کا ایک متغیر ہے، لیکن صرف ایک ڈبے کو کھلا رکھنے کے بجائے، الگورتھم آخری ڈبے کو کھلا رکھتا ہے اور پہلے ڈبے کا انتخاب کرتا ہے جس میں آئٹم فٹ ہوتا ہے۔ کیونکہ، این کے ایف ایسے نتائج فراہم کرتا ہے جو این ایف کے نتائج کے مقابلے میں بہتر ہوتے ہیں، تاہم، مستقل اقدار تک بڑھ کر الگورتھم کو اس کے بدترین رویے میں مزید بہتر نہیں کرتا ہے۔ اگر الگورتھم ایک آلموسٹ اینی فٹ الگورتھم ہے اور پھر۔ نیکسٹ فٹ ڈکریزنگ (این ایف ڈی) نیکسٹ فٹ کا آف لائن ورژن ہے: یہ تمام ان پٹ آئٹمز کو قبول کرتا ہے، انہیں نزولی سائز کے ذریعے آرڈر کرتا ہے، اور نیکسٹ فٹ کو کال کرتا ہے۔ اس کا غیر علامتی تخمینہ تناسب بہت بہتر ہے: 2 کے بجائے 1.7 سے کم۔ حوالہ جات بن پیکنگ