First-fit bin packing
فرسٹ فٹ (ایف ایف) بن پیکنگ کے لیے ایک آن لائن الگورتھم ہے۔ اس کا ان پٹ مختلف سائز کی اشیاء کی فہرست ہے۔ اس کی پیداوار ایک پیکنگ ہے-اشیاء کو مقررہ گنجائش کے ڈبوں میں تقسیم کرنا، اس طرح کہ ہر ڈبے میں موجود اشیاء کے سائز کا مجموعہ زیادہ سے زیادہ گنجائش پر ہو۔ مثالی طور پر، ہم زیادہ سے زیادہ کم ڈبے استعمال کرنا چاہیں گے، لیکن ڈبوں کی تعداد کو کم کرنا ایک این پی سخت مسئلہ ہے۔ فرسٹ فٹ الگورتھم مندرجہ ذیل ہیورسٹک کا استعمال کرتا ہے: یہ کھلے ڈبوں کی فہرست رکھتا ہے، جو ابتدائی طور پر خالی ہے۔ جب کوئی آئٹم آئے تو پہلا ڈبہ تلاش کریں جس میں آئٹم فٹ ہو سکتا ہے، اگر کوئی ہو۔ اگر ایسا ڈبہ مل جائے تو نئی چیز اس کے اندر رکھی جاتی ہے۔ ورنہ، ایک نیا ڈبہ کھولا جاتا ہے اور آنے والی چیز کو اس کے اندر رکھا جاتا ہے۔ تخمینہ تناسب ایف ایف (ایل) کے ذریعے فرسٹ فٹ کے ذریعے استعمال ہونے والے ڈبوں کی تعداد اور او پی ٹی (ایل) کے ذریعے فہرست ایل کے لیے ممکنہ ڈبوں کی زیادہ سے زیادہ تعداد کو ظاہر کرتا ہے۔ ایف ایف (ایل) کا تجزیہ کئی مراحل میں کیا گیا تھا۔ ایف ایف کے لیے پہلی اوپری حد 1971 میں المین نے ثابت کی تھی۔ 1972 میں، اس اوپری حد کو گیری، گراہم اور المین، جانسن اور ڈیمرز نے بہتر بنایا۔ 1976 میں، اس میں گیری، گراہم، جانسن، یاؤ اور چی-چیہ نے بہتری لائی، جو اور کی یکجہتی کی وجہ سے برابر ہے۔ اگلی بہتری، 2010 میں ژیا اور ٹین کی طرف سے، حد کو کم کر دیا۔ آخر کار، 2013 میں، اس حد کو ڈوسا اور سگل نے بہتر بنایا۔ وہ ایک مثال ان پٹ لسٹ بھی پیش کرتے ہیں، جس کے لیے اس باؤنڈ سے میل کھاتا ہے۔ ذیل میں ہم ثبوت کے خیال کی وضاحت کرتے ہیں۔ غیر علامتی تناسب زیادہ سے زیادہ 2 یہاں اس بات کا ثبوت ہے کہ غیر علامتی تناسب زیادہ سے زیادہ 2 ہے۔ اگر کوئی ایف ایف بن ہے جس کی رقم 1/2 سے کم ہے، تو باقی تمام اشیاء کا سائز 1/2 سے زیادہ ہے، لہذا مندرجہ ذیل تمام ڈبوں کا مجموعہ 1/2 سے زیادہ ہے۔ لہذا، زیادہ سے زیادہ ایک کے علاوہ تمام ایف ایف ڈبوں کی رقم کم از کم 1/2 ہوتی ہے۔ تمام بہترین ڈبوں کا مجموعہ زیادہ سے زیادہ 1 ہوتا ہے، لہذا تمام سائز کا مجموعہ زیادہ سے زیادہ او پی ٹی ہوتا ہے۔ لہذا، ایف ایف ڈبوں کی تعداد زیادہ سے زیادہ 1 + او پی ٹی/(1/2) = 2 * او پی ٹی + 1 غیر علامتی تناسب زیادہ سے زیادہ 1.75 ہے۔ پہلے ایک خاص معاملے پر غور کریں جس میں تمام آئٹم کے سائز زیادہ سے زیادہ 1/2 ہوں۔ اگر کوئی ایف ایف بن ہے جس کی رقم 2/3 سے کم ہے، تو باقی تمام اشیاء کا سائز 1/3 سے زیادہ ہے۔ چونکہ سائز زیادہ سے زیادہ 1/2 ہوتے ہیں، اس لیے مندرجہ ذیل تمام ڈبوں میں (شاید آخری کے علاوہ) کم از کم دو آئٹم ہوتے ہیں، اور رقم 2/3 سے بڑی ہوتی ہے۔ لہذا، زیادہ سے زیادہ ایک کے علاوہ تمام ایف ایف ڈبوں میں کم از کم 2/3 کا مجموعہ ہوتا ہے، اور ایف ایف ڈبوں کی تعداد زیادہ سے زیادہ 2 + او پی ٹی/(2/3) = 3/2 * او پی ٹی + 1 ہوتی ہے۔ "دشواری زدہ" اشیاء وہ ہیں جن کا سائز 1/2 سے بڑا ہے۔ لہذا، تجزیہ کو بہتر بنانے کے لیے، آئیے 1/2 سے بڑی ہر آئٹم کو آر کا بونس دیں۔ کسی آئٹم کے وزن کو اس کے سائز اور اس کے بونس کے طور پر بیان کریں۔ اشیاء کے ایک سیٹ کے وزن کو اس کے مندرجات کے وزن کے مجموعے کے طور پر بیان کریں۔ اب، ایک آئٹم کے ساتھ ہر ایف ایف بن کا وزن (زیادہ سے زیادہ ایک کے علاوہ) کم از کم 1/2 + آر ہے، اور دو یا زیادہ آئٹمز کے ساتھ ہر ایف ایف بن کا وزن (زیادہ سے زیادہ ایک کے علاوہ) 2/3 ہے۔ R = 1/6 لینے سے یہ نتیجہ نکلتا ہے کہ تمام FF ڈبوں کا وزن کم از کم 2/3 ہے۔ دوسری طرف، زیادہ سے زیادہ پیکنگ میں ہر ڈبے کا وزن زیادہ سے زیادہ 1 + R = 7/6 ہوتا ہے، کیونکہ اس طرح کے ہر ڈبے میں زیادہ سے زیادہ ایک چیز 1/2 سے بڑی ہوتی ہے۔ لہذا، تمام اشیاء کا کل وزن زیادہ سے زیادہ 7/6 * او پی ٹی ہے، اور ایف ایف ڈبوں کی تعداد زیادہ سے زیادہ 2 + (7/6 * او پی ٹی/(2/3)) = 7/4 * او پی ٹی + 2 ہے۔ غیر علامتی تناسب زیادہ سے زیادہ 1.7 مندرجہ ذیل ثبوت سے اخذ کیا گیا ہے۔ کسی ان پٹ آئٹم کے وزن کی وضاحت اس طرح کریں کہ آئٹم کا سائز x کچھ بونس درج ذیل شمار کیا گیا ہے: غیر علامتی تخمینہ کا تناسب دو دعووں سے ملتا ہے: زیادہ سے زیادہ پیکنگ میں، ہر ڈبے کا وزن زیادہ سے زیادہ 17/12 ہوتا ہے ؛ فرسٹ فٹ پیکنگ میں، ہر ڈبے کا اوسط وزن کم از کم 5/6 = 10/12 ہوتا ہے۔ لہذا، غیر علامتی طور پر، ایف ایف پیکنگ میں ڈبوں کی تعداد زیادہ سے زیادہ 17/10 * او پی ٹی ہونی چاہیے۔ دعوی 1 کے لیے، یہ ثابت کرنا کافی ہے کہ، کسی بھی سیٹ B کے لیے زیادہ سے زیادہ 1 کی رقم کے ساتھ، بونس (B) زیادہ سے زیادہ 5/12 ہے۔ درحقیقت: اگر B کے پاس 1/2 سے بڑی کوئی چیز نہیں ہے، تو اس میں 1/6 سے بڑی زیادہ سے زیادہ پانچ اشیاء ہیں، اور ان میں سے ہر ایک کا بونس زیادہ سے زیادہ 1/12 ہے۔ اگر B کے پاس 1/2 سے بڑی چیز ہے لیکن [1/3,1 2] میں کوئی چیز نہیں ہے، تو اس میں (1/6,1 3) میں زیادہ سے زیادہ دو اشیاء کے لیے گنجائش ہے، اور ان کے بونس کا مجموعہ زیادہ سے زیادہ (1/2/2-1/6) = 1/12 ہے، لہذا کل بونس 4/12 + 1/12 = 5/12 ہے۔ اگر B کے پاس 1/2 سے بڑی آئٹم اور [1/3,1 2] میں کوئی آئٹم ہے، تو اس میں 1/6 سے بڑے سائز کی آئٹمز کے لیے مزید گنجائش نہیں ہے، اس لیے کل بونس دوبارہ 4/12+1 12 = 5/12 ہے۔ لہذا، B کا وزن زیادہ سے زیادہ 1 + 5/12 = 17/12 ہے۔ دعوی 2 کے لیے، پہلے کسی ایک آئٹم کے ساتھ ایف ایف بن بی پر غور کریں۔ اگر رقم (بی) <1/2 ہے، تو-جس طرح سے ایف ایف کام کرتا ہے-بی کے بعد پروسیس شدہ تمام آئٹمز 1/2 سے بڑی ہونی چاہئیں (بصورت دیگر انہیں بی میں داخل کیا جاتا)۔ لہذا، زیادہ سے زیادہ ایک ایف ایف بن ہے جس کی رقم <1/2 ہے۔ اب رقم (B)> 1/2 کے ساتھ ایک آئٹم کے ساتھ دیگر تمام ڈبے B پر غور کریں۔ ان تمام ڈبوں کے لیے وزن (B)> 1/2+1 3 = 5/6 ہے۔ اب دو یا زیادہ اشیاء کے ساتھ ایف ایف ڈبے بی پر غور کریں۔ اگر رقم (B) <2/3 ہے، تو-جس طرح سے FF کام کرتا ہے-B کے بعد پروسیس شدہ تمام آئٹمز 1/3 سے بڑی ہونی چاہئیں (بصورت دیگر انہیں B میں داخل کیا جاتا)۔ لہذا، دو یا زیادہ اشیاء والے مندرجہ ذیل تمام ڈبے 2/3 سے بڑے ہوتے ہیں۔ لہذا زیادہ سے زیادہ ایک ایف ایف بن ہے جس میں دو یا زیادہ آئٹمز اور رقم <2/3 ہے۔ اب دو یا زیادہ آئٹمز والے دیگر تمام ڈبوں پر غور کریں اور رقم> 2/3 کریں۔ انہیں B [1]، B [2]،. B [k] سے نشان زد کریں، جس ترتیب سے وہ کھولے جاتے ہیں۔ 1،.، k میں ہر ایک i کے لیے، ہم ثابت کرتے ہیں کہ B [i] کا مجموعہ اور B [i + 1] کا بونس کم از کم 5/6 ہے: مجموعہ (B [i]) + بونس (B [i + 1])> = 5/6۔ درحقیقت، اگر مجموعہ (B [i])> = 5/6 ہے تو عدم مساوات معمولی ہے۔ ورنہ، جمع کریں (B [i]): = 1-x۔ نوٹ کریں کہ x 1/6 اور 2/6 کے درمیان ہے، کیونکہ مجموعہ (B [i]) 2/3 اور 5/6 کے درمیان ہے۔ چونکہ B [i + 1] کو B [i] کے بعد کھولا جاتا ہے، B [i + 1] میں کم از کم دو آئٹمز ہوتے ہیں، جیسے کہ c1 اور c2، جو B [i] میں فٹ نہیں ہوتے، یعنی: c1، c2> 1-sum (B [i]) = x> 1/6۔ پھر c1 اور c2 میں سے ہر ایک کا بونس کم از کم x/2-1/12 ہے۔ لہذا، B [i + 1] کا بونس کم از کم x-1/6 ہے، لہذا مجموعہ (B [i]) + بونس (B [i + 1])> = (1-x) + (x-1/6) = 5/6 ہے۔ ہم مذکورہ بالا عدم مساوات کو لگاتار جوڑوں پر لاگو کر سکتے ہیں، اور حاصل کر سکتے ہیں: مجموعہ (B [1]) + بونس (B [2]) + مجموعہ (B [2]) + بونس (B [3]) + + مجموعہ (B [k-1]) + بونس (B [k])> = 5/6 * (k-1)۔ لہذا، تمام ایف ایف ڈبوں کا کل وزن کم از کم 5/6 * (ایف ایف-3) ہے (جہاں ہم ایک آئٹم کے لیے 3 کو رقم <1/2 کے ساتھ، واحد دو آئٹم کے لیے رقم <2/3 کے ساتھ، اور دو آئٹم کے ڈبوں سے کے-1 کو رقم> = 2/3 کے ساتھ گھٹاتے ہیں)۔ مجموعی طور پر، ہمیں وہ 17/12 * OPT> = 5/6 * (FF-3) ملتا ہے، لہذا FF <= 17/10 * OPT + 3۔ ڈسا اور سگل ایک سخت تجزیہ پیش کرتے ہیں جو 3 سے چھٹکارا حاصل کرتا ہے، اور اس FF <= 17/10 * OPT کو حاصل کرتا ہے۔ زیریں باؤنڈ ایسی مثالیں ہیں جن پر 1.7OPT کی کارکردگی کا باؤنڈ تنگ ہے۔ مندرجہ ذیل مثال پر مبنی ہے۔ بن کی گنجائش 101 ہے، اور: ترتیب یہ ہے: 6 (x7)، 10 (x7)، 16 (x3)، 34 (x10)، 51 (x10)۔ بہترین پیکنگ میں 10 ڈبے ہوتے ہیں: [51+34 + 16] (x3)، [51+34 + 10+6] (x7)۔ تمام بن کی رقم 101 ہے۔ فرسٹ فٹ پیکنگ میں 17 ڈبے ہوتے ہیں: [6 (x7) + 10 (x5)]، [10 (x2) + 16 (x3)]، [34+34] (x5)، [51] (x10)۔ بن کے مجموعے یہ ہیں: 92، 68، 68 (x5)، 51 (x10)۔ انعامات (101 پر عام) 0، 0، 16.8 (x5)، 33.7 (x10) ہیں۔ کل وزن (101 پر معمول) 92، 68، 84.8 (x5)، 84.7 (x10) ہیں۔ یہ دیکھا جا سکتا ہے کہ تقریبا تمام وزن 101 * 5/6 = 84.1 کے قریب ہیں۔ ریفائنڈ فرسٹ فٹ ریفائنڈ فرسٹ فٹ (آر ایف ایف) بن پیکنگ کے لیے ایک اور آن لائن الگورتھم ہے، جو پہلے تیار کردہ ایف ایف الگورتھم میں بہتری لاتا ہے۔ اسے اینڈریو چی چی یاؤ نے پیش کیا تھا۔ الگورتھم آئٹمز کو ان کے سائز کے مطابق چار کلاسوں میں درجہ بندی کیا گیا ہے (جہاں ڈبے کی گنجائش 1 ہے):-پیس-سائز میں۔ - ٹکڑا-سائز میں۔ - ٹکڑا-سائز میں۔ - ٹکڑا-سائز میں۔ اسی طرح ڈبوں کو چار زمروں میں تقسیم کیا گیا ہے: 1، 2، 3 اور 4۔ ایک فکسڈ انٹیجر ہونے دیں۔ اگلی آئٹم کو ایک ڈبے میں تفویض کیا جاتا ہے-کلاس 1، اگر ایک ٹکڑا ہے، کلاس 2، اگر ایک ٹکڑا ہے، کلاس 3، اگر ایک ٹکڑا ہے، لیکن کسی بھی عدد کے لیے اب تک دیکھا گیا تیسرا ٹکڑا نہیں۔ کلاس 1، اگر اب تک دیکھا گیا چوتھا ٹکڑا ہے، کلاس 4، اگر ایک ٹکڑا ہے۔ ایک بار جب آئٹم کی کلاس کا انتخاب ہو جاتا ہے، تو اسے فرسٹ فٹ بن پیکنگ کا استعمال کرتے ہوئے اس کلاس کے ڈبوں کے اندر رکھا جاتا ہے۔ نوٹ کریں کہ آر ایف ایف کوئی فٹ الگورتھم نہیں ہے کیونکہ یہ ایک نیا ڈبہ کھول سکتا ہے اس حقیقت کے باوجود کہ موجودہ آئٹم ایک کھلے ڈبے (کسی اور کلاس سے) کے اندر فٹ بیٹھتا ہے۔ تخمینہ تناسب آر ایف ایف کی تخمینہ ضمانت ہے۔ فار کے ساتھ فہرستوں کا ایک خاندان موجود ہے۔ فرسٹ فٹ ڈکریزنگ (ایف ایف ڈی) فرسٹ فٹ کا آف لائن ورژن ہے: یہ تمام ان پٹ آئٹمز کو قبول کرتا ہے، انہیں نزولی سائز کے ذریعے آرڈر کرتا ہے، اور فرسٹ فٹ کو کال کرتا ہے۔ اس کا غیر علامتی تخمینہ تناسب بہت بہتر ہے: 1.7 کے بجائے تقریبا 1.222۔ نفاذ ازگر: پی آر ٹی پی پیکج میں فرسٹ فٹ کا نفاذ ہوتا ہے۔ حوالہ جات بن پیکنگ