پاورپوینت هوش مصنوعی فصل چهارم جست و جوی آگاهانه و اکتشاف

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

اسلاید 1 :

هوش مصنوعي
فصل چهارم
جست و جوی آگاهانه و اکتشاف

اسلاید 2 :

هوش مصنوعي Artificial Intelligence
فهرست
متدهای جست و جوی آگاهانه
يادگيری برای جست و جوی بهتر
جست و جوی محلی و بهينه سازی

اسلاید 3 :

جست و جوی آگاهانه و اکتشاف
متدهای جستجوی آگاهانه
جستجوی بهترین
حريصانه
A*
IDA*
RBFS
جستجوی محلی و بهينه سازی
تپه نوردی
شبيه سازی حرارت
پرتو محلی

اسلاید 4 :

جستجوی بهترین Best First Search
اين استراتژي به اين صورت بيان ميشود که در يک درخت، زماني که گرهها مرتب ميشوند، گرهاي که بهترين ارزيابي را داشته باشد، قبل از ديگر گرهها بسط داده ميشود.

هدف: يافتن راهحلهاي کمهزينه است، اين الگوريتمها عموماً از تعدادي معيار تخمين براي هزينه راهحلها استفاده ميکنند و سعي بر حداقل کردن آنها دارند.

اسلاید 5 :

جست و جوی آگاهانه و اکتشاف
تعاريف
تابع هزينه مسير، g(n) : هزينه مسير از گره اوليه تا گره n
تابع اکتشافی، h(n) : هزينه تخمينی ارزان ترين مسير از گره n به گره هدف (هزينه رسيدن به هدف از يک حالت ويژه ميتواند تخمين زده شود اما دقيقاً تعيين نميشود. تابعي که چنين هزينههايي را محاسبه ميکند تابع اکتشافی یا کشفکننده h ناميده ميشود.)
تابع ارزيابي، f(n) : هزينه تخمينی ارزان ترين مسير از طريق n

اسلاید 6 :

جستجوي حريصانه:
يکي از سادهترين استراتژيهاي جستجوي بهترين، به حداقل رساندن هزينه تخمين زده شده براي رسيدن به هدف است. بدين صورت که حالت گرهاي که به حالت هدف نزديکتر است، ابتدا بسط داده ميشود.
در این حالت تابع ارزیابی : f(n) = h(n)

اسلاید 7 :

جست و جوی آگاهانه و اکتشاف
جستجوی حريصانه

اسلاید 9 :

Romania with step costs in km

اسلاید 10 :

Greedy best-first search example

اسلاید 11 :

Greedy best-first search (جستجوی حریصانه)

اسلاید 15 :

کامل بودن: خير
اما اگر h = h* آنگاه جستجو کامل ميشود (h* هزینه واقعی گره n تا هدف است)
بهينگی: خير
اما اگر h = h* آنگاه جستجو کامل ميشود
پيچيدگي زماني:
پيچيدگی فضا:
جست و جوی آگاهانه و اکتشاف
جستجوی حريصانه

اسلاید 16 :

ويژگيهاي جستجوي حريصانه:
جستجوي حريصانه از لحاظ دنبال کردن يک مسير ويژه در تمام طول راه به طرف هدف، مانند جستجوي عمقي است و زماني که به بنبست ميرسد، برميگردد.
اين جستجو بهينه نيست و ناکامل است.
پيچيدگي زماني در بدترين حالت براي جستجوي حريصانه O(bm)، که m حداکثر عمق فضاي جستجو است.
جستجوي حريصانه تمام گرهها را در حافظه نگه ميدارد، بنابراين پيچيدگي فضاي آن مشابه پيچيدگي زماني آن است.
ميزان کاهش پيچيدگي به مسئله و کيفيت تابع h بستگي دارد.

اسلاید 17 :

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

اسلاید 18 :

جست و جوی آگاهانه و اکتشاف
جستجوی A* در نقشه رومانی
جستجوی Bucharest با شروع از Arad
f(Arad) = g(Arad)+h(Arad)=0+366=366

اسلاید 19 :

جست و جوی آگاهانه و اکتشاف
جستجوی A* در نقشه رومانی
ََArad را باز کرده و f(n) را برای هر يک از زيربرگها محاسبه ميکنيم:
f(Sibiu)=c(Arad,Sibiu)+h(Sibiu)=140+253=393
f(Timisoara)=c(Arad,Timisoara)+h(Timisoara)=118+329=447
f(Zerind)=c(Arad,Zerind)+h(Zerind)=75+374=449
بهترين انتخاب شهر Sibiu است

اسلاید 20 :

جست و جوی آگاهانه و اکتشاف
جستجوی A* در نقشه رومانی
ََSibiu را باز کرده و f(n) را برای هر يک از زيربرگها محاسبه ميکنيم:
f(Arad)=c(Sibiu,Arad)+h(Arad)=280+366=646
f(Fagaras)=c(Sibiu,Fagaras)+h(Fagaras)=239+179=415
f(Oradea)=c(Sibiu,Oradea)+h(Oradea)=291+380=671
f(Rimnicu Vilcea)=c(Sibiu,Rimnicu Vilcea)+ h(Rimnicu Vilcea)=220+192=413
بهترين انتخاب شهر Rimnicu Vilcea است