Quadratic assignment problem
کواڈریٹک اسائنمنٹ مسئلہ (کیو اے پی) ریاضی میں اصلاح یا کارروائیوں کی تحقیق کی شاخ میں بنیادی مشترکہ اصلاح کے مسائل میں سے ایک ہے، سہولیات کے مقام کے مسائل کے زمرے سے جو سب سے پہلے کوپمینز اور بیک مین نے متعارف کرایا تھا۔ مسئلہ مندرجہ ذیل حقیقی زندگی کے مسئلے کا نمونہ ہے: n سہولیات کا ایک مجموعہ اور n مقامات کا ایک مجموعہ ہے۔ مقامات کے ہر جوڑے کے لیے، ایک فاصلہ متعین کیا جاتا ہے اور سہولیات کے ہر جوڑے کے لیے ایک وزن یا بہاؤ متعین کیا جاتا ہے (مثال کے طور پر، دونوں سہولیات کے درمیان نقل و حمل کی فراہمی کی مقدار)۔ مسئلہ یہ ہے کہ تمام سہولیات کو مختلف مقامات پر تفویض کیا جائے جس کا مقصد متعلقہ بہاؤ سے ضرب شدہ فاصلے کے مجموعے کو کم سے کم کرنا ہے۔ بدیہی طور پر، لاگت فنکشن ایک دوسرے کے درمیان زیادہ بہاؤ والی سہولیات کو ایک دوسرے کے قریب رکھنے کی ترغیب دیتا ہے۔ دشواری کا بیان اسائنمنٹ کے مسئلے سے ملتا جلتا ہے، سوائے اس کے کہ لاگت کی تقریب کواڈریٹک عدم مساوات کے لحاظ سے ظاہر کیا گیا ہے، لہذا یہ نام ہے۔ رسمی ریاضیاتی تعریف کواڈریٹک اسائنمنٹ کے مسئلے کی رسمی تعریف مندرجہ ذیل ہے: مساوی سائز کے دو سیٹوں، P ("سہولیات") اور L ("مقامات") کو دیکھتے ہوئے، وزن فنکشن w: P × P → R اور فاصلاتی فنکشن d: L × L → R کے ساتھ مل کر۔ بیجیکشن f: P → L ("اسائنمنٹ") تلاش کریں تاکہ لاگت فنکشن: کم سے کم ہو۔ عام طور پر وزن اور فاصلے کے افعال کو مربع حقیقی قدر والے میٹرکس کے طور پر دیکھا جاتا ہے، تاکہ لاگت کے فنکشن کو اس طرح لکھا جائے: میٹرکس نوٹیشن میں: جہاں پرموٹیشن میٹرکس کا سیٹ ہے، وزن میٹرکس ہے اور فاصلہ میٹرکس ہے۔ کمپیوٹیشنل پیچیدگی مسئلہ این پی-سخت ہے، اس لیے کثیر الجہتی وقت میں اس مسئلے کو حل کرنے کے لیے کوئی معلوم الگورتھم نہیں ہے، اور یہاں تک کہ چھوٹی مثالوں میں بھی طویل کمپیوٹیشن وقت کی ضرورت پڑ سکتی ہے۔ یہ بھی ثابت ہوا کہ اس مسئلے میں کسی بھی (مستقل) عنصر کے لیے کثیر الجہتی وقت میں چلنے والا تخمینہ الگورتھم نہیں ہے، جب تک کہ P = NP نہ ہو۔ ٹریولنگ سیلز مین مسئلہ (ٹی ایس پی) کو کیو اے پی کے ایک خاص معاملے کے طور پر دیکھا جا سکتا ہے اگر کوئی یہ فرض کرے کہ بہاؤ تمام سہولیات کو صرف ایک رنگ کے ساتھ جوڑتے ہیں، تمام بہاؤ کی ایک ہی غیر صفر (مستقل) قیمت ہوتی ہے اور تمام فاصلے ٹی ایس پی مثال کے متعلقہ فاصلے کے برابر ہوتے ہیں۔ معیاری مشترکہ اصلاح کے مسائل کے بہت سے دوسرے مسائل اس شکل میں لکھے جا سکتے ہیں۔ ایپلی کیشنز اصل پلانٹ لوکیشن فارمولیشن کے علاوہ، کیو اے پی پرنٹڈ سرکٹ بورڈ یا مائیکرو چپ پر باہم مربوط الیکٹرانک اجزاء کی جگہ کے مسئلے کے لیے ایک ریاضیاتی ماڈل ہے، جو الیکٹرانکس انڈسٹری میں کمپیوٹر ایڈیڈ ڈیزائن کی جگہ اور راستے کے مرحلے کا حصہ ہے۔ کواڈریٹک باٹلنیک اسائنمنٹ کا مسئلہ حوالہ جات نوٹ ذرائع A2.5: ND43، pg.218 بھی دیکھیں۔ بیرونی لنکس https://www.opt.math.tugraz.at/qaplib QAPLIB-ایک کواڈریٹک اسائنمنٹ پروبلم لائبریری http://www.wiomax.com/team/xie/maos-qap-quadratic-assignment-problem-project-portal MAOS-QAP-جاوا پر مبنی کواڈریٹک اسائنمنٹ پروبلم سولور https://CRAN.R-project.org/package=qap-R پیکیج qAP: کواڈریٹک اسائنمنٹ پروبلم کے لیے ہیورسٹکس https://apps.microsoft.com/store/detail/qapsolver/9N7WMCFB6NZZ-ونڈوز کے لیے میٹا ہیورسٹک QAP سولور 10/11 NP-سخت مسائل کا مجموعہ اصلاح