بخشی از پاورپوینت

--- پاورپوینت شامل تصاویر میباشد ----

اسلاید 1 :

جستجوي اول-بهترين
جستجوي حريصانه
جستجوي A*
جستجوي A* حافظه محدود
جستجوي عميق كننده تكراريA*
جستجوي اول بهترين بازگشتي(RBFA*)
SMA*
هيوريستيك ها
الگوريتم هاي جستجوي محلي
جستجوي simulated annealing
الگوريتم هاي ژنتيك
جستجوي online

اسلاید 2 :

نمونه اي از الگوريتم عمومي tree-search يا graph-search است که در ان يک گره بر اساس يک تابع ارزيابي f(n) براي گسترش انتخاب مي شود.
تابع ارزيابي evaluation function تخمين ”ميزان مطلوب بودن“ گره
هربار مطلوب ترين گره گسترش نيافته را بسط مي دهد.
پياده سازي:
گره ها در fringe به ترتيب نزولي ميزان مطلوبيت مرتب مي شوند.
يك صف اولويت
حالت هاي خاص
جستجوي حريصانه Greedy search
جستجوي A*

اسلاید 3 :

تابع هيوريستيك h(n)
هزينة تخميني مسير از گره n تا نزديکترين گره هدف
براي مثال، در نقشه روماني مي توان هزينة مسير از هر شهري به بخارست را از طريق مسافت يك خط مستقيم از آن شهر به بخارست تخمين زد.
hSLD(n) فاصله مستقيم از n تا بخارست
جستجوي اول -بهترين حريصانه
جستجوي حريصانه گره اي را گسترش مي دهد كه به نظر مي رسد نزديكترين گره به هدف ( بخارست) باشد.
تابع ارزيابي f(n)= h(n)

اسلاید 4 :

كامل؟
–خير (ممکن است در حلقه بينهايت گير کند)
پيچيدگي زماني؟
O(bm) – اما با يک هيوريستيک خوب مي تواند به شدت بهبود يابد
پيچيدگي حافظه؟
– O(bm) تمام گره ها را در حافظه نگه مي دارد.
بهينه؟
– خير (مثلا در مثال قبل مسير بهينه اي وجود دارد که از ديد جستجوي حريصانه مخفي مي ماند).

اسلاید 5 :

ايده: از گسترش مسيرهايي كه تاكنون مشخص شده پرهزينه مي باشند، اجتناب كن. 
تابع ارزيابي
f(n) = g(n) + h(n)
 
 

اسلاید 6 :

يك هيوريستيك h(n) قابل قبول است اگر براي هر گره n داشته باشيم :
h(n) ≤ h*(n)
که h*(n) هزينه واقعي براي رسيدن به هدف از گره n مي باشد.
يك هيوريستيك قابل قبول هرگز هزينه رسيدن به هدف را بيش از حد تخمين نمي زند، يعني خوش بينانه است.
مثال: هيوريستيكhSLD(n) هيچگاه فاصله را بيش از حد واقعي تخمين نمي زند.
قضيه: اگر h(n) قابل قبول باشد، A* با استفاده از TREE-SEARCH بهينه است

اسلاید 7 :

اگر به جايTREE–SEARCH از GRAPH–SEARCH استفاده كنيم، آنگاه قضيه قبل ديگر صدق نمي كند.
ممكن است راه حلهاي نيمه بهينه برگردانده شوند، زيرا GRAPH–SEARCH مي تواند ميسر بهينه به يك حالت تكراري را كنار بگذارد، اگر اولين گره توليدي نباشد.
دو راهکار براي حل اين مشكل:
اولين راه حل، اين است كه GRAPH–SEARCH را به نحوي توسعه بدهيم كه از بين مسيري كه به يك گره مي رسد آن مسيري كه پرهزينه تر است را كنار بگذارد. اين روش فضاي زيادي اشغال مي كند، اما بهينگي را تضمين مي كند.
راه حل دوم، اطمينان از اين موضوع است كه مسير بهينه به هر حالت تكراري، هميشه اولين مسيري است كه دنبال مي شود. شرط سازگاري (يا يكنواختي)

اسلاید 8 :

يك هيوريستيك سازگار  consistent است اگر 
h(n) ≤ c(n,a,n') + h(n')
 
 
 
شكلي از قانون كلي نامساوي مثلث است كه تصريح  مي كند هيچ ضلعي از يك مثلث نمي تواند بلندتر از مجموع دو ضلع ديگر باشد.
هر هيوريستيك سازگار، قابل قبول نيز هست.
قضيه: اگر h(n) سازگار باشد، A* با استفاده از GRAPH–SEARCH بهينه است

اسلاید 9 :

اگر h(n) سازگار باشد آنگاه f(n) در طول هر مسيري، غيرنزولي است. 
f(n') = g(n') + h(n') 
      = g(n) + c(n,a,n') + h(n') 
      ≥ g(n) + h(n) 
      = f(n)
 
 
 
 
مي توان نتيجه گرفت كه رشته اي از گره ها كه توسطA* با استفاده از GRAPH–SEARCH گسترش يافته اند به ترتيب غيرنزولي f(n) مي باشد. 
در نتيجه، اولين گره هدفي كه براي گسترش انتخاب مي شود بايد يك راه حل بهينه باشد، زيرا تمامي گره هاي بعدي حداقل به همان اندازه هزينة خواهند داشت.

اسلاید 10 :

اولين راه حل پيداشده، بايد يك راه حل بهينه باشد
زيرا گره هاي هدف در تمامي contourهاي بعدي داراي هزينه f بيشتري خواهند بود و در نتيجه هزينة G بالاتري نيز دارند (زيرا تمامي گره هاي هدف داراي h(n)=0 هستند).
جستجوي A* كامل است.
همان طور كه نوارهاي با f در حال افزايش را اضافه مي كنيم، بايد بالاخره به نواري برسيم كه در آنجا f مساوي هزينة مسير تا يك حالت هدف است.

در متن اصلی پاورپوینت به هم ریختگی وجود ندارد. برای مطالعه بیشتر پاورپوینت آن را خریداری کنید