بخشی از پاورپوینت
--- پاورپوینت شامل تصاویر میباشد ----
اسلاید 1 :
متدهای جستجوی آگاهانه
بهترين جستجو
حريصانه
A*
IDA*
RBFS
SMA*
جستجوی محلی و بهينه سازی
تپه نوردی
شبيه سازی حرارت
پرتو محلی
الگوريتمهای ژنتيک
اسلاید 2 :
مقدمه
الگوریتم های ارائه شده در ابتدای این فصل به خانواده ی الگوریتم های بهترین جستجو (Best First Search) تعلق دارند.
در این الگوریتمها گره ای برای بسط دادن انتخاب می شود که تابع ارزیابی (n)fآنرا مشخص می کند.
تابع ارزیابی ، فاصله تا هدف را اندازه گیری می کند.
در ادامه ی فصل ، الگوریتمهای جستجوی محلی و مسائل بهینه سازی بررسی خواهند شد.
اسلاید 3 :
تعاریف
تابع هزينه مسير، g(n) : هزينه مسير از گره اوليه تا گره n
تابع اکتشافی، h(n) : هزينه تخمينی ارزان ترين مسير از گره n به گره هدف
تابع بهترين مسير، h*(n) : هزینه ی واقعی ارزان ترين مسير از گره n تا گره هدف
تابع ارزيابي، f(n) : هزينه تخمينی ارزان ترين مسير از طريق n
اسلاید 4 :
جستجوی حریصانه
جستجوی حریصانه سعی می کند نزدیک ترین گره به هدف را بسط دهد.
در واقع تابع ارزیابی f(n)=h(n) می باشد که h(n) به نام تابع اکتشافی(heuristic)شناخته می شود و داریم:
هزینه ی تخمینی ارزان ترین مسیر از گره n به گره هدف h(n)=n
جستجوی حریصانه هیچ توجهی به هزینه ی مسیر تا رسیدن به گره فعلی ندارد.
اسلاید 5 :
جستجوی حریصانه در نقشه رومانی
برای این منظور از تابع فاصله مستقيم به عنوان تابع اکتشافی استفاده می کنیم.
تابع فاصله مستقيم، فاصله ی خط مستقیم هر شهر تا هدف یعنی بخارست را نشان می دهد.
اسلاید 6 :
جستجوی حریصانه در نقشه رومانی(ادامه1)
اسلاید 7 :
جستجوی حریصانه در نقشه رومانی(ادامه2)
اسلاید 8 :
جستجوی حریصانه در نقشه رومانی(ادامه3)
اسلاید 9 :
جستجوی حریصانه در نقشه رومانی(ادامه4)
اسلاید 10 :
جستجوی حریصانه (مثال 2)
