جستجوی دوجهته

الگوریتم جستجوی دو جهته الگوریتمی برای جستجوی گراف است که کوتاهترین مسیر در یک گراف جهت دار را از راس اولیه به راس هدف می یابد.

پیچیدگی

این الگوریتم دو جستجوی همزمان را اجرا می‌کند: یکی جلو رونده از راس اولیه ، و یکی عقب رونده از راس هدف، توقف هنگامی صورت می‌گیرد که دو جستجو در میان راه یکدیگر را ملاقات کنند. دلیل برای این رویکرد این است که در بسیاری از موارد بسیار سریع تر است: به عنوان مثال، در یک مدل ساده از مسئلهٔ پیچیدگی جستجو که در آن هر دو جستجوها یک درخت با ضریب انشعاب B گسترش پیدا می‌کنند، و فاصله از راس اولیه به راس هدف d می‌باشد ، هر یک از دو جستجو دارای پیچیدگی $O(b^{d/2})$ (در نماد O بزرگ) می‌باشند ، و مجموع پیچیدگی این دو جستجو بسیار کمتر از پیچیدگی $O(b^{d})$ می‌باشد که پیچیدگی یک جستجوی تنها از همان راس ابتدا به راس هدف است.

معایب

این تسریع در امر پاسخگویی با دادن یک هزینه همراه است: یک الگوریتم جستجوی دو جهته باید شامل منطق اضافی باشد تا تصمیم بگیرد که در هر مرحلهٔ جستجو کدام درخت جستجو گسترش یابد، مشکلات پیاده‌سازی افزایش می یابد، راس هدف باید شناخته شده باشد (به جای داشتن یک هدف کلی که ممکن است توسط بسیاری از حالات ملاقات شود) ، الگوریتم باید قادر به بازگشتن از راس هدف به راس اولیه باشد (که بدون کار اضافی ممکن نیست)، و الگوریتم نیاز به یک راه مؤثر برای پیدا کردن محل تقاطع دو درخت جستجو دارد. علاوه بر این، ضریب انشعاب جستجوی عقب رونده ممکن است با جستجوی جلو رونده متفاوت باشد. پیچیدگی اضافی برای انجام یک جستجوی دو جهته بدان معنی است که یک الگوریتم جستجوی A* اغلب یک انتخاب بهتر است اگر تابع شهودی ما (هیورستیک) یک تابع منطقی باشد.

ویژگی ها

همانند جستجوی A* ، جستجوی دو جهته می‌تواند با برآورد اکتشافی از فاصله باقی‌مانده تا راس هدف (در درخت جلو رونده) یا ازراس اولیه (در درخت عقب رونده) هدایت شود.یک اکتشاف قابل قبول همچنین می‌تواند کوتاه‌ترین راه حل را به دست آورد، همان‌طور که برای A* به اثبات رسیده است.

گره ای که از جلو در حال گسترش است دارای کمترین تعداد گرهٔ باز و محتمل‌ترین گره است. پایان الگوریتم زمانی اتفاق می افتد که یک گره در گروه دیگر هم باشد. ارزش F - فرزندان گره را باید در ارزش G – همهٔ گره‌ها در گروه دیگر حساب شود. از این رو گسترش گره در این روش از A* پر هزینه تر است. همان‌طور که در بالا ذکر شد می‌توان الگوریتم را به گونه ای هدایت کرد که مجموعهٔ گره‌های ملاقات شده کوچکتر شود. بنابراین می توانیم در فضای کمتری محاسبهٔ بیشتری انجام دهیم. مرجع 1977 نشان می‌دهد که الگوریتم دو جهته پاسخ را می یابد در حالی که الگوریتم A* از فضای داده شده، فضای بیشتری را اشغال می‌کند. همچنین مسیرهای کوتاه تری نیز پیدا می‌شوند اگر از تابع‌های شهودی غیر منطقی استفاده شود. این تست‌ها توسط $IraPohl$ در 15-پازل انجام گرفته‌است.

$IraPohl$ اولین کسی بود که یک الگوریتم جستجوی دو طرفهٔ هیورستیک را طراحی و پیاده‌سازی کرد. در این پیاده‌سازی یک گرهٔ فرزند در یک مرز جستجو فقط به گره‌ها در گروه دیگر مرتبط است. او گزارش کرد که دو درختی که از هر یک از جستجوها تشکیل می‌شود در فضای میانی همدیگر را ملاقات نکردند. بعدها او و یکی از شاگردانش به نام $GeorgePolitowski$ الگوریتم او را با گرفتن $D$ - گره به عنوان واسطهٔ طبیعی اصلاح کردند.

منابع

• de Champeaux, Dennis; Sint, Lenie (1977), "An improved bidirectional heuristic search algorithm", Journal of the ACM, 24 (2): 177–191, doi:10.1145/322003.322004.
• de Champeaux, Dennis (1983), "Bidirectional heuristic search again", Journal of the ACM, 30 (1): 22–32, doi:10.1145/322358.322360.
• Pohl, Ira (1971), "Bi-directional Search", in Meltzer, Bernard; Michie, Donald (eds.), Machine Intelligence, vol. 6, Edinburgh University Press, pp. 127–140.
• Russell, Stuart J.; Norvig, Peter (2002), "3.4 Uninformed search strategies", هوش مصنوعی: رهیافتی نوین (2nd ed.), Prentice Hall.