برداشت کلی شما از مقاله‌ی داده‌شده چیست؟

مقاله: این الگوریتم دو جستجوی همزمان را اجرا می‌کند: یکی جلو رونده از راس اولیه، و یکی عقب رونده از راس هدف، توقف هنگامی صورت می‌گیرد که دو جستجو در میان راه یکدیگر را ملاقات کنند. دلیل برای این رویکرد این است که در بسیاری از موارد بسیار سریع‌تر است: به عنوان مثال، در یک مدل ساده از مسئله پیچیدگی جستجو که در آن هر دو جستجوها یک درخت با ضریب انشعاب b گسترش پیدا می‌کنند، و فاصله از راس اولیه به راس هدف d می‌باشد، هر یک از دو جستجو دارای پیچیدگی (در نماد o بزرگ) می‌باشند، و مجموع پیچیدگی این دو جستجو بسیار کمتر از پیچیدگی می‌باشد که پیچیدگی یک جستجوی تنها از همان راس ابتدا به راس هدف است. این تسریع در امر پاسخگویی با دادن یک هزینه همراه است: یک الگوریتم جستجوی دو جهته باید شامل منطق اضافی باشد تا تصمیم بگیرد که در هر مرحله جستجو کدام درخت جستجو گسترش یابد، مشکلات پیاده‌سازی افزایش می‌یابد، راس هدف باید شناخته‌شده باشد (به جای داشتن یک هدف کلی که ممکن است توسط بسیاری از حالات ملاقات شود)، الگوریتم باید قادر به بازگشتن از راس هدف به راس اولیه باشد (که بدون کار اضافی ممکن نیست)، و الگوریتم نیاز به یک راه مؤثر برای پیدا کردن محل تقاطع دو درخت جستجو دارد. علاوه بر این، ضریب انشعاب جستجوی عقب رونده ممکن است با جستجوی جلو رونده متفاوت باشد. پیچیدگی اضافی برای انجام یک جستجوی دو جهته بدان معنی است که یک الگوریتم جستجوی a* اغلب یک انتخاب بهتر است اگر تابع شهودی ما (هیورستیک) یک تابع منطقی باشد. همانند جستجوی a*، جستجوی دو جهته می‌تواند با برآورد اکتشافی از فاصله باقی‌مانده تا راس هدف (در درخت جلو رونده) یا ازراس اولیه (در درخت عقب رونده) هدایت شود. یک اکتشاف قابل‌قبول همچنین می‌تواند کوتاه‌ترین راه‌حل را به دست آورد، همان‌طور که برای a* به اثبات رسیده است. گره‌ای که از جلو در حال گسترش است دارای کمترین تعداد گره باز و محتمل‌ترین گره است. پایان الگوریتم زمانی اتفاق می‌افتد که یک گره در گروه دیگر هم باشد. ارزش f - فرزندان گره را باید در ارزش g – همه گره‌ها در گروه دیگر حساب شود. از این رو گسترش گره در این روش از a* پر هزینه‌تر است. همان‌طور که در بالا ذکر شد می‌توان الگوریتم را به گونه‌ای هدایت کرد که مجموعه گره‌های ملاقات شده کوچکتر شود. بنابراین می‌توانیم در فضای کمتری محاسبه بیشتری انجام دهیم …
برداشت:
الگوریتم جستجوی دو جهته الگوریتمی برای جستجوی گراف است که کوتاهترین مسیر در یک گراف جهت دار را از راس اولیه به راس هدف می‌یابد .