الگوریتم جستجوی عمیق شونده تکراری


در مطلب شماره 13 هوش مصنوعی، یعنی الگوریتم جستجوی عمق اول محدود، توضیح دادیم که در صورت تعیین یک محدوده بر روی درخت جستجو، احتمال بروز خطا و یا گیر افتادن در مسیرهای بسیار طولانی و یا حتی بی نهایت کاهش میابد. (برای درک بهتر این مطلب مبحث الگوریتم جستجوی عمق اول محدود را مطالعه فرمایید). اما ظاهرا انتخاب یک محدوده جهت جلوگیری از رشد بی رویه و بی سرانجام یک درخت جستجو خود میتواند کاری سخت باشد (جلوتر توضیح خواهیم داد). از این رو در این مطلب قصد داریم تا الگوریتم دیگری  با نام الگوریتم جستجوی عمیق شونده تکراری را معرفی نماییم.

در مطلب شماره 13 به شما گفتیم که فرض نمایید نقشه ای متشکل از 20 شهر داریم و میخواهیم از نقطه A به نقطه B برسیم. به این نتیجه رسیدم که با جلوگیری از بوجود آمدن مسیر های تکراری در بدترین حالت باید از 19 شهر بگذریم تا به مقصد برسیم. حال به نقشه زیر که از 20 شهر تشکیل شده است دقت فرمایید؟ آیا واقعا برای رسیدن از هر شهر به شهر دیگر در بدترین حالت باید از 19 شهر بگذریم؟

بررسی الگوریتم جستجوی عمیق شونده تکراری
نقشه ای متشکل از 20 شهر

همانطور که مشاهده میفرمایید در نقشه فوق به علت نحوه جاده کشی آن، در بدترین حالت از هر شهر به شهر دیگر  باید از 9 شهر گذشت! این نشان میدهد که عدد 19 در واقع بدترین ِ بدترین حالات بوده است که ما آن را بدون توجه به نقشه حدس زده ایم.  گرچه این عدد درست بوده ولی میتوانسته به اندازه قابل توجهی کاهش یابد. باید یادمان باشد که همیشه مسئله به کوچکی نقشه فوق نخواهند بود و تعیین عدد ‘محدوده’ با چشم در اغلب اوقات و در مسائل واقعی کاری غیر ممکن است! به عدد 9 اصطلاحا قطر فضای حالت میگویند.

الگوریتم جستجوی عمیق شونده تکراری با استفاده از استراتژی بررسی تمام محدوده های ممکن سعی میکند تا مشکل انتخاب بهترین محدوده را بر طرف نماید. اول عمق 0 سپس عمق 1 بعد از آن عمق 2 تا … جستجو مینماییم. دقیقا مانند نمودار زیر. در واقع الگوریتم جستجوی عمیق شوند تکراری مزایای دو روش جستجوی سطح و عمق اول را با هم ترکیب مینماید. این الگوریتم مانند روش سطح اول کامل بوده و همیشه پاسخ را در کمترین عمق درخت میابد. از طرفی این الگوریتم همانند روش عمق اول از بهینه بودن میزان مصرفی حافظه نیز برخوردار است.

نمایش الگوریتم جستجوی عمیق شونده تکراری
نمایش الگوریتم جستجوی عمیق شونده تکراری

 

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

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

بر طبق الگوریتم جستجوی عمق اول اگر وضعیت هدف در عمق d ام درخت باشد و فاکتور انشعاب برابر با b برای رسیدن به هدف باید تعداد زیر از نودها بر روی درخت ایجاد شود :

1+b+(b^2)+….+(b^(d-2))+(b^(d-1))+(b^d)

پس برای درختی با عمق 5 و فاکتور انشعاب 10 تعداد وضعیت های  ایجاد شده برابر با 111,111 خواهد بود.

حال در صورتی که به جای الگوریتم عمق اول از الگوریتم عمیق شونده تکراری استفاده نماییم، با توجه به فرمول زیر این عدد به 123,456 افزایش خواهد یافت. (فرمول محاسبه تعداد نود های گسترش داده شده در عمیق شونده تکراری)

((d+1)*1)+d*b+(d-1)(b^2)+…+(3b^(d-2))+(2b^(d-1))+(b^d)

از مقایسه دو عدد فوق متوجه میشویم که اختلاف الگوریتم عمیق شونده تکراری با الگوریتم عمق اول در تعداد وضعیت های ایجاد شده بر روی درخت تنها 11% است. پس میتوان نتیجه گرفت که هر چقدر فاکتور انشعاب بزرگتر باشد بار اضافه بر روی وضعیت های ایجاد شده تکراری بر روی درخت کمتر خواهد بود.

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

الگوریتم جستجوی عمیق شونده تکراری
الگوریتم جستجوی عمیق شونده تکراری

Add a Comment

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

Copy Protected by Chetan's WP-Copyprotect.