هوش مصنوعی

4-     جستجوی عمقی محدود شده (Depth-limited Search)

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

مثال :در نقشه رومانی 20 شهر وجود دارد. بنابراین می توان گفت که اگر در شهر A است، باید مسیری با حداکثر طول 19 پیدا کند.

ولی مهم ترین عیب این استراتژی این است که اگر عمق تعیین شده آن قدر کوچک باشد که راه حل بهینه در آن عمق وجود نداشته باشد، جستجو ناقص می ماند.

5-     جستجوی عمیق کننده تکراری (Iterative Deepening Search)

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

جستجوی عمیق کننده تکراری (همانند جستجوی سطحی) ابتدا تمامی حالات عمق 0 را بررسی کرد و سپس به سراغ عمق 1 و الی آخر می رود.

بنابراین جستجوی عمیق کننده تکراری مزایای جستجوی سطحی و عمقی را با هم ترکیب می کند.

ویژگی های مثبت

·         کامل است.

·         بهینه است.

·         حافظه اندکی را مورد استفاده قرار می دهد.

این استراتژی از نظر زمانی همانند جستجوی عمقی است.

6-     جستجوی دو طرفه (Bidirectional Search)

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

سخت ترین کار در این استراتژی، یافتن والد های حالت ها(در حرکت رو به عقب) است. مسئله دیگر این است که آیا این گره که ایجاد شده قبلا در درخت جستجوی طرف دیگر ظاهر شده یا نه.

جستجوی سطحی زمانی موفق می شود که شاخه ای از حالت اولیه، شاخه ای از حالت هدف را ملاقات کند. این جستجو در همه ي موارد قابل اجرا نیست.

حال به ارزیابی این شش استراتژی جستجو می پردازیم:

b = فاکتور انشعاب (در هر مرحله چند حالت جدید به وجود می آید؟)

d = عمق پاسخ

m = ماکزیمم عمق درخت جستجو

l = محدودیت عمق