بخشی از پاورپوینت
اسلاید 1 :
هوش مصنوعی
ادامه فصل سوم و فصل چهارم: جست و جوي آگاهانه و اکتشاف
INFORMED (HEURISTIC) SEARCH STRATEGIES
اسلاید 2 :
جست و جوي آگاهانه و اکتشاف
متدهاي جستجوي آگاهانه
بهترين جستجو
حريصانه
A*
IDA*
RBFS
MA* و SMA*
جستجوي محلي و بهينه سازي
تپه نوردي
شبيه سازي حرارت
پرتو محلي
الگوريتمهاي ژنتيک
اسلاید 3 :
جستجوي بهترين: (best-first search)
اين استراتژي به اين صورت بيان ميشود که در يک درخت، زماني که گرهها مرتب ميشوند، گرهی که بهترين ارزيابي را داشته باشد، قبل از ديگر گرهها بسط داده ميشود.
هدف: يافتن راهحلهاي کمهزينه است، اين الگوريتمها عموماً از تعدادي معيار تخمين براي هزينه راهحلها استفاده ميکنند و سعي بر حداقل کردن آنها دارند.
اسلاید 4 :
حداقل هزينه تخمين زده شده براي رسيدن به هدف: جستجوي حريصانه
يکي از سادهترين استراتژيهاي جستجوي بهترين، به حداقل رساندن هزينه تخمين زده شده براي رسيدن به هدف است. بدين صورت که حالت گرهاي که به حالت هدف نزديکتر است، ابتدا بسط داده ميشود.
تابع هیوریستیک: هزينه رسيدن به هدف از يک حالت ويژه ميتواند تخمين زده شود اما دقيقاً تعيين نميشود. تابعي که چنين هزينههايي را محاسبه ميکند تابع هیوریستیک h ناميده ميشود.
جستجوي حريصانه: جستجوي بهترين که h را به منظور انتخاب گره بعدي براي بسط استفاده ميکند، جستجوي حريصانه (greedy search) ناميده ميشود.
اسلاید 5 :
ويژگيهاي جستجوي حريصانه:
جستجوي حريصانه از لحاظ دنبال کردن يک مسير ويژه در تمام طول راه به طرف هدف، مانند جستجوي عمقي است، اما زماني که به بنبست ميرسد، برميگردد.
اين جستجو بهينه نيست و ناکامل است.
پيچيدگي زماني در بدترين حالت براي جستجوي حريصانه O(bm)، که m حداکثر عمق فضاي جستجو وb فاکتور شاخه شاخه شدن درخت است.
جستجوي حريصانه تمام گرهها را در حافظه نگه ميدارد، بنابراين پيچيدگي فضاي آن مشابه پيچيدگي زماني آن است.
ميزان کاهش پيچيدگي به مسئله و کيفيت تابع h بستگي دارد.
اسلاید 6 :
جست و جوي آگاهانه و اکتشاف
تعاريف
تابع هزينه مسير، g(n) : هزينه مسير از گره اوليه تا گره n
تابع اکتشافي، h(n) : هزينه تخميني کم هزینه ترين مسير از گره n به گره هدف
تابع بهترين مسير، h*(n) : هزینه کم هزینه ترين مسير از گره n تا گره هدف (واقعی)
تابع ارزيابي، f(n) : هزينه تخميني کم هزینه ترين مسير از طريق n از مبدا تا هدف
f(n): g(n) + h(n)
f*(n) : هزينه کم هزینه ترين مسير از طريقn (واقعی) از مبدا تا هدف
` f*(n): g(n) + h*(n)
اسلاید 7 :
جست و جوي آگاهانه و اکتشاف
جستجوي حريصانه
اسلاید 11 :
کامل بودن: خير
اما اگر h = h* آنگاه جستجو کامل ميشود
: خير
اما اگر h = h* آنگاه جستجو بهینه ميشود
پيچيدگي زماني:
اما اگر h = h* آنگاه
پيچيدگي فضا:
اما اگر h = h* آنگاه
بهينگي
اسلاید 12 :
حداقلسازي مجموع هزينه مسير: جستجوي A*
جستجو با هزينه يکسان، هزينه مسير، g(n) را نيز حداقل ميکند.
با ترکيب دو تابع ارزيابي داريم:
f(n) = g(n) + h(n)
:g(n) هزينه مسير از گره آغازين به گره n را به ما ميدهد.
h(n): هزينه تخمين زده شده از ارزانترين مسير از n به هدف است
و ما داريم:
هزينه تخمين زده شده ارزانترين راه حل از طريق n = f(n)
اسلاید 13 :
جست و جوي آگاهانه و اکتشاف
جستجوي A*
A/5
B/4
C/4
D/5
E/1
F/3
G/2
H/2
I/3
K/0
M/2
L/3
N/1
O/3
P/3
Q/1
J/1
W/1
V/2
X/0
Y/2
Z/1
R/2
S/2
T/1
U/1
اسلاید 14 :
جستجوي A*
A/5
اسلاید 15 :
جستجوي A*
A/5
B/1
C/4
D/5
E/1
F/3
G/2
H/2
I/3
K/0
M/2
L/3
N/1
O/3
P/3
Q/1
J/1
W/1
V/2
X/0
Y/2
Z/1
R/2
S/2
T/1
U/1
اسلاید 16 :
جستجوي A*
A/5
B/1
C/9
D/5
E/1
F/3
G/2
H/2
I/3
K/0
M/2
L/3
N/1
O/3
P/3
Q/1
J/1
W/1
V/2
X/0
Y/2
Z/1
R/2
S/2
T/1
U/1
اسلاید 17 :
جستجوي A*
A/5
اسلاید 18 :
جستجوي A*
کامل بودن: بله
بهينگي: بله
پيچيدگي زماني:
اما اگر h = h* آنگاه
پيچيدگي فضا:
اما اگر h = h* آنگاه
اسلاید 19 :
Optimality of A* (proof)
Suppose some suboptimal goal G2 has been generated and is in the fringe. Let n be an unexpanded node in the fringe such that n is on a shortest path to an optimal goal G.
f(G2) = g(G2)since h(G2) = 0
g(G2) > g(G) since G2 is suboptimal
f(G) = g(G)since h(G) = 0
f(G2) > f(G)from above
AI, Informed search strategies
اسلاید 20 :
Optimality of A* (proof)
Suppose some suboptimal goal G2 has been generated and is in the fringe. Let n be an unexpanded node in the fringe such that n is on a shortest path to an optimal goal G.
f(G2)> f(G) from above
h(n)≤ h*(n)since h is admissible
g(n) + h(n)≤ g(n) + h*(n)
f(n) ≤ f(G)
Hence f(G2) > f(n), and A* will never select G2 for expansion
AI, Informed search strategies
