Mixed Chinese postman problem
مخلوط چینی پوسٹ مین مسئلہ (ایم سی پی پی یا ایم سی پی) عمودی V کے سیٹ کے ساتھ گراف کے مختصر ترین ٹریورسل کی تلاش ہے، مثبت عقلی وزن کے ساتھ غیر ہدایت شدہ کناروں E کا ایک سیٹ، اور مثبت عقلی وزن کے ساتھ ہدایت شدہ آرکس A کا ایک سیٹ جو کم سے کم قیمت پر کم از کم ایک بار ہر کنارے یا آرک کا احاطہ کرتا ہے۔ یہ مسئلہ پاپاڈیمیٹریو کے ذریعہ این پی مکمل ثابت ہوا ہے۔ مخلوط چینی پوسٹ مین کا مسئلہ اکثر آرک روٹنگ کے مسائل جیسے برف کی جوتی میں پیدا ہوتا ہے، جہاں کچھ سڑکیں دونوں سمتوں میں گزرنے کے لیے بہت تنگ ہوتی ہیں جبکہ دوسری سڑکیں دو طرفہ ہوتی ہیں اور دونوں سمتوں میں جوتی جا سکتی ہیں۔ یہ چیک کرنا آسان ہے کہ آیا مخلوط گراف میں کسی بھی سائز کا پوسٹ مین ٹور ہے یا نہیں، اس بات کی تصدیق کرکے کہ آیا گراف مضبوطی سے جڑا ہوا ہے۔ مسئلہ این پی مشکل ہے اگر ہم پوسٹ مین ٹور کو ہر آرک کو بالکل ایک بار عبور کرنے تک محدود رکھیں یا اگر ہم اسے ہر کنارے کو بالکل ایک بار عبور کرنے تک محدود رکھیں، جیسا کہ زرگوزا مارٹنیز نے ثابت کیا ہے۔ ریاضیاتی تعریف ریاضیاتی تعریف یہ ہے: ان پٹ: ہر کنارے کی لاگت اور زیادہ سے زیادہ لاگت کے ساتھ ایک مضبوطی سے جڑا ہوا، مخلوط گراف۔ سوال: کیا کوئی (ہدایت شدہ) ٹور ہے جو ہر کنارے اور ہر آرک کو کم از کم ایک بار میں عبور کرتا ہے اور اس میں زیادہ سے زیادہ لاگت آتی ہے؟ کمپیوٹیشنل پیچیدگی مخلوط چینی پوسٹ مین کے مسئلے کو حل کرنے میں بنیادی مشکل (غیر ہدایت شدہ) کناروں کے لیے سمتوں کا انتخاب کرنے میں ہے جب ہمیں اپنے دورے کے لیے ایک تنگ بجٹ دیا جاتا ہے اور ہم صرف ایک بار ہر کنارے کو عبور کرنے کے متحمل ہوتے ہیں۔ اس کے بعد ہمیں کناروں کو سمت دینا ہوگا اور کچھ مزید آرکس شامل کرنا ہوں گے تاکہ ایک ہدایت شدہ یولیرین گراف حاصل کیا جا سکے، یعنی ہر سرے کو متوازن بنایا جا سکے۔ اگر ایک سرے پر متعدد کنارے واقع ہوتے ہیں، تو ہر کنارے کی صحیح سمت کا تعین کرنا آسان کام نہیں ہے۔ ریاضی دان پاپاڈیمیٹریو نے مزید پابندیوں کے ساتھ اس مسئلے کا تجزیہ کیا ؛ "مکسڈ چینی پوسٹ مین این پی مکمل ہے، چاہے ان پٹ گراف طیارہ دار ہو، ہر سرے کی ڈگری زیادہ سے زیادہ تین ہو، اور ہر کنارے اور آرک کی قیمت ایک ہو۔" یولیرین گراف یہ جانچنے کا عمل کہ آیا مخلوط گراف یولیرین ہے، مخلوط چینی پوسٹ مین کے مسئلے کو حل کرنے کے لیے الگورتھم بنانے کے لیے اہم ہے۔ ایک مخلوط گراف G کی ڈگریاں یولیرین سائیکل کے لیے یکساں ہونی چاہئیں، لیکن یہ کافی نہیں ہے۔ تخمینہ یہ حقیقت کہ مخلوط چینی پوسٹ مین این پی-ہارڈ ہے، کثیر الجہتی وقت کے الگورتھم کی تلاش کا باعث بنی ہے جو معقول حد تک زیادہ سے زیادہ حل تک پہنچتے ہیں۔ فریڈرکسن نے 3/2 کے عنصر کے ساتھ ایک طریقہ تیار کیا جس کا اطلاق پلانر گراف پر کیا جا سکتا ہے، اور راگھوچاری اور ویراسامی نے ایک ایسا طریقہ دریافت کیا جس کا پلانر ہونا ضروری نہیں ہے۔ تاہم، کثیر الجہتی وقت سر قلم کرنے کی لاگت کو تلاش نہیں کر سکتا، سڑکوں تک پہنچنے میں جس وقت برف کا ہل لگتا ہے وہ ہل کرے گا یا سڑکوں تک پہنچنے کے لیے اسٹریٹ سویپر جھاڑ دے گا۔ رسمی تعریف ایک ورٹیکس سیٹ کے ساتھ مضبوطی سے منسلک مخلوط گراف، اور ایج سیٹ، ایک آرک سیٹ اور ہر ایک کے لیے غیر منفی لاگت کو دیکھتے ہوئے، ایم سی پی پی کم از کم ایک بار ہر لنک سے گزرنے والے کم سے کم لاگت والے دورے کو تلاش کرنے پر مشتمل ہوتا ہے۔ دیا گیا،،، اور میں بالکل ایک اختتامی نقطہ کے ساتھ کناروں کے سیٹ کی نشاندہی کرتا ہے۔ ایک ورٹیکس کو دیکھتے ہوئے، (انڈیگری) آرکس کے داخل ہونے کی تعداد کی نشاندہی کرتا ہے، (آؤٹ ڈگری) چھوڑنے والے آرکس کی تعداد ہے، اور (ڈگری) ان لنکس کی تعداد ہے جن کے ساتھ واقعہ ہوتا ہے۔ اس بات کو نوٹ کریں۔ ایک مخلوط گراف کو اس صورت میں بھی کہا جاتا ہے جب اس کے تمام عمودی حصوں کی ڈگری یکساں ہو، اسے ہم آہنگی کہا جاتا ہے اگر ہر عمودی حصے کے لیے، اور اسے متوازن کہا جاتا ہے اگر، عمودی حصوں کے کسی بھی ذیلی سیٹ کو دیکھتے ہوئے، آرکس کی تعداد کے درمیان فرق، اور آرکس کی تعداد، جو اس سے ہدایت کی جاتی ہے، شامل ہونے والے غیر سمت والے کناروں کی تعداد سے زیادہ نہیں ہے اور،۔ یہ ایک معروف حقیقت ہے کہ ایک مخلوط گراف یولیرین ہے اگر اور صرف اس صورت میں جب وہ یکساں اور متوازن ہو۔ نوٹ کریں کہ اگر یکساں اور ہم آہنگ ہے، تو G بھی متوازن ہے (اور یولیرین)۔ مزید برآں، اگر یکساں ہے، تو اسے بالکل کثیر الجہتی وقت میں حل کیا جا سکتا ہے۔ یہاں تک کہ ایم سی پی پی الگورتھم ایک یکساں اور مضبوطی سے جڑے ہوئے مخلوط گراف کو دیکھتے ہوئے، عین مطابق طور پر ایک ہی لاگت کے ساتھ کناروں کو سمت تفویض کرکے حاصل کردہ آرکس کا مجموعہ ہونے دیں۔ ہدایت شدہ گراف میں ہر سرے i کے لیے حساب لگائیں۔ کے ساتھ ایک ورٹیکس کو سپلائی ڈیمانڈ کے ساتھ ایک ماخذ (سنک) سمجھا جائے گا۔ نوٹ کریں کہ جیسا کہ ایک یکساں گراف ہے، تمام رسد اور مطالبات یکساں اعداد ہیں (صفر کو یکساں نمبر سمجھا جاتا ہے)۔ ان متعلقہ کناروں کی لاگت کے ساتھ اور ان کے ساتھ مخالف سمت میں آرکس کا سیٹ ہونے دیں، اور صفر لاگت پر متوازی آرکس کا سیٹ ہونے دیں۔ تمام عمودی حصوں کے مطالبات کو پورا کرنے کے لیے، گراف میں کم از کم لاگت کے بہاؤ کے مسئلے کو حل کریں، جس میں ہر آرک میں لامحدود صلاحیت ہوتی ہے اور ہر آرک میں گنجائش 2 ہوتی ہے۔ زیادہ سے زیادہ بہاؤ ہونے دیں۔ ڈو میں ہر آرک کے لیے: اگر، پھر متعلقہ کنارے کو سے سمت میں موڑ دیں (مرحلہ 1 میں متعلقہ کنارے کو تفویض کردہ سمت، سے، "غلط" تھی) ؛ اگر، تو G میں متعلقہ کنارے کو سمت سے سمت میں موڑ دیں (اس صورت میں، مرحلہ 1 میں سمت "صحیح" تھی)۔ نوٹ کریں کہ معاملہ ناممکن ہے، کیونکہ آرکس کے ذریعے تمام بہاؤ کی اقدار یکساں اعداد ہیں۔ ہر آرک کی کاپیاں شامل کرکے اضافہ کریں۔ نتیجے میں گراف یکساں اور ہم آہنگ ہے۔ ہیورسٹک الگورتھم جب مخلوط گراف یکساں نہ ہو اور تمام نوڈس میں یکساں ڈگری نہ ہو تو گراف کو یکساں گراف میں تبدیل کیا جا سکتا ہے۔ ایک مخلوط گراف ہونے دیں جو مضبوطی سے جڑا ہوا ہے۔ آرک کی سمتوں کو نظر انداز کرکے عجیب ڈگری نوڈس تلاش کریں اور کم سے کم لاگت کا ملاپ حاصل کریں۔ یکساں گراف تیار کرنے کے لیے کم سے کم لاگت کے ملاپ سے کناروں کے ساتھ گراف کو بڑھائیں۔ گراف یکساں ہے لیکن متناسب نہیں ہے اور ایک یولیرین مخلوط گراف متناسب اور متناسب ہے۔ ایک ہم آہنگ گراف حاصل کرنے کے لیے کم از کم لاگت کے بہاؤ کے مسئلے کو حل کریں جو شاید یکساں نہ ہو۔ آخری مرحلے میں سمیٹرک گراف کو یکساں بنانا شامل ہے۔ عجیب ڈگری نوڈس کو لیبل کریں۔ ایسے چکروں کو تلاش کریں جو آرک سیٹ میں لائنوں اور ایج سیٹ میں لائنوں کے درمیان متبادل ہوں جو پوائنٹس پر شروع اور ختم ہوں۔ اندر کے آرکس کو غیر ہدایت شدہ کناروں کے طور پر سمجھا جانا چاہیے، نہ کہ ہدایت شدہ آرکس کے طور پر۔ جینیاتی الگورتھم ہوا جیانگ اور دیگر کے ذریعہ شائع کردہ ایک مقالہ۔ آل نے ایک آبادی پر کام کرکے مخلوط چینی پوسٹ مین کے مسئلے کو حل کرنے کے لیے ایک جینیاتی الگورتھم تیار کیا۔ الگورتھم نے ایم سی پی پی کے دیگر تخمینہ الگورتھم کے مقابلے میں اچھی کارکردگی کا مظاہرہ کیا۔ کیپیسیٹیٹڈ آرک روٹنگ کا مسئلہ بھی دیکھیں حوالہ جات گراف تھیوری میں کمپیوٹیشنل مسائل