Multidimensional assignment problem
کثیر جہتی تفویض کا مسئلہ (ایم اے پی) ایک بنیادی مشترکہ اصلاح کا مسئلہ ہے جسے ولیم پیئرسکلا نے متعارف کرایا تھا۔ اس مسئلے کو لکیری اسائنمنٹ کے مسئلے کی عمومی شکل کے طور پر دیکھا جا سکتا ہے۔ الفاظ میں، مسئلہ کو اس طرح بیان کیا جا سکتا ہے: مسئلہ کی ایک مثال میں کئی ایجنٹ (یعنی کارڈینیلیٹی پیرامیٹر) اور کام کی متعدد خصوصیات (یعنی جہتی پیرامیٹر) جیسے ٹاسک، مشین، وقت کا وقفہ وغیرہ ہوتے ہیں۔ مثال کے طور پر، ایک ایجنٹ کو وقت کے وقفے Z کے دوران مشین Y پر ٹاسک X انجام دینے کے لیے تفویض کیا جا سکتا ہے۔ کسی بھی ایجنٹ کو کسی بھی قیمت پر منفرد کام کی خصوصیات کے کسی بھی امتزاج کے ساتھ کام انجام دینے کے لیے تفویض کیا جا سکتا ہے۔ یہ اخراجات ایجنٹ کی تفویض کی بنیاد پر ملازمت کی خصوصیات کے امتزاج کی بنیاد پر مختلف ہو سکتے ہیں-مخصوص کام، مشین، وقت کا وقفہ وغیرہ۔ مسئلہ یہ ہے کہ ایجنٹوں کو تفویض کرنے کی کل لاگت کو کم سے کم کیا جائے تاکہ ہر کام کی خصوصیت کے لیے ایجنٹوں کی تفویض ایک انجیکٹو فنکشن ہو، یا ایجنٹوں سے کسی دی گئی نوکری کی خصوصیت کے لیے ون ٹو ون فنکشن ہو۔ متبادل طور پر، گراف تھیوری کا استعمال کرتے ہوئے مسئلے کو بیان کرنا: کثیر جہتی تفویض کا مسئلہ وزن والے کثیر الجہتی گراف میں، کسی دیئے گئے سائز کا ملاپ تلاش کرنے پر مشتمل ہوتا ہے، جس میں کناروں کے وزن کا مجموعہ کم سے کم ہوتا ہے۔ رسمی تعریف اس مسئلے کی مختلف شکلیں ادب میں مل سکتی ہیں۔ لاگت کے افعال کا استعمال کرتے ہوئے، جہتی تفویض کا مسئلہ (یا ایم اے پی) مندرجہ ذیل طور پر بیان کیا جا سکتا ہے: دیئے گئے سیٹ، اور، مساوی سائز کے، مل کر لاگت کی صف یا کثیر جہتی وزن کے فنکشن کے ساتھ:، ترتیبات تلاش کریں: A → اس طرح کہ کل لاگت کا فنکشن: کم سے کم ہو۔ کثیر جہتی اسائنمنٹ مسئلہ (ایم اے پی) میں دو کلیدی پیرامیٹرز ہوتے ہیں جو کسی مسئلے کی مثال کے سائز کا تعین کرتے ہیں: جہتی پیرامیٹر کارڈینیلیٹی پیرامیٹر، جہاں میں عناصر کی تعداد کو ظاہر کرتا ہے۔ لاگت کی صف کا سائز پیرامیٹرز کے ساتھ ایم اے پی کی کسی بھی دشواری کی مثال میں اس کی مخصوص لاگت کی صف ہوتی ہے، جو مثال کے طور پر مخصوص اخراجات/وزن کے پیرامیٹرز پر مشتمل ہوتی ہے۔ لاگت کی صف کا سائز ہے۔ قابل عمل حل کی تعداد ایم اے پی کا قابل عمل علاقہ یا حل کی جگہ بہت بڑی ہے۔ قابل عمل حلوں کی تعداد (ایم اے پی مثال کا سائز) ایم اے پی پیرامیٹرز پر منحصر ہے۔ خاص طور پر۔ کمپیوٹیشنل پیچیدگی مسئلہ عام طور پر این پی سخت ہوتا ہے۔ دوسرے لفظوں میں، کثیر الجہتی وقت میں اس مسئلے کو حل کرنے کے لیے کوئی معلوم الگورتھم نہیں ہے، اور اس لیے یہاں تک کہ اعتدال پسند سائز (جہتی اور بنیادی پیرامیٹرز پر مبنی) کے مسائل کی مثالوں کو حل کرنے کے لیے ایک طویل کمپیوٹیشنل وقت کی ضرورت پڑ سکتی ہے۔ ایپلی کیشنز اس مسئلے کا اطلاق بہت سے ڈومینز میں پایا گیا: شیڈولنگ (پروڈکشن کے عمل) ملٹی سینسر ڈیٹا فیوژن ریکارڈ لنکج یا ملٹی پارٹیٹ اینٹیٹی ریزولوشن ابتدائی ذرہ طبیعیات چھوٹے پہننے کے قابل آلات والے بزرگوں میں زوال کا پتہ لگانا حوالہ جات مشترکہ اصلاح https://issuu.com/ostraky/docs/the_top_5_english_coursework_help_strategies_for_t