تحقیقی کام شاید ہماری تربیت کا سب سے دلچسپ حصہ ہے۔ خیال یہ ہے کہ یونیورسٹی میں رہتے ہوئے بھی اپنی منتخب کردہ سمت میں خود کو آزمانا ہے۔ مثال کے طور پر، سافٹ ویئر انجینئرنگ اور مشین لرننگ کے شعبوں کے طلباء اکثر کمپنیوں میں تحقیق کرنے جاتے ہیں (بنیادی طور پر JetBrains یا Yandex، لیکن نہ صرف)۔
اس پوسٹ میں میں کمپیوٹر سائنس میں اپنے پروجیکٹ کے بارے میں بات کروں گا۔ اپنے کام کے ایک حصے کے طور پر، میں نے NP کے مشکل ترین مسائل میں سے ایک کو حل کرنے کے طریقوں کا مطالعہ کیا اور عمل میں لایا: عمودی کو ڈھانپنے کا مسئلہ.
آج کل، NP- مشکل مسائل کے لیے ایک دلچسپ نقطہ نظر بہت تیزی سے ترقی کر رہا ہے - پیرامیٹرائزڈ الگورتھم۔ میں آپ کو تیز رفتار بنانے کی کوشش کروں گا، آپ کو کچھ آسان پیرامیٹرائزڈ الگورتھم بتاؤں گا اور ایک طاقتور طریقہ بیان کروں گا جس نے میری بہت مدد کی۔ میں نے PACE چیلنج مقابلے میں اپنے نتائج پیش کیے: اوپن ٹیسٹ کے نتائج کے مطابق، میرا حل تیسرا مقام رکھتا ہے، اور حتمی نتائج 1 جولائی کو معلوم ہوں گے۔
میرے بارے میں
میرا نام واسیلی الفروف ہے، میں اب نیشنل ریسرچ یونیورسٹی ہائر سکول آف اکنامکس - سینٹ پیٹرزبرگ میں اپنا تیسرا سال مکمل کر رہا ہوں۔ مجھے اپنے اسکول کے زمانے سے ہی الگورتھم میں دلچسپی ہے، جب میں نے ماسکو کے اسکول نمبر 179 میں تعلیم حاصل کی اور کمپیوٹر سائنس اولمپیاڈز میں کامیابی سے حصہ لیا۔
پیرامیٹرائزڈ الگورتھم میں ماہرین کی ایک محدود تعداد بار میں داخل ہوتی ہے...
کتاب سے لی گئی مثال
تصور کریں کہ آپ ایک چھوٹے سے شہر میں بار سیکیورٹی گارڈ ہیں۔ ہر جمعہ کو، آدھا شہر آرام کرنے کے لیے آپ کے بار میں آتا ہے، جس سے آپ کو کافی پریشانی ہوتی ہے: آپ کو لڑائی سے بچنے کے لیے بدمعاش گاہکوں کو بار سے باہر پھینکنے کی ضرورت ہے۔ آخر کار، آپ تنگ آ جاتے ہیں اور احتیاطی تدابیر اختیار کرنے کا فیصلہ کرتے ہیں۔
چونکہ آپ کا شہر چھوٹا ہے، آپ کو بخوبی معلوم ہے کہ سرپرستوں کے کون سے جوڑے ایک ساتھ بار میں ختم ہونے پر آپس میں لڑ سکتے ہیں۔ آپ کی ایک فہرست ہے n وہ لوگ جو آج رات بار میں آئیں گے۔ آپ نے فیصلہ کیا کہ شہر کے کچھ لوگوں کو بار سے باہر رکھنے کا فیصلہ کیا جائے بغیر کسی سے لڑائی جھگڑے کے۔ ایک ہی وقت میں، آپ کے مالک منافع کھونا نہیں چاہتے ہیں اور اگر آپ اس سے زیادہ نہیں ہونے دیتے ہیں تو ناخوش ہوں گے۔ k لوگ.
بدقسمتی سے، آپ کے سامنے مسئلہ ایک کلاسک NP- مشکل مسئلہ ہے۔ ہو سکتا ہے تم اسے جانتے ہو۔ ، یا عمودی ڈھکنے کے مسئلے کے طور پر۔ اس طرح کے مسائل کے لیے، عام صورت میں، کوئی الگورتھم نہیں ہیں جو قابل قبول وقت میں کام کریں۔ بالکل درست ہونے کے لیے، غیر ثابت شدہ اور کافی مضبوط مفروضہ ETH (Exponential Time Hypothesis) کہتا ہے کہ یہ مسئلہ وقت پر حل نہیں ہو سکتا۔ ، یعنی، آپ مکمل تلاش سے بہتر کسی چیز کے بارے میں نہیں سوچ سکتے۔ مثال کے طور پر، ہم کہتے ہیں کہ کوئی آپ کے بار میں آنے والا ہے۔ N = 1000 انسان پھر مکمل تلاش ہوگی۔ اختیارات جو تقریباً موجود ہیں۔ - پاگل رقم. خوش قسمتی سے، آپ کی انتظامیہ نے آپ کو ایک حد دے دی ہے۔ k = 10۔، لہذا آپ کو اعادہ کرنے کے لئے مجموعوں کی تعداد بہت کم ہے: دس عناصر کے ذیلی سیٹوں کی تعداد ہے . یہ بہتر ہے، لیکن ایک طاقتور کلسٹر پر بھی اسے ایک دن میں شمار نہیں کیا جائے گا۔
بار کے زائرین کے درمیان کشیدہ تعلقات کی اس ترتیب میں لڑائی کے امکان کو ختم کرنے کے لیے، آپ کو باب، ڈینیئل اور فیڈور کو باہر رکھنے کی ضرورت ہے۔ ایسا کوئی حل نہیں جس میں صرف دو ہی پیچھے رہ جائیں۔
کیا اس کا مطلب یہ ہے کہ اب وقت آگیا ہے کہ ہم سب کو اندر آنے دیں؟ آئیے دوسرے اختیارات پر غور کریں۔ ٹھیک ہے، مثال کے طور پر، آپ صرف ان لوگوں کو داخل نہیں کر سکتے ہیں جو لوگوں کی ایک بہت بڑی تعداد کے ساتھ لڑنے کا امکان رکھتے ہیں۔ اگر کوئی کم از کم اس سے لڑ سکتا ہے۔ k+1 دوسرا شخص، پھر آپ یقینی طور پر اسے اندر نہیں جانے دے سکتے ہیں - ورنہ آپ کو سب کو باہر رکھنا پڑے گا۔ k+1 شہر کے لوگ، جن کے ساتھ وہ لڑ سکتا ہے، جو یقیناً قیادت کو پریشان کرے گا۔
آپ اس اصول کے مطابق ہر ایک کو باہر پھینک دیں۔ پھر ہر کوئی اس سے زیادہ نہیں لڑ سکتا k لوگ انہیں باہر پھینکنا k آدمی، تم اس سے زیادہ کچھ نہیں روک سکتے تنازعات اس کا مطلب ہے کہ اگر اس سے زیادہ ہے۔ اگر کوئی شخص کم از کم ایک تنازعہ میں ملوث ہے، تو یقیناً آپ ان سب کو روک نہیں سکتے۔ چونکہ، یقیناً، آپ یقینی طور پر مکمل طور پر غیر متضاد لوگوں کو آنے دیں گے، اس لیے آپ کو دو سو افراد میں سے دس کے سائز کے تمام ذیلی سیٹوں سے گزرنا ہوگا۔ وہاں تقریباً ہیں۔ ، اور آپریشنز کی اس تعداد کو پہلے ہی کلسٹر پر ترتیب دیا جا سکتا ہے۔
اگر آپ ایسے افراد کو محفوظ طریقے سے لے جا سکتے ہیں جن کا کوئی تنازعہ نہیں ہے، تو پھر ان لوگوں کا کیا ہوگا جو صرف ایک تنازعہ میں حصہ لیتے ہیں؟ درحقیقت، انہیں اپنے مخالف پر دروازہ بند کرکے اندر جانے دیا جا سکتا ہے۔ درحقیقت، اگر ایلس صرف باب کے ساتھ تنازعہ میں ہے، تو اگر ہم ایلس کو ان دونوں میں سے باہر جانے دیں، تو ہم نہیں ہاریں گے: باب کے دوسرے تنازعات ہوسکتے ہیں، لیکن ایلس کے پاس یقینی طور پر وہ نہیں ہیں۔ مزید یہ کہ ہمارے لیے یہ کوئی معنی نہیں رکھتا کہ ہم دونوں کو اندر نہ آنے دیں۔ اس طرح کے آپریشنز کے بعد کوئی اور باقی نہیں رہتا غیر حل شدہ قسمت کے ساتھ مہمان: ہمارے پاس صرف ہے۔ تنازعات، ہر ایک دو شرکاء کے ساتھ اور ہر ایک کم از کم دو میں ملوث ہے۔ تو جو باقی رہ جاتا ہے وہ حل کرنا ہے۔ اختیارات، جو لیپ ٹاپ پر آدھے دن کو آسانی سے سمجھا جا سکتا ہے۔
درحقیقت، سادہ استدلال سے آپ اور بھی زیادہ پرکشش حالات حاصل کر سکتے ہیں۔ نوٹ کریں کہ ہمیں یقینی طور پر تمام تنازعات کو حل کرنے کی ضرورت ہے، یعنی ہر ایک متضاد جوڑے میں سے، کم از کم ایک شخص کا انتخاب کریں جسے ہم اندر نہیں آنے دیں گے۔ آئیے درج ذیل الگورتھم پر غور کریں: کوئی بھی تنازعہ لیں، جس میں سے ہم ایک شریک کو ہٹاتے ہیں اور باقی سے بار بار شروع کرتے ہیں، پھر دوسرے کو ہٹاتے ہیں اور بار بار شروع کرتے ہیں۔ چونکہ ہم ہر قدم پر کسی کو باہر پھینک دیتے ہیں، اس لیے ایسے الگورتھم کا ریکریشن ٹری گہرائی کا ایک بائنری ٹری ہے۔ k، لہذا مجموعی طور پر الگورتھم کام کرتا ہے۔ جہاں n عمودی کی تعداد ہے، اور m - پسلیوں کی تعداد۔ ہماری مثال میں، یہ تقریباً دس ملین ہے، جسے نہ صرف ایک لیپ ٹاپ بلکہ موبائل فون پر بھی اسپلٹ سیکنڈ میں شمار کیا جا سکتا ہے۔
مندرجہ بالا مثال ایک مثال ہے۔ پیرامیٹرائزڈ الگورتھم. پیرامیٹرائزڈ الگورتھم وہ الگورتھم ہیں جو وقت کے ساتھ چلتے ہیں۔ f(k) poly(n)جہاں p - کثیر الجہتی، f ایک صوابدیدی کمپیوٹیبل فنکشن ہے، اور k - کچھ پیرامیٹر، جو، ممکنہ طور پر، مسئلہ کے سائز سے بہت چھوٹا ہوگا۔
اس الگورتھم سے پہلے تمام استدلال ایک مثال دیتا ہے۔ کرنلائزیشن پیرامیٹرائزڈ الگورتھم بنانے کی عمومی تکنیکوں میں سے ایک ہے۔ کرنلائزیشن پیرامیٹر کے فنکشن کے ذریعہ محدود قدر تک مسئلہ کے سائز کو کم کرنا ہے۔ نتیجے میں آنے والے مسئلے کو اکثر دانا کہا جاتا ہے۔ اس طرح، عمودی کی ڈگریوں کے بارے میں سادہ استدلال کے ذریعے، ہم نے ورٹیکس کور کے مسئلے کے لیے ایک چوکور دانا حاصل کیا، جو جواب کے سائز کے مطابق بنایا گیا ہے۔ اس کام کے لیے آپ دوسری ترتیبات بھی منتخب کر سکتے ہیں (جیسے ورٹیکس کور اباوو ایل پی)، لیکن یہ وہ ترتیب ہے جس پر ہم بحث کریں گے۔
پیس چیلنج
مقابلہ (The Parameterized Algorithms and Computational Experiments Challenge) 2015 میں پیرامیٹرائزڈ الگورتھم اور کمپیوٹیشنل مسائل کو حل کرنے کے لیے عملی طور پر استعمال ہونے والے طریقوں کے درمیان تعلق قائم کرنے کے لیے پیدا ہوا تھا۔ پہلے تین مقابلے ایک گراف کی درخت کی چوڑائی تلاش کرنے کے لیے وقف تھے (ایک سٹینر درخت کی تلاش (()۔ اس سال، ان مسائل میں سے ایک جس میں آپ اپنا ہاتھ آزما سکتے ہیں وہ تھا اوپر بیان کردہ عمودی ڈھکنے کا مسئلہ۔
یہ مقابلہ ہر سال مقبولیت حاصل کر رہا ہے۔ اگر آپ ابتدائی اعداد و شمار پر یقین رکھتے ہیں، تو اس سال 24 ٹیموں نے مقابلے میں حصہ لیا تاکہ صرف چوٹی کو ڈھانپنے کے مسئلے کو حل کیا جا سکے۔ یہ بات قابل غور ہے کہ مقابلہ کئی گھنٹے یا ایک ہفتہ تک نہیں بلکہ کئی ماہ تک جاری رہتا ہے۔ ٹیموں کو ادب کا مطالعہ کرنے کا موقع ملتا ہے، اپنے اصل خیال کے ساتھ آتے ہیں اور اسے نافذ کرنے کی کوشش کرتے ہیں. جوہر میں، یہ مقابلہ ایک تحقیقی منصوبہ ہے۔ سب سے زیادہ مؤثر حل اور جیتنے والوں کو ایوارڈ دینے کے خیالات کانفرنس کے ساتھ مل کر منعقد کیے جائیں گے۔ (انٹرنیشنل سمپوزیم آن پیرامیٹرائزڈ اینڈ ایکیکٹ کمپیوٹیشن) یورپ میں سب سے بڑی سالانہ الگورتھمک میٹنگ کے حصے کے طور پر . مقابلے کے بارے میں مزید تفصیلی معلومات خود پر مل سکتی ہیں۔ ، اور پچھلے سالوں کے نتائج جھوٹے ہیں۔ .
حل کا خاکہ
ورٹیکس کورنگ کے مسئلے کو حل کرنے کے لیے، میں نے پیرامیٹرائزڈ الگورتھم استعمال کرنے کی کوشش کی۔ وہ عام طور پر دو حصوں پر مشتمل ہوتے ہیں: آسان بنانے کے اصول (جو مثالی طور پر کرنلائزیشن کا باعث بنتے ہیں) اور تقسیم کے اصول۔ آسان بنانے کے اصول کثیر نامی وقت میں ان پٹ کی پری پروسیسنگ ہیں۔ اس طرح کے قواعد کو لاگو کرنے کا مقصد مسئلہ کو مساوی چھوٹے مسئلے تک کم کرنا ہے۔ آسان بنانے کے اصول الگورتھم کا سب سے مہنگا حصہ ہیں، اور اس حصے کو لاگو کرنے سے چلنے کا کل وقت ہوتا ہے سادہ کثیر الثانی وقت کے بجائے۔ ہمارے معاملے میں، تقسیم کرنے کے اصول اس حقیقت پر مبنی ہیں کہ ہر چوٹی کے لیے آپ کو اسے یا اس کے پڑوسی کو بطور جواب لینے کی ضرورت ہے۔
عام اسکیم یہ ہے: ہم آسان بنانے کے قوانین کو لاگو کرتے ہیں، پھر ہم کچھ ورٹیکس کو منتخب کرتے ہیں، اور دو بار بار آنے والی کالیں کرتے ہیں: پہلے ہم اسے جواب میں لیتے ہیں، اور دوسرے میں ہم اس کے تمام پڑوسیوں کو لیتے ہیں۔ یہ وہی ہے جسے ہم اس چوٹی کے ساتھ تقسیم کرنا (شاخ بندی) کہتے ہیں۔
اگلے پیراگراف میں اس اسکیم میں بالکل ایک اضافہ کیا جائے گا۔
تقسیم (برنچنگ) کے قوانین کے لیے خیالات
آئیے اس بات پر بحث کرتے ہیں کہ کس طرح ایک چوٹی کا انتخاب کیا جائے جس کے ساتھ تقسیم واقع ہو۔
الگورتھمک معنوں میں مرکزی خیال بہت لالچی ہے: آئیے زیادہ سے زیادہ ڈگری کا ایک ورٹیکس لیں اور اس کے ساتھ تقسیم کریں۔ یہ کیوں بہتر لگتا ہے؟ کیونکہ ریکسریو کال کی دوسری برانچ میں ہم اس طرح سے بہت سی چوٹیوں کو ہٹا دیں گے۔ آپ باقی ایک چھوٹے گراف پر اعتماد کر سکتے ہیں اور ہم اس پر تیزی سے کام کر سکتے ہیں۔
یہ نقطہ نظر، پہلے سے زیر بحث سادہ دانا بنانے کی تکنیک کے ساتھ، خود کو اچھی طرح سے ظاہر کرتا ہے اور سائز میں کئی ہزار چوٹیوں کے کچھ ٹیسٹوں کو حل کرتا ہے۔ لیکن، مثال کے طور پر، یہ کیوبک گرافس کے لیے اچھی طرح سے کام نہیں کرتا ہے (یعنی وہ گراف جن کے ہر چوٹی کی ڈگری تین ہے)۔
کافی سادہ خیال پر مبنی ایک اور آئیڈیا ہے: اگر گراف منقطع ہو جائے تو، اس کے منسلک اجزاء پر مسئلہ آزادانہ طور پر حل کیا جا سکتا ہے، آخر میں جوابات کو یکجا کر کے۔ ویسے، یہ اسکیم میں ایک چھوٹی وعدہ شدہ ترمیم ہے، جو حل کو نمایاں طور پر تیز کرے گی: پہلے، اس معاملے میں، ہم اجزاء کے جوابات کا حساب لگانے کے لیے اوقات کی پیداوار کے لیے کام کرتے تھے، لیکن اب ہم اس کے لیے کام کرتے ہیں۔ رقم. اور برانچنگ کو تیز کرنے کے لیے، آپ کو ایک منسلک گراف کو منقطع میں تبدیل کرنے کی ضرورت ہے۔
یہ کیسے کرنا ہے؟ اگر گراف میں کوئی نقطہ نظر ہے، تو آپ کو اس پر لڑنے کی ضرورت ہے۔ ایک آرٹیکولیشن پوائنٹ ایک ایسا ورٹیکس ہوتا ہے جسے ہٹانے پر، گراف اپنا رابطہ کھو دیتا ہے۔ ایک گراف میں تمام جنکشن پوائنٹس کو لکیری وقت میں کلاسیکی الگورتھم کا استعمال کرتے ہوئے پایا جا سکتا ہے۔ یہ نقطہ نظر نمایاں طور پر برانچنگ کو تیز کرتا ہے۔
جب منتخب کردہ چوٹیوں میں سے کسی کو ہٹا دیا جاتا ہے، تو گراف منسلک اجزاء میں تقسیم ہو جائے گا۔
ہم یہ کریں گے، لیکن ہم مزید چاہتے ہیں۔ مثال کے طور پر، گراف میں چھوٹے عمودی کٹوتیوں کو دیکھیں اور اس سے عمودی حصوں کے ساتھ تقسیم کریں۔ کم از کم عالمی ورٹیکس کٹ کو تلاش کرنے کا جو سب سے موثر طریقہ میں جانتا ہوں وہ ہے Gomori-hu درخت کا استعمال کرنا، جو کیوبک ٹائم میں بنایا گیا ہے۔ PACE چیلنج میں، گراف کا عام سائز کئی ہزار عمودی ہے۔ اس صورت حال میں، تکرار درخت کے ہر چوٹی پر اربوں آپریشن کرنے کی ضرورت ہے۔ یہ پتہ چلتا ہے کہ مختص وقت میں مسئلہ کو حل کرنے کے لئے یہ صرف ناممکن ہے.
آئیے حل کو بہتر بنانے کی کوشش کرتے ہیں۔ چوٹیوں کے جوڑے کے درمیان کم از کم چوٹی کاٹنا کسی بھی الگورتھم کے ذریعہ پایا جاسکتا ہے جو زیادہ سے زیادہ بہاؤ بناتا ہے۔ آپ اسے ایسے نیٹ ورک پر چھوڑ سکتے ہیں۔ عملی طور پر یہ بہت تیزی سے کام کرتا ہے۔ مجھے ایک شبہ ہے کہ آپریٹنگ ٹائم کے تخمینہ کو ثابت کرنا نظریاتی طور پر ممکن ہے۔ ، جو پہلے ہی کافی قابل قبول ہے۔
میں نے بے ترتیب چوٹیوں کے جوڑے کے درمیان کٹوتیوں کو تلاش کرنے اور سب سے زیادہ متوازن لینے کی کئی بار کوشش کی۔ بدقسمتی سے، اس سے اوپن PACE چیلنج ٹیسٹنگ میں خراب نتائج برآمد ہوئے۔ میں نے اس کا موازنہ ایک الگورتھم سے کیا جو زیادہ سے زیادہ ڈگری کے عمودی حصوں کو تقسیم کرتا ہے، انہیں نزول کی گہرائی کی حد کے ساتھ چلاتا ہے۔ الگورتھم کے اس طرح سے کٹ تلاش کرنے کی کوشش کرنے کے بعد، بڑے گراف باقی رہ گئے۔ یہ اس حقیقت کی وجہ سے ہے کہ کٹوتیاں بہت غیر متوازن نکلی ہیں: 5-10 چوٹیوں کو ہٹانے کے بعد، صرف 15-20 کو الگ کرنا ممکن تھا۔
یہ بات قابل غور ہے کہ نظریاتی طور پر تیز ترین الگورتھم کے بارے میں مضامین تقسیم کرنے کے لیے چوٹیوں کو منتخب کرنے کے لیے بہت زیادہ جدید تکنیکوں کا استعمال کرتے ہیں۔ اس طرح کی تکنیکوں کا نفاذ بہت پیچیدہ ہوتا ہے اور وقت اور یادداشت کے لحاظ سے اکثر خراب کارکردگی ہوتی ہے۔ میں ان لوگوں کی شناخت کرنے سے قاصر تھا جو مشق کے لیے کافی قابل قبول ہیں۔
آسان بنانے کے قواعد کو کیسے لاگو کریں۔
ہمارے پاس پہلے ہی کرنلائزیشن کے آئیڈیاز ہیں۔ مجھے آپ کو یاد دلانے دو:
- اگر کوئی الگ تھلگ چوٹی ہے تو اسے حذف کر دیں۔
- اگر ڈگری 1 کی چوٹی ہے تو اسے ہٹا دیں اور جواب میں اس کے پڑوسی کو لے جائیں۔
- اگر کم از کم ڈگری کی چوٹی ہے۔ k+1، اسے واپس لے لو.
پہلے دو کے ساتھ سب کچھ واضح ہے، تیسرے کے ساتھ ایک چال ہے۔ اگر کسی بار کے بارے میں مزاحیہ مسئلہ میں ہمیں اوپری حد دی گئی تھی۔ k، پھر PACE چیلنج میں آپ کو صرف کم از کم سائز کا ایک ورٹیکس کور تلاش کرنے کی ضرورت ہے۔ یہ فیصلہ کے مسائل میں تلاش کے مسائل کی ایک عام تبدیلی ہے؛ اکثر دو قسم کے مسائل میں کوئی فرق نہیں ہوتا ہے۔ عملی طور پر، اگر ہم عمودی ڈھکنے والے مسئلے کے لیے ایک حل لکھ رہے ہیں، تو فرق ہو سکتا ہے۔ مثال کے طور پر، جیسا کہ تیسرے نکتے میں ہے۔
نفاذ کے نقطہ نظر سے، آگے بڑھنے کے دو طریقے ہیں۔ پہلے نقطہ نظر کو تکراری گہرا کرنا کہا جاتا ہے۔ یہ مندرجہ ذیل ہے: ہم جواب پر نیچے سے کچھ معقول رکاوٹ کے ساتھ شروع کر سکتے ہیں، اور پھر اس رکاوٹ سے کم تکرار کے بغیر، اوپر سے جواب پر ایک رکاوٹ کے طور پر اس رکاوٹ کو استعمال کرتے ہوئے اپنا الگورتھم چلا سکتے ہیں۔ اگر ہمیں کچھ جواب مل گیا ہے، تو اس کے بہترین ہونے کی ضمانت ہے، ورنہ ہم اس حد کو ایک سے بڑھا کر دوبارہ شروع کر سکتے ہیں۔
ایک اور نقطہ نظر کچھ موجودہ بہترین جواب کو ذخیرہ کرنا اور ایک چھوٹا جواب تلاش کرنا ہے، جب مل جائے تو اس پیرامیٹر کو تبدیل کریں۔ k تلاش میں غیر ضروری شاخوں کو زیادہ سے زیادہ کاٹنے کے لیے۔
رات کے کئی تجربات کرنے کے بعد، میں نے ان دو طریقوں کے امتزاج پر طے کیا: پہلے، میں تلاش کی گہرائی پر کسی قسم کی حد کے ساتھ اپنا الگورتھم چلاتا ہوں (اسے منتخب کرنا تاکہ اس میں اہم حل کے مقابلے میں نہ ہونے کے برابر وقت لگے) اور بہترین استعمال جواب کی بالائی حد کے طور پر پایا گیا حل - یعنی ایک ہی چیز کے لیے k.
ڈگری کے عمودی 2
ہم نے ڈگری 0 اور 1 کی چوٹیوں سے نمٹا ہے۔ یہ پتہ چلتا ہے کہ یہ ڈگری 2 کے عمودی حصوں کے ساتھ کیا جا سکتا ہے، لیکن اس کے لئے گراف سے زیادہ پیچیدہ آپریشن کی ضرورت ہوگی.
اس کی وضاحت کرنے کے لیے، ہمیں کسی نہ کسی طرح چوٹیوں کو نامزد کرنے کی ضرورت ہے۔ آئیے ڈگری 2 کے ایک ورٹیکس کو ایک ورٹیکس کہتے ہیں۔ v، اور اس کے پڑوسی - عمودی x и y. اگلا ہمارے پاس دو مقدمات ہوں گے۔
- جب x и y - پڑوسی پھر آپ جواب دے سکتے ہیں۔ x и yاور v حذف کریں درحقیقت، اس مثلث سے بدلے میں کم از کم دو چوٹیوں کو لینے کی ضرورت ہے، اور اگر ہم لیں تو ہم یقینی طور پر نہیں ہاریں گے۔ x и y: ان کے شاید دوسرے پڑوسی ہیں، اور v وہ یہاں نہیں ہیں۔
- جب x и y - پڑوسی نہیں پھر یہ بتایا گیا ہے کہ تینوں چوٹیوں کو ایک میں چپکایا جا سکتا ہے۔ خیال یہ ہے کہ اس معاملے میں ایک بہترین جواب ہے، جس میں ہم یا تو لیتے ہیں۔ v، یا دونوں عمودی x и y. مزید یہ کہ پہلی صورت میں ہمیں تمام پڑوسیوں کو جواب میں لینا پڑے گا۔ x и yلیکن دوسرے میں یہ ضروری نہیں ہے۔ یہ بالکل ان معاملات سے مطابقت رکھتا ہے جب ہم جواب میں چپکنے والی چوٹی کو نہیں لیتے ہیں اور جب ہم ایسا کرتے ہیں۔ یہ صرف نوٹ کرنے کے لئے رہتا ہے کہ دونوں صورتوں میں اس طرح کے آپریشن سے ردعمل ایک سے کم ہوتا ہے.
یہ بات قابل غور ہے کہ اس نقطہ نظر کو منصفانہ لکیری وقت میں درست طریقے سے نافذ کرنا کافی مشکل ہے۔ چوٹیوں کو گلونگ کرنا ایک پیچیدہ آپریشن ہے؛ آپ کو پڑوسیوں کی فہرستیں کاپی کرنے کی ضرورت ہے۔ اگر یہ لاپرواہی سے کیا جاتا ہے تو، آپ غیر علامتی طور پر سب سے زیادہ وقت کے ساتھ ختم ہوسکتے ہیں (مثال کے طور پر، اگر آپ ہر ایک گلونگ کے بعد بہت سارے کناروں کو کاپی کرتے ہیں)۔ میں نے ڈگری 2 کے عمودی خطوط سے پورے راستے تلاش کرنے اور خاص معاملات کے ایک گروپ کا تجزیہ کرنے پر طے کیا، جیسے اس طرح کے عمودی سے سائیکل یا ایک کو چھوڑ کر ایسے تمام چوٹیوں سے۔
اس کے علاوہ، یہ ضروری ہے کہ یہ عمل الٹ جائے، تاکہ تکرار سے واپس آنے پر ہم گراف کو اس کی اصل شکل میں بحال کریں۔ اس بات کو یقینی بنانے کے لیے، میں نے ضم شدہ عمودی خطوط کے کنارے کی فہرستیں صاف نہیں کیں، اور پھر مجھے صرف یہ معلوم ہوا کہ کن کناروں کو کہاں جانا ہے۔ گراف کے اس نفاذ کے لیے بھی درستگی کی ضرورت ہوتی ہے، لیکن یہ مناسب لکیری وقت فراہم کرتا ہے۔ اور کئی دسیوں ہزار کناروں کے گراف کے لیے، یہ پروسیسر کیشے میں فٹ بیٹھتا ہے، جو رفتار میں بہت فائدہ دیتا ہے۔
لکیری دانا
آخر میں، دانا کا سب سے دلچسپ حصہ.
شروع کرنے کے لیے، یاد رکھیں کہ دو طرفہ گراف میں کم از کم ورٹیکس کور کا استعمال کرتے ہوئے پایا جا سکتا ہے . ایسا کرنے کے لیے آپ کو الگورتھم استعمال کرنے کی ضرورت ہے۔ وہاں زیادہ سے زیادہ مماثلت تلاش کرنے کے لیے، اور پھر تھیوریم کا استعمال کریں۔ .
لکیری دانا کا خیال یہ ہے: پہلے ہم گراف کو تقسیم کرتے ہیں، یعنی ہر ایک چوٹی کے بجائے v آئیے دو چوٹیوں کو شامل کریں۔ и ، اور ہر کنارے کے بجائے u --.v آئیے دو پسلیاں جوڑتے ہیں۔ и . نتیجہ کا گراف دو طرفہ ہوگا۔ آئیے اس میں کم از کم چوٹی کا احاطہ تلاش کریں۔ اصل گراف کے کچھ عمودی دو بار وہاں پہنچیں گے، کچھ صرف ایک بار، اور کچھ کبھی نہیں. Nemhauser-Trotter تھیوریم کہتا ہے کہ اس صورت میں کوئی ان چوٹیوں کو ہٹا سکتا ہے جو ایک بار بھی نہیں ٹکرائے اور جو دو بار مارے انہیں واپس لے سکتے ہیں۔ مزید برآں، وہ کہتی ہیں کہ بقیہ چوٹیوں میں سے (وہ جو ایک بار مارتے ہیں) آپ کو جواب کے طور پر کم از کم نصف لینے کی ضرورت ہے۔
ہم نے ابھی چھوڑنا سیکھا ہے۔ 2k چوٹیوں درحقیقت، اگر بقیہ جواب تمام عمودی خطوط کا کم از کم نصف ہے، تو مجموعی طور پر اس سے زیادہ کوئی عمودی نہیں ہیں 2k.
یہاں میں ایک چھوٹا سا قدم آگے بڑھانے کے قابل تھا۔ یہ واضح ہے کہ اس طرح سے بنائے گئے دانا کا انحصار اس بات پر ہے کہ ہم نے دو طرفہ گراف میں کس قسم کا کم سے کم ورٹیکس کور لیا ہے۔ میں ایک لینا چاہوں گا تاکہ باقی چوٹیوں کی تعداد کم سے کم ہو۔ پہلے، وہ صرف وقت پر ایسا کرنے کے قابل تھے . میں وقت میں اس الگورتھم کے نفاذ کے ساتھ آیا ہوں۔ اس طرح، اس کور کو ہر برانچنگ مرحلے پر لاکھوں عمودی خطوط میں تلاش کیا جا سکتا ہے۔
نتیجہ
پریکٹس سے پتہ چلتا ہے کہ میرا حل کئی سو چوٹیوں اور کئی ہزار کناروں کے ٹیسٹ پر اچھی طرح کام کرتا ہے۔ اس طرح کے ٹیسٹوں میں یہ توقع کی جا سکتی ہے کہ آدھے گھنٹے میں کوئی حل مل جائے گا۔ ایک قابل قبول وقت میں جواب تلاش کرنے کا امکان، اصولی طور پر، بڑھ جاتا ہے اگر گراف میں اعلیٰ درجے کے عمودی خطوط کی کافی بڑی تعداد ہو، مثال کے طور پر، ڈگری 10 اور اس سے زیادہ۔
مقابلے میں حصہ لینے کے لیے حل بھیجنا پڑتا تھا۔ . وہاں پیش کردہ معلومات سے اندازہ لگانا ، اوپن ٹیسٹ میں میرا حل دوسرے سے بڑے فرق کے ساتھ، بیس میں سے تیسرے نمبر پر ہے۔ مکمل طور پر ایماندار ہونے کے لئے، یہ مکمل طور پر واضح نہیں ہے کہ مقابلہ میں ہی حل کی جانچ کیسے کی جائے گی: مثال کے طور پر، میرا حل چوتھے نمبر پر حل کے مقابلے میں کم ٹیسٹ پاس کرتا ہے، لیکن جو پاس ہوتے ہیں، ان پر یہ تیزی سے کام کرتا ہے۔
بند ٹیسٹوں کے نتائج یکم جولائی کو معلوم ہوں گے۔
ماخذ: www.habr.com