الگوریتم جست وجوی دوطرفه bidirectional search

الگوریتم جست وجوی دوطرفه bidirectional search

ایده جست وجوی دوطرفه از استراتژی های جست وجوی ناآگاهانه است و اجرای دو جست وجو بطور همزمان است. یکی از آنها از حالت شروع به حالت هدف و دیگری از حالت هدف به حالت شروع با این هدف که دو جست وجو به هم برسند، انجام میپذیرند.

در الگوریتم جست وجوی دوطرفه به جای بررسی آزمون هدف، این بررسی میشود که مرز دو جست وجو یکدیگر را قطع میکنند یا خیر. در صورت قطع یکدیگر، یعنی جوابی پیدا شده است. هنگام تولید گره، یا وقتیکه  گره برای بسط انتخاب میشود، این بررسی انجام میگیرد. اگر از جدول درهم سازی استفاده شود، این بررسی در زمان ثابتی انجام میشود.

پیچیدگی زمانی و فضا در جست وجوی دوطرفه با استفاده از جست وجو های عرضی در هر دو جهت برابر است با : O(b^d/2) . اگر یکی از دو جست وجوها به روش IDS (جست وجوی تعمیق تکراری) انجام گیرد، میزان فضای مصرفی را میتوان نصف کرد، اما حداقل یکی از مرزها باید در حافظه نگهداری شود تا بتوان تقاطع آنها را بررسی کرد.  مهمترین ضعف الگوریتم جست وجوی دوطرفه این میزان حافظه مورد نیاز است.

برای انجام جستوجوی عقب گرد، باید پیشینهای حالت x را تمام حالتهایی تعریف کنیم که x بعنوان پسین آنهاست. جستوجوی دوطرفه به روشی برای  محاسبه پیشین ها نیاز دارد. وقتی تمام فعالیتها در فضای حالت برگشت پذیر باشند پیشین های x، همان پسینهای x هستند.

در جستوجوی عقبگرد از هدف، هدف باید مشخص باشد. اگر چندین حالت هدف بطور صریح مشخص شده باشند، آنگاه میتوان حالت هدف ساختگی جدیدی را ایجاد کرد که پیشین های بلافصل آن، حالت های هدف واقعی هستند. ولی اگر هدف یک توصیف انتزاعی باشد، مثل هدف مسئله هشت وزیر که: "هیچ وزیری ، وزیر دیگر را گارد ندهد"، استفاده از جست وجوی دوطرفه دشوار خواهد بود.