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

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

اسلاید 1 :

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

اسلاید 2 :

مثال ديگر از جستجوي A*
f(n)=g(n) + h(n)

اسلاید 3 :

مثال ديگر از جستجوي A*- انتخاب تابع اکتشافي
h(n)

اسلاید 4 :

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

اسلاید 5 :

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

اسلاید 6 :

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

اسلاید 7 :

جستجوي A* در نقشه روماني
ََRimnicu Vilcea را باز کرده و f(n) را براي هر يک از زيربرگها محاسبه ميکنيم:
f(Craiova)=g(Arad, Sibiu,Rimnicu Vilcea, Craiova)+h(Craiova)=360+160=526
f(Pitesti)=g(Arad, Sibiu,Rimnicu Vilcea, Pitesti)+h(Pitesti)=317+100=417
f(Sibiu)=g(Arad, Sibiu,Rimnicu Vilcea,Sibiu)+h(Sibiu)=300+253=553
بهترين انتخاب شهر Fagaras است

اسلاید 8 :

جستجوي A* در نقشه روماني
ََ Fagaras را باز کرده و f(n) را براي هر يک از زيربرگها محاسبه ميکنيم:
f(Sibiu)=g(Arad, Sibiu,Fagaras, Sibiu)+h(Sibiu)=338+253=591
f(Bucharest)=g(Arad, Sibiu,Fagaras,Bucharest)+h(Bucharest)=450+0=450
بهترين انتخاب شهر Pitesti !!! است

اسلاید 9 :

جستجوي A* در نقشه روماني
ََ Pitesti را باز کرده و f(n) را براي هر يک از زيربرگها محاسبه ميکنيم:
f(Bucharest)=g(Arad, Sibiu, Rimnicu Vilcea, Pitesti,Bucharest)+h(Bucharest)=418+0=418

بهترين انتخاب شهر Bucharest !!! است

اسلاید 15 :

جستجوي گراف با A*
A/6
B/5
C/1
D/1
E/2
F/2
G/1
J/1

اسلاید 18 :

جستجوي A* در در برخي مسائل مشکل مناسب نيست و معمولا با کمبود حافظه مواجه مي شود.

دو الگوريتم براي بهبود A* در مصرف حافظه:
(1) جستجوي عميق کننده تکراي A* (IDA*)
ايده: تعميم جستجوي عميق کننده تکراري( که مصرف حافظه آن به صورت خطي مي باشد) با استفاده از هيوريستيک ها

(2) جستجوي ساده شده با حافظه محدود (SMA*)
ايده: حذف يك گرهي موجود در حافظه، در صورتي كه حافظه پر شود.
جستجو با حافظه محدود

اسلاید 19 :

جستجوي اکتشافي با حافظه محدود IDA*
ساده ترين راه براي کاهش حافظه مورد نياز A* استفاده از عميق کننده تکرار در زمينه جست و جوي اکتشافي است.
الگوريتم عميق کننده تکرار A* IDA*
در جستجوي IDA* مقدار برش مورد استفاده، عمق نيست بلکه هزينه f(g+h) است.
در IDA* پيچيدگي فضا کمتر مي شود.

اسلاید 20 :

جستجوي IDA*
براي کاهش ميزان درخواست حافظه با هزينه افزايش زمان محاسبات، جستجوي عميق کننده تکراري ناآگاهانه با A* ترکيب مي شود.

در اين اگوريتم، هر تکرار يک جستجوي عمقي مي باشد ولي به جاي محدوده عمقي از محدوده f-cost استفاده مي شود.

در هر تکرار تمام گره ها با f(n) ≤ f-cost گسترش مي يابند و در صورتي که گره هدف در اين کانتور وجود نداشت، محدوده جستجو يعني f-cost افزايش يافته و کانتور بزرگتري رسم مي شود و .