قضیه قابل پذیرش بودن تابع هیورستیک

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

جستجوي حريصانه ميتواند زمان جستجو را اما كاهش دهد نه كامل است نه بهينه. در جستجو با هزينه يكسان هزينه مسير را نيز حداقل مي كند . جستجوي با هزينه يكسان هم بهينه هست هم كامل اما مي تواند بسيار بي فايده .باشد اگر ما بتوانيم دو استراتژي را براي دست يافتن به مزاياي هر دو جستجوتركيب كنيم ، بهترين كار را انجام مي دهيم . خوشبختانه مي توانيم با تركيب دو تابع ارزيابي به اين امر دست يابيم .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تخمين نمي زند.

لینک قضیه قابل پذیرش بودن تابع هیورستیک در ویکی پدیا

دانلود جزوه

دانلود ویدئو

(۳۷۰۱)