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


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

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

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

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

بکارگیری الگوریتم جستجوی دو طرفه در پروژه مسیر یاب
بکارگیری الگوریتم جستجوی دو طرفه در پروژه مسیر یاب
One Comment

Add a Comment

Your email address will not be published. Required fields are marked *

Copy Protected by Chetan's WP-Copyprotect.