Harmonic bin packing
ہارمونک بن پیکنگ بن پیکنگ کے لیے آن لائن الگورتھم کا ایک خاندان ہے۔ اس طرح کے الگورتھم کا ان پٹ مختلف سائز کی اشیاء کی فہرست ہے۔ آؤٹ پٹ ایک پیکنگ ہے-اشیاء کو مقررہ گنجائش کے ڈبوں میں تقسیم کرنا، اس طرح کہ ہر ڈبے میں موجود اشیاء کے سائز کا مجموعہ زیادہ سے زیادہ گنجائش پر ہو۔ مثالی طور پر، ہم زیادہ سے زیادہ کم ڈبے استعمال کرنا چاہیں گے، لیکن ڈبوں کی تعداد کو کم کرنا ایک این پی سخت مسئلہ ہے۔ ہارمونک بن پیکنگ الگورتھم ہارمونک ترقی کے بعد اشیاء کو ان کے سائز کی بنیاد پر زمروں میں تقسیم کرنے پر انحصار کرتے ہیں۔ اس خیال کی کئی قسمیں ہیں۔ ہارمونک-کے الگورتھم سائز کے وقفے کو ہم آہنگی سے ٹکڑوں میں تقسیم کرتا ہے۔ کسی آئٹم کو-آئٹم، اگر کہا جاتا ہے۔ الگورتھم خالی ڈبوں کے سیٹ کو ہر آئٹم ٹائپ کے لیے ایک بن ٹائپ کے لیے لامحدود کلاسوں میں تقسیم کرتا ہے۔ قسم کا ڈبہ صرف قسم کی اشیاء کو پیک کرنے کے لیے ڈبے کے لیے استعمال ہوتا ہے۔ کے لیے ہر قسم کے ڈبے میں بالکل-آئٹمز ہو سکتے ہیں۔ الگورتھم اب اس طرح کام کرتا ہے: اگر اگلی آئٹم ایک-آئٹم کے لیے ہے، تو آئٹم کو پہلے (صرف کھلے) ڈبے میں رکھا جاتا ہے جس میں کم سے کم ٹکڑے ہوتے ہیں یا اگر ایسا کوئی ڈبہ موجود نہ ہو تو نیا کھولتا ہے۔ اگر اگلی آئٹم ایک-آئٹم ہے، تو الگورتھم اسے نیکسٹ فٹ کا استعمال کرتے ہوئے ٹائپ کے ڈبوں میں رکھتا ہے۔ اس الگورتھم کو سب سے پہلے لی اور لی نے بیان کیا تھا۔ اس میں وقت کی پیچیدگی ہے جہاں n ان پٹ آئٹمز کی تعداد ہے۔ ہر مرحلے پر، زیادہ سے زیادہ کھلے ڈبے ہوتے ہیں جو ممکنہ طور پر اشیاء کو رکھنے کے لیے استعمال کیے جا سکتے ہیں، یعنی یہ ایک کے-باؤنڈڈ اسپیس الگورتھم ہے۔ لی اور لی نے غیر علامتی تخمینہ تناسب کا بھی مطالعہ کیا۔ انہوں نے ایک ترتیب کی وضاحت کی، اور ثابت کیا کہ اس کے لیے یہ ہے۔ کیونکہ یہ اس کو برقرار رکھتا ہے۔ مزید برآں، انہوں نے اس ریفائنڈ ہارمونک (آر ایچ) کے لیے بدترین صورت حال کی مثالیں پیش کیں۔ ریفائنڈ ہارمونک ہارمونک-کے الگورتھم کے خیالات کو ریفائنڈ فرسٹ فٹ کے خیالات کے ساتھ جوڑتا ہے۔ یہ ریفائنڈ-فرسٹ-فٹ کی طرح بڑی اشیاء کو رکھتا ہے، جبکہ چھوٹی اشیاء کو ہارمونک-کے کا استعمال کرتے ہوئے رکھا جاتا ہے۔ اس حکمت عملی کا انترجشتھان ان ٹکڑوں پر مشتمل ڈبوں کے بڑے فضلے کو کم کرنا ہے جو صرف اس سے بڑے ہیں۔ الگورتھم درج ذیل وقفوں کے حوالے سے اشیاء کی درجہ بندی کرتا ہے:،،،، کے لیے، اور۔ الگورتھم-آئٹمز کو ہارمونک-کے کی طرح رکھتا ہے، جبکہ یہ اور میں آئٹمز کے لیے ایک مختلف حکمت عملی پر عمل کرتا ہے۔ ڈبوں میں اشیاء اور اشیاء کو پیک کرنے کے چار امکانات ہیں۔ این-بن میں صرف ایک آئٹم ہوتا ہے۔ این-بن میں صرف ایک آئٹم ہوتا ہے۔ ایک ڈبے میں ایک آئٹم اور ایک آئٹم ہوتا ہے۔ ایک ڈبے میں دو آئٹمز ہوتے ہیں۔ این-بن ایک ایسے ڈبے کی نشاندہی کرتا ہے جسے دوسری آئٹم پر مشتمل ہونے کے لیے نامزد کیا جاتا ہے۔ الگورتھم حل میں متعلقہ ڈبوں کی تعداد کو شمار کرنے کے لیے نمبر این اے، این بی، این اے بی، این بی بی، اور این بی کا استعمال کرتا ہے۔ مزید برآں، فہرست L = (i _ 1، \dotts i _ n): 1 کے لیے N _ c = N _ b + N _ ab الگورتھم ریفائنڈ-ہارمونک-k۔ N _ a = N _ b = N _ ab = N _ bb = N _ b '= N _ c = 02۔ اگر i _ j ایک I _ k-ٹکڑا ہے تو اسے پیک کرنے کے لیے الگورتھم ہارمونک-k کا استعمال کریں۔ ورنہ اگر i _ j ایک I _ a-آئٹم ہے تو اگر N _ b! = 1، تو i _ j کو کسی بھی J _ b-بن میں پیک کریں۔ N _ b-- ؛ N _ ab + + ؛ ورنہ i _ j کو ایک نئے (خالی) بن میں رکھیں۔ N _ a + + ؛ 4۔ ورنہ اگر i _ j ایک I _ b-آئٹم ہے تو اگر N _ b '= 1 تو i _ j کو I _ b'-بن میں رکھیں۔ N _ b '= 0 ؛ N _ bb + + ؛ 5۔ ورنہ اگر N _ bb <= 3N _ c ہو تو i _ b کو رکھیں۔ انہوں نے ثابت کیا کہ یہ اس کے لیے ہے۔ دیگر اقسام میں ترمیم شدہ ہارمونک (ایم ایچ) کا غیر علامتی تناسب ہے۔ تبدیل شدہ ہارمونک 2 (MH2) کا غیر علامتی تناسب ہے۔ ہارمونک + 1 (H + 1) کا غیر علامتی تناسب ہے۔ ہارمونک + + (H + +) کا غیر علامتی تناسب اور ہے۔ حوالہ جات بن پیکنگ