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

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

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

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

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

اسلاید 4: 4حل مسئله با جستجوجستجوي بهترين:اين استراتژي به اين صورت بيان مي‌شود که در يک درخت، زماني که گره‌ها مرتب مي‌شوند، گره‌اي که بهترين ارزيابي را داشته باشد، قبل از ديگر گره‌ها بسط داده مي‌شود.هدف: يافتن راه‌حل‌هاي کم‌هزينه است، اين الگوريتم‌ها عموماً از تعدادي معيار تخمين براي هزينه راه‌حل‌ها استفاده مي‌‌کنند و سعي بر حداقل کردن آنها دارند.جست و جوی آگاهانه و اکتشاف

اسلاید 5: 5حداقل هزينه تخمين زده شده براي رسيدن به هدف: جستجوي حريصانهيکي از ساده‌ترين استراتژي‌هاي جستجوي بهترين، به حداقل رساندن هزينه تخمين زده شده براي رسيدن به هدف است. بدين صورت که حالت گره‌اي که به حالت هدف نزديک‌تر است، ابتدا بسط داده مي‌شود.تابع کشف‌کننده: هزينه رسيدن به هدف از يک حالت ويژه مي‌تواند تخمين زده شود اما دقيقاً تعيين نمي‌شود. تابعي که چنين هزينه‌هايي را محاسبه مي‌کند تابع کشف‌کننده h ناميده مي‌شود.جستجوي حريصانه: جستجوي بهترين که h را به منظور انتخاب گره بعدي براي بسط استفاده مي‌کند، جستجوي حريصانه (greedy search) ناميده مي‌شود.جست و جوی آگاهانه و اکتشاف

اسلاید 6: 6جست و جوی آگاهانه و اکتشافتعاريفتابع هزينه مسير، g(n) : هزينه مسير از گره اوليه تا گره nتابع اکتشافی، h(n) : هزينه تخمينی ارزان ترين مسير از گره n به گره هدفتابع بهترين مسير، h*(n) : ارزان ترين مسير از گره n تا گره هدفتابع ارزيابي، f(n) : هزينه تخمينی ارزان ترين مسير از طريق nf(n): g(n) + h(n)f*(n) : هزينه ارزان ترين مسير از طريقn f*(n): g(n) + h*(n)

اسلاید 7: 7جست و جوی آگاهانه و اکتشافABCDEFGHIKMLNO3PQJWVXYZRSTU1121332323231112321113231253013231221121021312332جستجوی حريصانه

اسلاید 8: 8جست و جوی آگاهانه و اکتشاف1ABCDEFGNO3X112111131253031322345جستجوی حريصانه

اسلاید 9: 9جست و جوی آگاهانه و اکتشافجستجوی حريصانهAFGHIMLNOPQWVXYZRSTU1332323111232111323BC2114DE1151KJ33013231221121021312333

اسلاید 10: 10جست و جوی آگاهانه و اکتشافجستجوی حريصانه2ABC2114DE1151KJ330113

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

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

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

اسلاید 14: 14جست و جوی آگاهانه و اکتشافرفتار جستجوي A*نگاهي گذرا به اثبات کامل و بهينه بودن A*:مشاهده مقدماتي:تقريباً تمام کشف‌کنندگي‌هاي مجاز داراي اين ويژگي هستند که در طول هر مسيري از ريشه، هزينه f هرگز کاهش پيدا نمي‌کند.اين خاصيت براي کشف‌کنندگي، خاصيت يکنوايي (monotonicity) گفته مي‌شود.اگر يکنوا نباشد، با ايجاد يک اصلاح جزئي آن را يکنوا مي‌کنيم.

اسلاید 15: 15جست و جوی آگاهانه و اکتشافجستجوی A*A/5B/4C/4D/5E/1F/3G/2H/2I/3K/0M/2L/3N/1O/32P/3Q/1J/1W/1V/2X/0Y/2Z/1R/2S/2T/1U/1111133332323111232111323

اسلاید 16: 16جست و جوی آگاهانه و اکتشافجستجوی A*132A/5B/4C/42165X/014N/1O/31384F/3G/21154

اسلاید 17: 17جست و جوی آگاهانه و اکتشافجستجوی A*A/5B/1C/4D/5E/1F/3G/2H/2I/3K/0M/2L/3N/1O/32P/3Q/1J/1W/1V/2X/0Y/2Z/1R/2S/2T/1U/1111133332323111232111323

اسلاید 18: 18جستجوی A*جست و جوی آگاهانه و اکتشافA/521345B/1C/42135D/5E/11184K/0J/13367X/014N/1O/31384F/3G/21154

اسلاید 19: 19جستجوی A*جست و جوی آگاهانه و اکتشافA/5B/1C/9D/5E/1F/3G/2H/2I/3K/0M/2L/3N/1O/32P/3Q/1J/1W/1V/2X/0Y/2Z/1R/2S/2T/1U/1111133332323111232111323

اسلاید 20: 20جستجوی A*جست و جوی آگاهانه و اکتشافA/5213B/1C/921310D/5E/11184K/0J/13361

اسلاید 21: 21جست و جوی آگاهانه و اکتشافh*(n) : هزينه واقعي رسيدن از n به هدف است.در استفاده عملي، خطاها با هزينه مسير متناسب هستند، و سرانجام رشد نمايي هر کامپيوتر را تسخير مي‌کند. البته، استفاده از يک کشف‌کنندگي خوب هنوز باعث صرفه‌جويي زيادي نسبت به جستجوي ناآگاهانه مي‌شود.A* معمولاً قبل از اينکه دچار کمبود زمان شود، دچار کمبود فضا مي‌شود. زيرا اين جستجو تمام گره‌هاي توليد شده را در حافظه ذخيره مي‌کند.

اسلاید 22: 22جستجوی A*جست و جوی آگاهانه و اکتشافکامل بودن: بلهبهينگی: بلهپيچيدگي زماني:اما اگر h = h* آنگاهپيچيدگی فضا:اما اگر h = h* آنگاه

اسلاید 23: 23جست و جوی آگاهانه و اکتشافABCDEFG1H1111111211001ABCDEFG1H1111113421001h ≤ h*h ≤ h*/جستجوی A*

اسلاید 24: 24جست و جوی آگاهانه و اکتشافجستجوی A*1234ABCDEFG1H1111111211001ABCDEFG1H1111113421001123456h ≤ h*h ≤ h*/

اسلاید 25: 25جست و جوی آگاهانه و اکتشافA/100B/80C/95E/86F/78G/90T/60H/80J/82N/72L/80K/85W/52X/58M/75Y/47Z/50O/78P/79D/90M/75I/87P/79O/78U/81V/83T/60R/20Q/0W/52X/58Y/47Z/50S/7010جستجوی A* و اجتناب از گره های تکراریهزينه هر مرحله 10 ميباشد

اسلاید 26: 26جست و جوی آگاهانه و اکتشافجستجوی A* و اجتناب از گره های تکراریA/100B/80C/95D/9090105100E/86F/7810698M/75I/8795107P/79O/78108109G/90T/6080110W/52X/58Y/47Z/5088829087R/20Q/07050N/72M/75105102T/60S/70100110W/52X/58102108Y/47Z/5010711012345678910

اسلاید 27: 27جست و جوی آگاهانه و اکتشافمثال ديگر از جستجوی A*f(n)=g(n) + h(n)

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

اسلاید 29: 29جست و جوی آگاهانه و اکتشافجستجوی 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 است

اسلاید 30: 30جست و جوی آگاهانه و اکتشافجستجوی 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 است

اسلاید 31: 31جست و جوی آگاهانه و اکتشافجستجوی 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 است

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

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

اسلاید 34: 34جست و جوی آگاهانه و اکتشافجستجوی A* در نقشه رومانی

اسلاید 35: 35جست و جوی آگاهانه و اکتشافتوابع اکتشافیمثال برای معمای8ميانگِين هزينه حل تقريبا 22 مرحله و فاکتور انشعاب در حدود 3 است.جست و جوی جامع تا عمق 22 : با انتخاب يک تابع اکتشافی مناسب ميتوان مراحل جستجو را کاهش داد

اسلاید 36: 36جست و جوی آگاهانه و اکتشافدو روش اکتشافي متداول برای معمای8تعداد کاشيها در مکانهای نادرستدر حالت شروع اکتشاف قابل قبولی است، زيرا هر کاشي که در جای نامناسبی قرار دارد، حداقل يکبار بايد جابجا شود

اسلاید 37: 37جست و جوی آگاهانه و اکتشافدو روش اکتشافي متداول برای معمای8مجموعه فواصل کاشيها از موقعيتهای هدف آنهادر حالت شروعچون کاشيها نميتوانند در امتداد قطر جا به جا شوند, فاصله ای که محاسبه ميکنيم مجموع فواصل افقی و عمودی است. اين فاصله را فاصله بلوک شهر يا فاصله مانهاتان مينامند.

اسلاید 38: 38جست و جوی آگاهانه و اکتشافدو روش اکتشافي متداول برای معمای8مجموعه فواصل کاشيها از موقعيتهای هدف آنها قابل قبول است، زيرا هر جابجايي که ميتواند انجام گيرد، به اندازه يک مرحله به هدف نزديک ميشود.هيچ کدام از اين برآوردها، هزينه واقعی راه حل نيستهزينه واقعي 36 است

اسلاید 39: 39جست و جوی آگاهانه و اکتشافالگوريتم های جست و جوی محلی و بهينه سازیالگوريتم های قبلی، فضای جست و جو را به طور سيستماتيک بررسی ميکنندتا رسيدن به هدف يک يا چند مسير نگهداری ميشوندمسير رسيدن به هدف، راه حل مسئله را تشکيل ميدهددر الگوريتم های محلی مسير رسيدن به هدف مهم نيستمثال: مسئله 8 وزيردو امتياز عمده جست و جوهای محلياستفاده از حافظه کمکیارائه راه حلهای منطقي در فضاهای بزرگ و نامتناهیاين الگوريتمها برای حل مسائل بهينه سازی نيز مفيدنديافتن بهترين حالت بر اساس تابع هدف

اسلاید 40: 40جست و جوی آگاهانه و اکتشافالگوريتم های جست و جوی محلی و بهينه سازی

اسلاید 41: 41جست و جوی تپه نوردیجست و جوی آگاهانه و اکتشافحلقه اي که در جهت افزايش مقدار حرکت ميکند(بطرف بالای تپه)رسيدن به بلندترين قله در همسايگی حالت فعلی، شرط خاتمه است.ساختمان داده گره فعلی، فقط حالت و مقدار تابع هدف را نگه ميداردجست و جوی محلی حريصانه نيز نام داردبدون فکر قبلي حالت همسايه خوبي را انتخاب ميکندتپه نوردی به دلايل زير ميتواند متوقف شود:بيشينه محليبرآمدگي هافلات

اسلاید 42: 42جست و جوی آگاهانه و اکتشافانواع تپه نوردی:تپه نوردی غيرقطعی، تپه نوردی اولين انتخاب، تپه نوردی شروع مجدد تصادفیمثال: مسئله 8 وزيرمسئله 8 وزير با استفاده از فرمولبندی حالت کاملدر هر حالت 8 وزير در صفحه قرار دارندتابع جانشين: انتقال يک وزير به مربع ديگر در همان ستونتابع اکتشاف: جفت وزيرهايي که نسبت به هم گارد دارندمستقيم يا غير مستقيمجست و جوی تپه نوردی

اسلاید 43: 43جست و جوی آگاهانه و اکتشافمثال جست و جوی تپه نوردیالف- حالت با هزينه h=17 که مقدار h را برای هر جانشين نشان ميدهدب- کمينه محلی در فضای حالت 8 وزير؛ h=1الفب

اسلاید 44: 44جست و جوی آگاهانه و اکتشافجست و جوی شبيه سازی حرارتتپه نوردی مرکب با حرکت تصادفیشبيه سازی حرارت: حرارت با درجه بالا و به تدريج سرد کردنمقايسه با حرکت توپتوپ در فرود از تپه به عميق ترين شکاف ميرودبا تکان دادن سطح توپ از بيشينه محلي خارج ميشودبا تکان شديد شروع(دمای زياد)بتدريج تکان کاهش(به دمای پايين تر)با کاهش زمانبندی دما به تدريج، الگوريتم يک بهينه عمومی را مي يابد

اسلاید 45: 45جست و جوی آگاهانه و اکتشافالگوريتم های ژنتيکشکلی از جست و جوی پرتو غير قطعی که حالتهای جانشين از طريق ترکيب دو حالت والد توليد ميشود

اسلاید 46: 46الگوريتم های ژنتيکجست و جوی آگاهانه و اکتشافجهت اوليهتابع برازشانتخابتقاطعجهش