First-fit-decreasing bin packing
فرسٹ فٹ ڈیکریزنگ (ایف ایف ڈی) بن پیکنگ کے لیے ایک الگورتھم ہے۔ اس کا ان پٹ مختلف سائز کی اشیاء کی فہرست ہے۔ اس کی پیداوار ایک پیکنگ ہے-اشیاء کو مقررہ گنجائش کے ڈبوں میں تقسیم کرنا، اس طرح کہ ہر ڈبے میں موجود اشیاء کے سائز کا مجموعہ زیادہ سے زیادہ گنجائش پر ہو۔ مثالی طور پر، ہم زیادہ سے زیادہ کم ڈبوں کا استعمال کرنا چاہیں گے، لیکن ڈبوں کی تعداد کو کم کرنا ایک این پی سخت مسئلہ ہے، لہذا ہم تقریبا بہترین ہیورسٹک کا استعمال کرتے ہیں۔ تفصیل ایف ایف ڈی الگورتھم مندرجہ ذیل طریقے سے کام کرتا ہے۔ اشیاء کو سب سے بڑے سے لے کر سب سے چھوٹے تک آرڈر کریں۔ ایک نیا خالی ڈبے، بن #1 کھولیں۔ سب سے بڑی سے لے کر سب سے چھوٹی ہر آئٹم کے لیے پہلا ڈبہ تلاش کریں جس میں آئٹم فٹ ہو، اگر ہو۔ اگر ایسا ڈبہ مل جائے تو اس میں نئی چیز ڈال دیں۔ ورنہ، ایک نیا خالی ڈبہ کھولیں اور اس میں نئی چیز ڈالیں۔ مختصرا: ایف ایف ڈی اشیاء کو نیچے کی طرف آرڈر کرتا ہے، اور پھر فرسٹ فٹ بن پیکنگ کو کال کرتا ہے۔ ایف ایف ڈی الگورتھم کی مساوی وضاحت مندرجہ ذیل ہے۔ اشیاء کو سب سے بڑے سے لے کر سب سے چھوٹے تک آرڈر کریں۔ جب کہ چیزیں باقی ہیں: ایک نیا خالی ڈبہ کھولیں۔ سب سے بڑی سے لے کر سب سے چھوٹی تک ہر آئٹم کے لیے: اگر یہ موجودہ ڈبے میں فٹ ہو سکتا ہے تو اسے داخل کریں۔ معیاری تفصیل میں، ہم اشیاء کو ایک بار لوپ کرتے ہیں، لیکن بہت سے ڈبے کھلے رکھتے ہیں۔ مساوی تفصیل میں، ہم اشیاء کو کئی بار لوپ کرتے ہیں، لیکن ہر بار صرف ایک کھلا ڈبہ رکھتے ہیں۔ کارکردگی کا تجزیہ ایف ایف ڈی کی کارکردگی کا تجزیہ کئی مراحل میں کیا گیا۔ ذیل میں، ان پٹ سیٹ S اور بن کی صلاحیت C کے لیے FFD کے ذریعے استعمال ہونے والے ڈبوں کی تعداد کی نشاندہی کی گئی ہے۔ 1973 میں، D. S. جانسن نے اپنے ڈاکٹریٹ کے مقالے میں ثابت کیا کہ کسی بھی صورت میں ایس اور صلاحیت سی۔ 1985 میں، بی ایس۔ بیکر نے تھوڑا سا آسان ثبوت دیا اور دکھایا کہ اضافی مستقل 3 سے زیادہ نہیں ہے۔ یوے منی نے ثابت کیا کہ 1991 میں اور 1997 میں، اس تجزیے کو لی رونگ ہینگ کے ساتھ مل کر بہتر بنایا۔ 2007 میں گیوگی ڈسا نے تنگ باؤنڈ کو ثابت کیا اور اس کے لیے ایک مثال پیش کی۔ بدترین صورت کی مثال ڈوسا کی طرف سے دی گئی نچلی باؤنڈ کی مثال درج ذیل ہے: دو بن کی ترتیبات پر غور کریں: ؛۔ اگر بہترین حل میں 4 کاپیاں اور 2 کاپیاں ہیں، تو ایف ایف ڈی مندرجہ ذیل ڈبوں کا حساب لگائے گا: ترتیب کے ساتھ 4 ڈبے، ترتیب کے ساتھ 1 ڈبے، ترتیب کے ساتھ 1 ڈبے، ترتیب کے ساتھ 1 ڈبے، ترتیب کے ساتھ 1 حتمی ڈبے، یعنی کل 8 ڈبے، جبکہ زیادہ سے زیادہ صرف 6 ڈبے ہوتے ہیں۔ لہذا، اوپری باؤنڈ تنگ ہے، کیونکہ۔ اس مثال کو تمام سائز تک بڑھایا جا سکتا ہے: زیادہ سے زیادہ ترتیب میں 9k + 6 ڈبے ہیں: 6k + 4 قسم B1 اور 3k + 2 قسم B2 کے۔ لیکن ایف ایف ڈی کو کم از کم 11 ہزار + 8 ڈبوں کی ضرورت ہوتی ہے۔ یکسانیت کی خصوصیات وجدان کے برعکس، سی کا یکسانیت فنکشن نہیں ہے۔ اسی طرح، ایس میں آئٹمز کے سائز کا یکسانیت فنکشن نہیں ہے: یہ ممکن ہے کہ کوئی آئٹم سائز میں سکڑ جائے، لیکن ڈبوں کی تعداد میں اضافہ ہو۔ تاہم، ایف ایف ڈی الگورتھم میں ایک "ایسمپٹوٹک مونوٹونیکیٹی" خاصیت ہے، جس کی تعریف مندرجہ ذیل ہے۔ ہر مثال S اور انٹیجر m کے لیے، من کیپ (S، m) کو سب سے چھوٹی صلاحیت C ہونے دیں تاکہ ہر انٹیجر m کے لیے، من ریشو (m) کو r ≤ 1 نمبروں کا لامحدود ہونا چاہیے تاکہ، تمام ان پٹ سیٹوں S کے لیے،۔ یہ وہ رقم ہے جس کے ذریعے ہمیں ڈبوں کو "پھولنے" کی ضرورت ہوتی ہے تاکہ ایف ایف ڈی ڈبوں کی زیادہ سے زیادہ تعداد حاصل کر سکے۔ پھر، ہر ان پٹ S کے لیے اور ہر r ≤ MinRatio (m) کے لیے،۔ یہ، خاص طور پر، ظاہر کرتا ہے کہ مندرجہ بالا تعریف میں لامحدود کو کم سے کم سے تبدیل کیا جا سکتا ہے۔ مثال کے طور پر، فرض کریں کہ ان پٹ: 44، 24، 24، 22، 21، 17، 8، 8، 6، 6 ہے۔ 60 کی گنجائش کے ساتھ، ایف ایف ڈی 3 ڈبے پیک کرتا ہے: 44، 8، 8 ؛ 24، 24، 6، 6 ؛ 22، 21، 17۔ لیکن گنجائش 61 کے ساتھ، ایف ایف ڈی 4 ڈبے پیک کرتا ہے: 44، 17 ؛ 24، 24، 8 ؛ 22، 21، 8، 6 ؛ 6۔ اس کی وجہ یہ ہے کہ، گنجائش 61 کے ساتھ، 17 پہلے ڈبے میں فٹ ہوجاتا ہے، اور اس طرح مندرجہ ذیل 8، 8 کا راستہ روکتا ہے۔ ایک اور مثال کے طور پر، فرض کریں کہ ان پٹ یہ ہیں: 51، 28، 28، 28، 27، 25، 12، 12، 10، 10، 10، 10، 10، 10، 10۔ 75 کی گنجائش کے ساتھ، ایف ایف ڈی 4 ڈبے پیک کرتا ہے: 51، 12، 12، 28، 28، 10، 28، 27، 10، 25، 10، 10، 10، 10، 10، 10 لیکن 76 کی گنجائش کے ساتھ، اسے 5 ڈبوں کی ضرورت ہے: 51، 25، 28، 28، 12، 28، 27، 12، 10، 10، 10، 10، 10، 10، 10، 10 10۔ اگر 17 16 ہو جاتا ہے، تو اس کے نتیجے میں پیکنگ: 44، 16 ؛ 24، 24، 8 ؛ 22، 21، 8، 6 ؛ 6 ہے۔ ماڈیفائیڈ فرسٹ فٹ ڈکریزنگ ماڈیفائیڈ فرسٹ فٹ ڈریسنگ (ایم ایف ایف ڈی) نصف ڈبے سے بڑی آئٹمز کے لیے ایف ایف ڈی میں بہتری لاتا ہے، جس میں آئٹمز کو سائز کے لحاظ سے چار سائز کی کلاسوں میں درجہ بندی کیا جاتا ہے، بڑی، درمیانے، چھوٹی اور چھوٹی، جو بالترتیب سائز> 1/2 ڈبے،> 1/3 ڈبے،> 1/6 ڈبے اور چھوٹی آئٹمز سے مطابقت رکھتی ہیں۔ پھر یہ پانچ مراحل سے گزرتا ہے: ہر بڑی چیز کے لیے ایک ڈبہ مختص کریں، جس کا آرڈر سب سے بڑا سے چھوٹا ہوتا ہے۔ ڈبوں کے ذریعے آگے بڑھیں۔ ہر ایک پر: اگر سب سے چھوٹی باقی درمیانی چیز فٹ نہیں ہوتی ہے تو اس ڈبے کو چھوڑ دیں۔ بصورت دیگر، سب سے بڑی باقی درمیانی چیز رکھیں جو فٹ ہو۔ ان ڈبوں کے ذریعے پیچھے کی طرف بڑھیں جن میں درمیانی چیز نہ ہو۔ ہر ایک پر: اگر دو سب سے چھوٹی باقی چھوٹی اشیاء فٹ نہیں ہوتیں تو اس ڈبے کو چھوڑ دیں۔ ورنہ، سب سے چھوٹی بقیہ چھوٹی چیز اور سب سے بڑی بقیہ چھوٹی چیز رکھیں جو فٹ ہو۔ تمام ڈبوں سے آگے بڑھیں۔ اگر کسی بھی سائز کی کلاس کی سب سے چھوٹی بقیہ چیز فٹ نہیں ہوتی ہے تو اس ڈبے کو چھوڑ دیں۔ ورنہ، سب سے بڑی چیز رکھیں جو فٹ ہو اور اس ڈبے پر رہیں۔ بقیہ اشیاء کو نئے ڈبوں میں پیک کرنے کے لیے ایف ایف ڈی کا استعمال کریں۔ اس الگورتھم کا سب سے پہلے 1985 میں جانسن اور گیری نے مطالعہ کیا، جہاں انہوں نے یہ ثابت کیا۔ اس حد کو سال 1995 میں یو اور ژانگ نے بہتر بنایا جس نے یہ ثابت کیا۔ دیگر اقسام بیسٹ فٹ ڈکریزنگ (بی ایف ڈی) ایف ایف ڈی سے بہت ملتی جلتی ہیں، سوائے اس کے کہ فہرست کو ترتیب دینے کے بعد، اس پر بہترین فٹ بن پیکنگ کے ذریعے کارروائی کی جاتی ہے۔ اس کا غیر علامتی تخمینہ تناسب ایف ایف ڈی-11/9 کے برابر ہے۔ نفاذ ازگر: پی آر ٹی پی پیکج میں فرسٹ فٹ ڈریسنگ کا نفاذ ہوتا ہے۔ ملٹی فٹ الگورتھم بھی دیکھیں-یکساں مشینوں کے شیڈولنگ کے لیے ایک الگورتھم، جو ایف ایف ڈی کو ذیلی روٹین کے طور پر استعمال کرتا ہے۔ حوالہ جات بن پیکنگ