Stacker crane problem
مشترکہ اصلاح میں، اسٹیکر کرین کا مسئلہ ایک اصلاح کا مسئلہ ہے جو ٹریول سیلز پرسن کے مسئلے سے قریب سے متعلق ہے۔ اس کا ان پٹ میٹرک اسپیس میں پوائنٹس کے ترتیب شدہ جوڑوں کے مجموعے پر مشتمل ہوتا ہے، اور اس کا مقصد ان پوائنٹس کو کم سے کم کل لمبائی کے چکر میں جوڑنا ہے جس میں تمام جوڑے شامل ہوتے ہیں، جو ایک دوسرے کے ساتھ مستقل طور پر مبنی ہوتے ہیں۔ یہ ایک اسٹیکر کرین، تعمیراتی کرین یا (ڈریج میں) ٹرک کے ذریعے کارگو کے انفرادی بوجھ کے پک اپ اور ڈیلیوری کے شیڈولنگ کے مسائل کو ان ڈیلیوری کے وقت پر رکاوٹوں کے بغیر آسان شکل میں ماڈل کرتا ہے۔ اسے ان پٹ جوڑوں کی ماڈلنگ کرنے والے ہدایت شدہ کناروں اور ان کے فاصلے کی ماڈلنگ کرنے والے غیر ہدایت شدہ کناروں کے ساتھ مخلوط گراف کے لحاظ سے مساوی تشکیل کے ساتھ متعارف کرایا گیا تھا۔ فریڈرکسن اور دیگر۔ اس کی تشکیل کا سہرا ڈینیل جے روزنکرانٹز کی ذاتی بات چیت کو جاتا ہے۔ اسٹیکر کرین کے مسئلے کو میٹرک جگہوں پر ٹریول سیلز پرسن کے مسئلے کی عمومی شکل کے طور پر دیکھا جا سکتا ہے: ٹریول سیلز پرسن کے مسئلے کی کسی بھی مثال کو اسٹیکر کرین کے مسئلے کی مثال میں تبدیل کیا جا سکتا ہے، جس میں ٹریول سیلز مین کے مثال میں ہر پوائنٹ کے لیے ایک جوڑا ہوتا ہے۔ دوسری سمت میں، اسٹیکر کرین کے مسئلے کو غیر متناسب ٹریولنگ سیلز پرسن کے مسئلے کے ایک خاص معاملے کے طور پر دیکھا جا سکتا ہے، جہاں غیر متناسب ٹریولنگ سیلز پرسن کے مسئلے کے نکات اسٹیکر کرین کے مثال کے جوڑے ہیں اور ایک جوڑے سے دوسرے جوڑے تک کا فاصلہ پہلے جوڑے کے ڈیلیوری پوائنٹ سے، اس کے پک اپ پوائنٹ کے ذریعے، دوسرے جوڑے کے ڈیلیوری پوائنٹ تک کے فاصلے کے طور پر لیا جاتا ہے۔ چونکہ یہ ٹریول سیلز پرسن کے مسئلے کو عام کرتا ہے، اس لیے اسے وہی کمپیوٹیشنل پیچیدگی وراثت میں ملتی ہے: یہ این پی سخت ہے، اور کم از کم اتنا ہی مشکل ہے جتنا کہ تخمینہ لگانا۔ ٹریول سیلز پرسن کے مسئلے کے لیے کرسٹوفائڈز الگورتھم پر مبنی ایک تخمینہ الگورتھم اسٹیکر کرین کے مسئلے کے حل کا تخمینہ 9/5 کے تخمینہ تناسب کے اندر لگا سکتا ہے۔ استعمال شدہ دھاگے کی کل مقدار کو کم سے کم کرنے کے لیے کڑھائی کے پیٹرن کے پچھلے حصے کو ڈیزائن کرنے کا مسئلہ اسٹیکر کرین کے مسئلے سے گہرا تعلق رکھتا ہے، لیکن یہ اس کے ہر جوڑے کے نکات (پیٹرن کے اگلے حصے پر نظر آنے والے ٹانکے کے سروں) کو کسی بھی سمت میں عبور کرنے کی اجازت دیتا ہے، بجائے اس کے کہ ٹریورسل کو تمام جوڑوں سے مستقل سمت میں گزرنا پڑے۔ یہ ٹریول سیلز پرسن کے مسئلے سے اسی تبدیلی کی وجہ سے این پی سخت ہے، اور 2 کے تخمینہ تناسب کے اندر اس کا تخمینہ لگایا جا سکتا ہے۔ اسٹیکر کرین کے مسئلے کی ایک اور تبدیلی، جسے ڈائل-اے-رائیڈ مسئلہ کہا جاتا ہے، کسی گاڑی کے لیے پک اپس اور ڈیلیوری کا مجموعہ انجام دینے کے لیے کم سے کم راستہ مانگتا ہے جبکہ اسے اپنے راستے کے ساتھ کسی بھی مقام پر کچھ تعداد میں بوجھ رکھنے کی اجازت دیتا ہے۔ حوالہ جات ٹریول سیلز مین کا مسئلہ