Bidirectional search
دو طرفہ تلاش ایک گراف سرچ الگورتھم ہے جو ایک ہدایت شدہ گراف میں ابتدائی ورٹیکس سے گول ورٹیکس تک کا مختصر ترین راستہ تلاش کرتا ہے۔ یہ بیک وقت دو تلاشیں چلاتا ہے: ایک ابتدائی حالت سے آگے، اور ایک گول سے پیچھے، جب دونوں ملتے ہیں تو رکتے ہیں۔ اس نقطہ نظر کی وجہ یہ ہے کہ بہت سے معاملات میں یہ تیز ہے: مثال کے طور پر، تلاش کے مسئلے کی پیچیدگی کے ایک آسان ماڈل میں جس میں دونوں تلاشیں برانچنگ فیکٹر b کے ساتھ ایک ٹری کو بڑھاتی ہیں، اور شروع سے گول تک کا فاصلہ d ہوتا ہے، دونوں تلاشوں میں سے ہر ایک میں پیچیدگی O (bd/2) (بگ O نوٹیشن میں) ہوتی ہے، اور ان دونوں تلاش کے اوقات کا مجموعہ O (bd) پیچیدگی سے بہت کم ہوتا ہے جو شروع سے لے کر مقصد تک ایک ہی تلاش کے نتیجے میں ہوتا ہے۔ اینڈریو گولڈ برگ اور دیگر نے ڈیجسٹرا کے الگورتھم کے دو طرفہ ورژن کے لیے صحیح اختتامی شرائط کی وضاحت کی۔ جیسا کہ اے * سرچ میں، دو طرفہ تلاش کی رہنمائی گول (فارورڈ ٹری میں) یا شروع سے (بیکورڈ ٹری میں) باقی فاصلے کے ہیورسٹک تخمینے سے کی جا سکتی ہے۔ وہ سب سے پہلے تھا جس نے دو طرفہ ہیورسٹک سرچ الگورتھم کو ڈیزائن اور نافذ کیا۔ شروع سے نکلنے والے سرچ ٹری اور گول نوڈس حل کی جگہ کے بیچ میں ملنے میں ناکام رہے۔ بی ایچ ایف ایف اے الگورتھم نے اس عیب چیمپیکس (1977) کو ٹھیک کیا۔ ایک قابل قبول ہیورسٹک کا استعمال کرتے ہوئے یونی ڈائرکشنل A * الگورتھم کے ذریعہ پایا جانے والا حل راستے کی لمبائی میں سب سے کم ہوتا ہے۔ یہی خاصیت ڈی چیمپیکس (1983) میں بیان کردہ BHFFA2 بائی ڈائرکشنل ہیورسٹک ورژن کے لیے بھی ہے۔ بی ایچ ایف ایف اے 2 میں، دوسروں کے درمیان، بی ایچ ایف ایف اے کے مقابلے میں زیادہ محتاط اختتامی شرائط ہیں۔ تفصیل ایک دو طرفہ ہیورسٹک سرچ کسی ریاست سے دوسری ریاست میں ریاستی خلائی تلاش ہے، جو بیک وقت آنے جانے کی تلاش کرتی ہے۔ یہ آپریٹرز کی ایک درست فہرست واپس کرتا ہے جس پر اگر درخواست دی جائے تو ہمیں دے گا۔ اگرچہ ایسا لگتا ہے کہ آپریٹرز کو ریورس سرچ کے لیے الٹا ہونا پڑتا ہے، لیکن کسی بھی نوڈ کو دیکھتے ہوئے، صرف اس طرح کے پیرنٹ نوڈس کا سیٹ تلاش کرنا ضروری ہے کہ ہر پیرنٹ نوڈس سے کچھ درست آپریٹر موجود ہو۔ اسے اکثر روٹ فائنڈنگ ڈومین میں یک طرفہ گلی سے تشبیہ دی جاتی ہے: دونوں سمتوں میں سفر کرنے کے قابل ہونا ضروری نہیں ہے، لیکن سڑک کے آخر میں کھڑے ہونے پر یہ ضروری ہے کہ ممکنہ راستے کے طور پر گلی کے آغاز کا تعین کیا جائے۔ اسی طرح، ان کناروں کے لیے جن میں الٹا آرکس ہوتے ہیں (یعنی۔ دونوں سمتوں میں جانے والے آرکس) یہ ضروری نہیں ہے کہ ہر سمت کی قیمت برابر ہو۔ ریورس سرچ ہمیشہ الٹا لاگت کا استعمال کرے گی (یعنی۔ آگے کی سمت میں آرک کی لاگت)۔ مزید رسمی طور پر، اگر پیرنٹ کے ساتھ نوڈ ہے، تو، اس کی تعریف لاگت سے لاگت کے طور پر کی گئی ہے۔ (Auer Kaindl 2004) اصطلاحات اور اشارے تلاش کے درخت کی شاخ سازی کا عنصر نوڈ سے نوڈ میں منتقل ہونے سے وابستہ لاگت جڑ سے نوڈ تک کی لاگت نوڈ اور مقصد کے درمیان فاصلے کا ہیورسٹک تخمینہ موجودہ تلاش کی سمت کو ظاہر کرتا ہے (بعض اوقات، فنکشن کے ساتھ الجھن میں نہ پڑنا)۔ روایت کے مطابق، آگے کی سمت کے لیے 1 اور پیچھے کی سمت کے لیے 2 کے برابر ہے (کوا 1989) مخالف تلاش کی سمت (یعنی) د کی سمت میں سرچ ٹری۔ اگر، جڑ ہے، اگر، جڑ کے پتے ہیں (بعض اوقات کہا جاتا ہے)۔ اس سیٹ سے توسیع کے لیے نوڈ کا انتخاب کیا جاتا ہے۔ دو طرفہ تلاش میں، انہیں بعض اوقات سرچ 'فرنٹیئرز' یا 'ویو فرنٹس' کہا جاتا ہے، جس سے یہ ظاہر ہوتا ہے کہ جب کسی تلاش کو گرافک طور پر پیش کیا جاتا ہے تو وہ کیسے ظاہر ہوتے ہیں۔ اس استعارہ میں، 'تصادم' اس وقت ہوتا ہے جب توسیعی مرحلے کے دوران، ایک لہر کے محاذ سے ایک نوڈ مخالف لہر کے محاذ میں جانشین پایا جاتا ہے۔ کے غیر پتوں والے نوڈس۔ اس سیٹ میں وہ نوڈس شامل ہیں جو پہلے سے ہی سرچ اپروچز کے ذریعے دو طرفہ ہیورسٹک سرچ کے لیے دیکھے گئے ہیں۔ دو طرفہ الگورتھم کو وسیع پیمانے پر تین زمروں میں تقسیم کیا جا سکتا ہے: فرنٹ ٹو فرنٹ، فرنٹ ٹو بیک (یا فرنٹ ٹو اینڈ)، اور پیریمیٹر سرچ (کینڈل کینز 1997)۔ یہ ہیورسٹک کا حساب لگانے کے لیے استعمال ہونے والے فنکشن سے مختلف ہوتے ہیں۔ فرنٹ ٹو بیک فرنٹ ٹو بیک الگورتھم مخالف سرچ ٹری کے جڑ کے درمیان ہیورسٹک تخمینہ کا استعمال کرتے ہوئے نوڈ کی قیمت کا حساب لگاتے ہیں، یا۔ فرنٹ ٹو بیک تین زمروں میں سب سے زیادہ فعال طور پر تحقیق شدہ ہے۔ موجودہ بہترین الگورتھم (کم از کم پندرہ پہیلی ڈومین میں) بیمیکس-بی ایس * ایف الگورتھم ہے، جسے آؤر اور کینڈل (آؤر، کینڈل 2004) نے بنایا ہے۔ فرنٹ ٹو فرنٹ الگورتھم کے درمیان اور کچھ ذیلی سیٹ کا استعمال کرتے ہوئے نوڈ کی قیمت کا حساب لگاتا ہے۔ کینونکل مثال بی ایچ ایف ایف اے (بائی ڈائرکشنل ہیورسٹک فرنٹ ٹو فرنٹ الگورتھم) کی ہے، جہاں فنکشن کو موجودہ نوڈ اور مخالف محاذ پر موجود نوڈس کے درمیان تمام ہیورسٹک تخمینوں کے کم از کم کے طور پر بیان کیا جاتا ہے۔ یا، رسمی طور پر: جہاں قابل قبول واپسی ہوتی ہے (یعنی۔ زیادہ اندازہ نہ لگانا) نوڈس اور نوڈس کے درمیان فاصلے کا ہیورسٹک تخمینہ۔ فرنٹ ٹو فرنٹ کمپیوٹیشنل طور پر ضرورت سے زیادہ مطالبہ کرنے کا شکار ہے۔ ہر بار جب کسی نوڈ کو کھلی فہرست میں ڈالا جاتا ہے، تو اس کی قیمت کا حساب لگانا ضروری ہے۔ اس میں مخالف سیٹ کے ہر نوڈ سے ہیورسٹک تخمینہ لگانا شامل ہے، جیسا کہ اوپر بیان کیا گیا ہے۔ تمام ڈومینز کے لیے سیٹ کے سائز میں تیزی سے اضافہ ہوتا ہے۔ حوالہ جات۔ ۔ ۔ ۔ گراف الگورتھم سرچ الگورتھم