قابل پذیرش بودن تابع هیورستیک (Admissible heuristic) در الگوریتم *A

در این ویدئو به دنبال این هستیم تا به بیان ساده قابل پذیرش بودن تابع هیورستیک (Admissible heuristic) در الگوریتم *A را نمایش دهیم. جستجوی حریصانه میتواند زمان جستجو را اما کاهش دهد نه کامل است نه بهینه. در جستجو با هزینه یکسان هزینه مسیر را نیز حداقل می کند . جستجوی با هزینه یکسان هم بهینه هست هم کامل اما می تواند بسیار بی فایده .باشد اگر ما بتوانیم دو استراتژی را برای دست یافتن به مزایای هر دو جستجوترکیب کنیم ، بهترین کار را انجام می دهیم . خوشبختانه می توانیم با ترکیب دو تابع ارزیابی به این امر دست یابیم .F(n) = g(n) + h(n)-

اگـــر تـــابع هیوریـــستیک شـــرایط لازم را داشـــته باشـــد A* کامـــل وبهینـــه اســـت A*. کـــه ازGraph searchاستفاده می کنـد بـه شـرطی بهینـه اسـت کـه (h(nسـازگار یـا یکنواخـت باشـد و *Aکه ازTree searchاستفاده می کند به شرطی بهینه است که)(h(nقابل قبول باشد.

تابع هیوریستیکی قابل قبول است کـه هرگـز هزینـه رسـیدن بـه هـدف را بیـشتر از هزینـه واقعـی تخمـین نزنــد.ــه عبــارت دیگر،یــک هیورســتیک ماننــد (h(nقابــل قبــول اســت اگــر بــرای هــر گــره nداشــته باشـیم:

(n)<=h*(n)کـه در ایـن رابطـه(h*(nهزینـه واقعـی بـرای رسـیدن بـه هـدف از گـره nمـی باشد.از آنجایی کـه (g(nهزینـه واقعـی رسـیدن بـه nاسـت اگـر(h(nقابـل قبـول باشـد آنگـاه(f(n)نیـزقابل قبول خواهد بود یعنی(f(nهرگز بیشتر از هزینه واقعی راه حل از طریق nتخمین نمی زند.

دریافت جزوه