Reverse-search algorithm
ریورس سرچ الگورتھم الگورتھم کی ایک کلاس ہے جو کسی مخصوص سائز کی تمام اشیاء کو مشترکہ اشیاء کی کچھ کلاسوں سے تیار کرتی ہے۔ بہت سے معاملات میں، یہ طریقے اشیاء کو کثیر الجہتی وقت فی آبجیکٹ میں پیدا کرنے کی اجازت دیتے ہیں، جس میں اشیاء کی مستقل تعداد (کثیر الجہتی جگہ) کو ذخیرہ کرنے کے لیے صرف کافی میموری کا استعمال کیا جاتا ہے۔ (عام طور پر، تاہم، انہیں کثیر الجہتی وقت کے الگورتھم کے طور پر درجہ بند نہیں کیا جاتا ہے، کیونکہ ان سے پیدا ہونے والی اشیاء کی تعداد متغیر ہوتی ہے۔) وہ اپنی ریاستی جگہ کے ایک پھیلے ہوئے درخت میں پیدا ہونے والی اشیاء کو منظم کرکے کام کرتے ہیں، اور پھر اس درخت کی گہرائی سے پہلے تلاش کرتے ہیں۔ ریورس سرچ الگورتھم کو ڈیوڈ ایوس اور کومی فوکوڈا نے 1991 میں کنویکس پولی ٹاپس کے عمودی حصوں اور ہائپرپلین کے انتظامات کے خلیوں کو پیدا کرنے کے مسائل کے لیے متعارف کرایا تھا۔ انہیں 1996 میں ایوس اور فوکودا نے زیادہ وسیع پیمانے پر باقاعدہ بنایا تھا۔ اصول ایک ریورس سرچ الگورتھم ریاستی جگہ میں مشترکہ اشیاء پیدا کرتا ہے، ایک مضمر گراف جس کے عمودی حصے وہ اشیاء ہیں جنہیں درج کیا جانا ہے اور جن کے کنارے اشیاء کے جوڑوں کو جوڑنے والی کچھ "مقامی چالوں" کی نمائندگی کرتے ہیں، عام طور پر ان کی ساخت میں چھوٹی تبدیلیاں کرکے۔ یہ اس ریاستی جگہ کے جڑوں پر پھیلے ہوئے درخت میں گہرائی سے پہلے تلاش کا استعمال کرتے ہوئے ہر چیز کو ڈھونڈتا ہے، جسے درج ذیل معلومات سے بیان کیا گیا ہے: پھیلے ہوئے درخت کی جڑ، اشیاء میں سے ایک درخت میں موجود ہر شے کے والدین کو پیدا کرنے کے لیے ایک ذیلی روٹین، اس خاصیت کے ساتھ کہ اگر کافی بار دہرایا جائے تو یہ بالآخر جڑ تک پہنچ جائے گا ریاستی جگہ کے تمام پڑوسیوں کو درج کرنے کے لیے ایک ذیلی روٹین (جن میں سے سبھی درخت میں پڑوسی نہیں ہو سکتے ہیں) اس معلومات سے درخت میں کسی بھی نوڈ کے بچوں کو تلاش کرنا ممکن ہے، جو پیرنٹ سب روٹین کی طرف سے دیئے گئے لنکس کو الٹ دیتا ہے: وہ صرف پڑوسی ہیں جن کے والدین دیئے گئے نوڈ ہیں۔ یہ چائلڈ نوڈس کے یہ الٹے لنکس ہیں جو الگورتھم تلاش کرتا ہے۔ اس پھیلے ہوئے درخت کی کلاسیکی گہرائی-پہلی تلاش درخت کو بار بار گزرتی ہے، جڑ سے شروع ہوتی ہے، ہر نوڈ پر تمام بچوں کی فہرست بناتی ہے اور ہر ایک کے لیے بار بار کال کرتی ہے۔ سائیکلوں کے ساتھ گراف کی ڈیپتھ فرسٹ سرچ کے برعکس، بار بار آنے سے بچنے کے لیے پہلے سے دیکھے گئے نوڈس کے سیٹ کو برقرار رکھنا ضروری نہیں ہے ؛ درخت میں اس طرح کی تکرار ممکن نہیں ہے۔ تاہم، اس تکراری الگورتھم کو اب بھی اپنے کال اسٹیک کے لیے بڑی مقدار میں میموری کی ضرورت پڑ سکتی ہے، ایسے معاملات میں جب درخت بہت گہرا ہو۔ اس کے بجائے، ریورس سرچ پھیلے ہوئے درخت کو ایک ہی ترتیب میں عبور کرتی ہے جبکہ صرف دو اشیاء کو محفوظ کرتی ہے: ٹریورسل کا موجودہ آبجیکٹ، اور پہلے سے منتقل شدہ آبجیکٹ۔ ابتدائی طور پر، موجودہ آبجیکٹ کو درخت کی جڑ پر سیٹ کیا جاتا ہے، اور اس میں کوئی پچھلی آبجیکٹ نہیں ہے۔ اس معلومات سے، مندرجہ ذیل کیس تجزیہ کے ذریعے ٹریورسل کے اگلے مرحلے کا تعین کرنا ممکن ہے: اگر کوئی پچھلا آبجیکٹ نہیں ہے، یا پچھلا آبجیکٹ موجودہ آبجیکٹ کا پیرنٹ ہے، تو یہ پہلی بار ہے جب ٹریورسل موجودہ آبجیکٹ تک پہنچا ہے، لہذا یہ سرچ سے آؤٹ پٹ ہے۔ اگلا مقصد اس کا پہلا بچہ یا، اگر اس کی کوئی اولاد نہیں ہے، تو اس کا والدین ہے۔ دیگر تمام صورتوں میں، پچھلا آبجیکٹ موجودہ آبجیکٹ کا بچہ ہونا چاہیے۔ الگورتھم اس پچھلے بچے تک پہنچنے تک بچوں (یعنی موجودہ شے کے ریاستی-خلائی پڑوسیوں جن کے والدین موجودہ شے ہیں) کو ایک وقت میں ایک فہرست دیتا ہے، اور پھر بچوں کی اس فہرست میں ایک اور قدم اٹھاتا ہے۔ اگر دوسرا بچہ اس طرح پایا جاتا ہے، تو یہ اگلا آبجیکٹ ہے۔ اگر کوئی اگلا بچہ نہیں ہے اور موجودہ آبجیکٹ جڑ نہیں ہے، تو اگلا آبجیکٹ موجودہ آبجیکٹ کا والدین ہے۔ بقیہ صورت میں، جب کوئی اگلا بچہ نہیں ہوتا ہے اور موجودہ شے جڑ ہوتی ہے، تو ریورس سرچ ختم ہو جاتی ہے۔ اس الگورتھم میں تلاش کے ہر مرحلے کے لیے کسی شے کے پڑوسیوں کو ایک بار درج کرنا شامل ہے۔ تاہم، اگر کوئی اشیاء درج کی جانی ہیں، تو تلاش اقدامات انجام دیتی ہے، لہذا یہ اشیاء کے پڑوسیوں کو کتنی بار پیدا کرتی ہے اس کی تعداد دو گنا کے عنصر کے اندر ہوتی ہے جو کہ ریکرسو ڈیپتھ-فرسٹ سرچ ایک ہی کام کرے گی۔ ایپلی کیشنز جن مسائل پر ریورس سرچ کا اطلاق کیا گیا ہے ان کی مثالوں میں مندرجہ ذیل مشترکہ نسل کے مسائل شامل ہیں: سادہ کنویکس پولی ٹاپس کے عمودی۔ اگر ایک جہتی کنویکس پولی ٹاپ کو نصف خالی جگہوں کے چوراہے کے طور پر بیان کیا جاتا ہے، تو اس کے عمودی حصوں کو نصف خالی جگہوں پر پابند ہائپر پلین کے چوراہے کے طور پر بیان کیا جا سکتا ہے۔ یہ ایک سادہ پولی ٹاپ ہے اگر کوئی عمودی ان ہائپر پلینوں میں سے زیادہ کا چوراہا نہیں ہے۔ ورٹیکس گنتی کا مسئلہ ان تمام عمودی حصوں کو درج کرنے کا مسئلہ ہے۔ پولیٹوپ کے کنارے عمودی جوڑوں کو جوڑتے ہیں جن میں ہائپرپلین مشترک ہوتے ہیں، لہذا عمودی اور کنارے ایک ریاستی جگہ بناتے ہیں جس میں ہر عمودی کے پڑوسی ہوتے ہیں۔ لکیری پروگرامنگ کے نظریہ سے سمپلیکس الگورتھم ایک ورٹیکس کو تلاش کرتا ہے جو نقاط کے دیئے گئے لکیری فنکشن کو زیادہ سے زیادہ کرتا ہے، ورٹیکس سے ورٹیکس تک چل کر، ہر مرحلے پر فنکشن کی زیادہ قیمت کے ساتھ ایک ورٹیکس کا انتخاب کرتا ہے۔ "پیوٹ رول" کے کئی معیاری انتخاب ہیں جو زیادہ واضح طور پر یہ بتاتے ہیں کہ کس ورٹیکس کا انتخاب کرنا ہے۔ اس طرح کے کسی بھی محور اصول کی تشریح پولیٹوپ کے پھیلے ہوئے درخت کے پیرنٹ فنکشن کی وضاحت کے طور پر کی جا سکتی ہے، جس کی جڑ بہترین ورٹیکس ہے۔ اس ڈیٹا پر ریورس سرچ کا اطلاق پولیٹوپ کے تمام عمودی حصے پیدا کرتا ہے۔ اسی طرح کا الگورتھم لکیری پروگرام کے تمام اڈوں کی گنتی بھی کر سکتا ہے، اس کی ضرورت کے بغیر کہ یہ ایک سادہ پولیٹوپ کی وضاحت کرتا ہے۔ ہائپرپلین انتظامات کے خلیے ایک ہائپرپلین انتظام یوکلڈین اسپیس کو خلیوں میں تحلیل کرتا ہے، ہر ایک کو "سائن ویکٹر" کے ذریعے بیان کیا جاتا ہے جو یہ بیان کرتا ہے کہ آیا اس کے نکات ہائپرپلین (سائن 0) میں سے کسی ایک سے تعلق رکھتے ہیں، ہائپرپلین (سائن + 1) کے ایک طرف ہیں، یا دوسری طرف (سائن-1) ہیں۔ خلیات مقامی چالوں کے تحت ایک منسلک ریاستی جگہ بناتے ہیں جو ایک اکائی کے ذریعے ایک ہی نشان کو تبدیل کرتے ہیں، اور یہ چیک کرنا ممکن ہے کہ یہ عمل لکیری پروگرامنگ فزیبلٹی کے مسئلے کو حل کرکے ایک درست سیل تیار کرتا ہے۔ جڑ کے خلیے کے کسی بھی انتخاب کے لیے ایک پھیلا ہوا درخت ایک پیرنٹ آپریٹر کی وضاحت کر کے بنایا جا سکتا ہے جو پہلی ممکنہ تبدیلی کرتا ہے جو سائن ویکٹر کو جڑ کے قریب لائے گا۔ اس اسٹیٹ اسپیس اور پیرنٹ آپریٹر کے لیے ریورس سرچ کا استعمال کرتے ہوئے تمام خلیوں کو کثیر الجہتی وقت فی سیل میں درج کرنے کے لیے ایک الگورتھم تیار کرتا ہے۔ پوائنٹ سیٹ مثلث ایک پلینر پوائنٹ سیٹ کے مثلث "پلپ" چالوں سے جڑے ہوتے ہیں جو مثلث سے ایک اخترن کو ہٹاتے ہیں اور اسے دوسرے سے بدل دیتے ہیں۔ اگر ڈیلونی مثلث کو جڑ کے طور پر منتخب کیا جاتا ہے، تو ہر مثلث کو ڈیلونی مثلث میں ان مراحل کے ذریعے پلٹا جا سکتا ہے جن میں چار نکات کے کچھ ذیلی سیٹ کے مثلث کو اس کے ڈیلونی مثلث سے تبدیل کیا جاتا ہے۔ ہر مثلث کے والدین کے طور پر پہلے ڈیلونی پلٹ کا انتخاب کرنا، اور مقامی تلاش کو لاگو کرنا، تمام مثلثوں کو کثیر الجہتی وقت فی مثلث میں درج کرنے کے لیے ایک الگورتھم تیار کرتا ہے۔ جڑے ہوئے ذیلی گراف کسی دیئے گئے جڑے ہوئے گراف کے جڑے ہوئے ذیلی گراف، اور جڑے ہوئے محرک ذیلی گراف، ایک ریاستی جگہ بناتے ہیں جس کی مقامی حرکتیں بالترتیب گراف کے ایک کنارے یا سرے کا اضافہ یا ہٹانا ہوتی ہیں۔ اس ریاستی جگہ کا ایک پھیلا ہوا درخت پہلے کنارے یا عمودی (کناروں یا عمودی کے کچھ ترتیب میں) کو شامل کرکے حاصل کیا جا سکتا ہے جس کے اضافے سے ایک اور منسلک ذیلی گراف پیدا ہوتا ہے۔ اس کی جڑ پورا گراف ہے۔ اس ریاستی جگہ اور پیرنٹ آپریٹر پر مقامی تلاش کا اطلاق تمام منسلک ذیلی گرافوں کو کثیر الجہتی وقت فی ذیلی گراف میں درج کرنے کے لیے ایک الگورتھم تیار کرتا ہے۔ دیگر ایپلی کیشنز میں درج ذیل ڈھانچے پیدا کرنے کے لیے الگورتھم شامل ہیں: پولیمینوس، پولی ایمونڈ پروٹوٹائل، اور پولی ہیکس (ریاضی) ہائیڈرو کاربن مالیکیول۔ ایک ریاستی جگہ کا استعمال کرتے ہوئے، جس کی مقامی حرکتیں دو عناصر کی ترتیب کو الٹ دیتی ہیں، ہدایت شدہ سایکلک گراف کی ٹوپوولوجیکل ترتیب۔ گراف کے پھیلے ہوئے درخت، پلینر پوائنٹ سیٹوں کے پھیلے ہوئے درختوں کو پار نہ کرنا، اور زیادہ عام طور پر میٹروئڈز کے اڈے، ایک ریاستی جگہ کا استعمال کرتے ہوئے جو ایک کنارے کو دوسرے کے لیے تبدیل کرتا ہے۔ یولر گراف میں ٹور کرتے ہیں۔ غیر معمولی گرافوں کے زیادہ سے زیادہ آزاد سیٹ۔ زیادہ سے زیادہ طیارہ گراف اور پولی ہیڈرل گراف۔ کسی دیئے گئے پوائنٹ سیٹ پر غیر کراسنگ کم سے کم سخت گراف۔ آس پاس کے کثیر الاضحی، کثیر الاضحی جن میں کچھ دیئے گئے نکات عمودی ہوتے ہیں اور باقی کو گھیرے ہوئے ہوتے ہیں، ایک ریاستی جگہ کا استعمال کرتے ہوئے جو کثیر الاضحی کے ایک سرے کو جوڑتا یا ہٹاتا ہے۔ کنویکس پولی ٹاپس کے منکوسکی مجموعہ کے عمودی یا پہلو۔ یک جہتی آئیڈیلز کے کونے (ملٹی ڈگری)۔ حوالہ جات تلاش الگورتھم مشترکہ الگورتھم