آموزش گام به گام هوش مصنوعی

آموزش گام به گام هوش مصنوعی

اسلاید 1: آموزش گام به گام هوش مصنوعیتهیه کننده: محمود رضوی1

اسلاید 2: منابعکتاب هوش مصنوعی، رهیافتی نوین ویرایش سوم2

اسلاید 3: فصل اول: مفاهیم پایه3

اسلاید 4: مفاهیم پایهتعریف هوش مصنوعی چهار دیدگاه مختلف در تبیین هوش مصنوعیانسانی فکر کردن – علوم شناختیانسانی عمل کردن – ازمون تورینگعقلانی عمل کردن – منطقعقلانی عمل کردن – نگرش عامل گرایانهدسته بندی دیگرنماد گرایانهپیوند گرایانه4

اسلاید 5: تاریخچه هوش مصنوعیپیدایش در دهه 50 میلادیارزوهای بزرگ در دهه 60 میلادیزمستان اولیه هوش مصنوعیسیستم های خبره و تجاری شدن ان در دهه 70هوش مصنوعی پیوند گرایانه در دهه80زمستان دوم هوش مصنوعیعامل های هوشمند در دهه 90پیوند با وب در سالهای اخیر5

اسلاید 6: فصل سوم: روشهای جستجو6

اسلاید 7: فضای حالتانتزاعی کردن مسئله (Problem Abstraction)فرموله سازی مسئله و فرموله سازی هدفمثال از فضای حالت در مسائل طراحی الگوریتم مانند شاخه و حدگراف فضای حالتجستجو – راه حل7

اسلاید 8: توصیف گراف فضای حالتحالت اولیهاعمال (اگر قابل انجام باشند)مدل انتقال (تابع جانشین)تست هدفتابع هزینه مسیر – هزینه مرحله 8

اسلاید 9: مسئله معمای 89

اسلاید 10: توصیف فضای حالت معمای 8حالاتوضعیت اغازیناعمالمدل گذرازمون هدفهزینه مسیرکل حالت های مسئله 9!تعداد حالتهای قابل دسترس برابر است با 9!/210

اسلاید 11: مسئله 8 وزیرفرموله سازی تدریجی مسئلهعدم تهدید سطری و ستونیوضعیت آغازین صفحه خالیاعمال: افزودن وزیر به سطر جدیدتعداد حالتهای ممکن کمتر از 8!مدل گذر : حالت صفحه را بعد از افزودن وزیر جدید می دهدآزمون هدف: 8 وزیر بدون تهدید در صفحه باشند11

اسلاید 12: الگوریتمهای جستجو12

اسلاید 13: برخی واژه های کلیدیSearch Tree- Generation- ExpansionParent Node- Child Node- Leaf NodeFrontier = Open ListRepeated States- Loopy Paths- Redundant PathsExplored Sets= Closed Sets13

اسلاید 14: مسئله چهارخانه های مربع مستطیلی14

اسلاید 15: شمای کلی الگوریتم های جستجو15

اسلاید 16: ملاکهای کارایی روشهای جستجوکامل بودن بهینگیپیچیدگی زمانیپیچیدگی فضاییفاکتور انشعاب bعمق راه حل dبیشترین عمق گراف m16

اسلاید 17: دسته بندی کلیروشهای جستجوی اگاهانهروشهای جستجوی غیر اگاهانهتفاوت بین این روشها17

اسلاید 18: جستجوی غیر اگاهانه18

اسلاید 19: جستجوی سطح اول (Breadth-first search)19

اسلاید 20: BFS20

اسلاید 21: ملاکهای مقایسه BFSکامل بودن؟ بلهبهینگی؟ بلهپیچیدگی زمانی؟ = پیچیدگی فضایی؟1+b+b2+b3+…+bd=O(bd)چرا O(bd+1) نیست؟O(bd+1) گره در مجموعه مرور شده و O(bd) در مجموعه حاشیهنقطه ضعف مهم : فضای مصرفی نمایی21

اسلاید 22: جستجوی هزینه یکنواخت22

اسلاید 23: جستجوی عمق اول (Depth-first Search)23

اسلاید 24: DFSبا فرض حستجوی گرافی برای گرافهای متناهی کامل است.اما جستجوی درختی ان حتی برای گرافهای متناهی کامل نیست.هم جستجوی گرافی و هم درختی ان بهینه نیستند.پیچیدگی زمانی: O(bm)پیچیدگی فضایی: O(bm)با استفاده از پیجویی به عقب (Back Tracking) پیچیدگی فضایی به O(m) کاهش می یابد.24

اسلاید 25: جستجو با عمق محدوداین روش قادر است مشکل کامل نبودن DFS را با تعیین یک محدودیت حل کند.کامل است اگر عمق l>=d باشد (l= عمق محدود شده)این روش بهینه نیست.پیجیدگی زمانی: O(bl)پیچیدگی فضایی: O(bl)25

اسلاید 26: جستجو عمیق کننده تکراری26

اسلاید 27: ID-DFSکامل بودن ؟ بلهبهینگی؟ بلهپیچیدگی فضایی؟ D(bd)پیچیدگی زمانی؟ bd+(d-1)b2+…+1bd=O(bd)بهترین روش از بین روشهای غیراگاهانه27

اسلاید 28: جستجوی دوطرفه28

اسلاید 29: مقایسه روشها29

اسلاید 30: جستجوی اگاهانه30

اسلاید 31: مفاهیم پایهتفاوت روشهای اگاهانه و غیر اگاهانهتابع ارزیابی Evaluation Function: f(n) تعیین میکند که کدام گره باید بست داده شودتابع ابتکاری Heuristic Function: h(n) تابع ابتکاری تخمینی از هزینه مسیر بهینه از وضعیت جاری تا نزدیکترین هدف است.توابع دیگرg(n) : هزینه مسیر از نقطه شروع تا به گره ng*(n): کوتاه ترین فاصله ممکن از مبدا تا گره جاری nh*(n): کوتاه ترین فاصله از گره جاری n به نزدیکترین هدفf*(n)=g*(n)+ h*(n): کوتاهترین مسیر از مبدا تا مقصد که از گره n عبور میکند اگر n روی مسیر بهینه باشد برابر با مسیر بهینه یا C* خواهد بود31

اسلاید 32: جستجوی اول بهترین حریصانهتابع ارزیابی f(n)=h(n) یعنی تابع اکتشاف = تخمین هزینه از گره n به هدفگره ای توسعه می یابد که به نظر می رسد به هدف نزدیکتر است.کامل است؟ خیر – ممکن است در حلقه بیافتد.بهینه است؟ خیرپیچیدگی زمانی؟ O(bm) اما با بکاربردن تابع اکتشاف خوب می تواند بسیار بهبود یابد.پیچیدگی فضایی؟ O(bm) همه گره ها را در حافظه نگهداری می کند.32

اسلاید 33: مثال33

اسلاید 34: الگوریتم جستجوی A*تابع ارزیابی f(n)=g(n)+h(h)تابع اکتشاف h(n) قابل قبول (admissible) است اگر برای هر گره n، h(n)<=h*(n) باشد که در ان h*(n) هزینه واقعی برای رسیدن به هدف از گره n است.یک اکتشاف قابل قبول هرگز هزینه تخمینی را بیشتر از هزینه واقعی براورد نمی کند.34

اسلاید 35: 35مثال از جستجوی A*f(n)=g(n) + h(n)

اسلاید 36: 36جستجوی A* در نقشه رومانیجستجوی Bucharest با شروع از Aradf(Arad) = g(Arad)+h(Arad)=0+366=366

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

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

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

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

اسلاید 41: 41جستجوی A* در نقشه رومانیََ Pitesti را باز کرده و f(n) را برای هر يک از زيربرگها محاسبه ميکنيم:f(Bucharest)=c(Pitesti,Bucharest)+h(Bucharest)=418+0=418بهترين انتخاب شهر Bucharest !!! است

اسلاید 42: قضیه امکان پذیریقضیه: اگر h(n) قابل قبول باشد، A* با استفاده از جستجوی درختی بهینه است.قضیه: اگر A* پایدار باشد A* با استفاده از جستجوی گرافی بهینه است.لم: در هر مرحله قبل از اتمام الگوریتم A*، همواره گره ای مانند n’ در لیست حاشیه با خواص سه گانه زیر قرار دارد:n‘ روی مسیر بهینه تا هدف قرار دارد.A* مسیر بهینه تا n’ را یافته است.f(n’) <= C*42

اسلاید 43: اثبات بهینگی الگوریتم A*فرض کنید که یک هدف غیربهینه مانند G2 تولید شده و در حاشیه باشد. و n یک گره توسعه داده نشده در حاشیه باشد بطوری که n روی کوتاهترین مسیر به سمت هدف بهینه G باشد.از انجایی که h(G2)=0 پس f(G2)=g(G2)از انجایی که G2 غیربهینه است پس g(G2)>g(G)از انجایی که h(G)=0 پس f(G)=g(G)پس نتیجه می شود f(G2)>f(G)43

اسلاید 44: اثبات بهینگی الگوریتم A*پس f(G2) > f(G)از انجایی که h قابل قبول است پس h(n) <=h*(n)، g(n)+h(n) <=g(n)+h*(n)پس f(n) <=f(G)پس f(G2)>f(n) است و A* هرگز G2 را برای توسعه انتخاب نخواهد کرد44

اسلاید 45: بهینگی الگوریتم A*A* گره ها را به ترتیب افزایش مقدار f توسعه می دهد.به کانتور-f گره ها به تدریج افزوده می شود.کانتور iام شامل گره هایی با f=fi است که fi<fi+145

اسلاید 46: 46