مثال :

امیدوارم نقشه رومانی رو یادتون نرفته باشه! یک تابع کشف کننده خوب برای مسائل مسیریابی، مانند این مسئله، تابع مسافت مستقیم تا هدف است.

h_SLD(n) : مسافت مستقیم بین n و مکان هدف.

فاصله مستقیم بین شهر های نقشه  و هدف :

با محاسبه مقادیر h_SLD در این مسئله، تابع کشف کنندگی حالت مطلوب را ارائه می دهد. زیرا یک مسیر A به B را معمولا در جهت درست هدایت می کند.

با بررسی درخت جستجوی حریصانه برای رسیدن به بخارست، به این نتیجه می رسیم که استراتژی ترجیح می دهد که راه بزرگتر را برای رسیدن به هدف پیدا کند(زیرا راهی که انتخاب کرده 32 کیلومتر طولانی تر از راه  Rimnicuاست.)، بدون اینکه نگرانی ای در مورد طولانی بودن آن داشته باشد. از این رو نام حریصانه برای این استراتژی کاملا مناسب است.

گرچه حرص یکی از هفت گناه کبیره است!! ولی الگوریتم های حریص اغلب کارآیی خوبی دارند. آن ها تمایل به یافتن راه حل های سریع دارند.

اگر چه همانطور که در این مثال نشان داده شد، آن ها همیشه راه حل بهینه را پیدا نمی کنند.

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

ویژگی ها

از شناسایی های مشابه گریزان است.

بهینه نیست.

کامل نیست.

پیچیدگی فضای آن O(b^m) است. (m = حداکثر عمق فضای جستجو)

پیچیدگی زمان آن O(b^m) است.

·   حداقل سازی مجموع هزینه مسیر : جستجوی A*

جستجوی حریصانه هزینه تخمین زده شده h(n) به سمت هدف را به حداقل می رساند و به موجب آن، هزینه جستجو را به مقدار قابل ملاحظه ای کاهش می دهد. ولی نه بهینه و نه کامل است.

همچنین جستجو با هزینه یکسان، هزینه مسیر g(n) را به حداقل می رساند و علاوه بر آن بهینه و کامل نیز هست.

اگر بتوانیم دو استراتژی را (برای دست یابی به مزایای آن ها) ترکیب کنیم، بهترین کار را انجام داده ایم.

این کار به این صورت انجام می شود :

f(n) = g(n) + h(n)

در نتیجه :

هزینه تخمین زده شده ارزانترین راه حل از طریق n = f(n)

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

این استراتژی جستجو را جستجوی A* می گویند.

نوشته شده توسط حسین | موضوع: سیستم های جستجو | لینک ثابت | | | |