بخشی از پاورپوینت
اسلاید 1 :
هوش مصنوعي
فصل سوم: حل مسئله با جستجو
اسلاید 2 :
هوش مصنوعي Artificial Intelligence
فهرست
عاملهاي حل مسئله
مسئله
اندازه گيري کارايي حل مسئله
جستجوي ناآگاهانه
اجتناب از حالتهاي تکراري
جستجو با اطلاعات ناقص
HA-AI, IUST-CE Dep.
اسلاید 3 :
عاملهاي حل مسئله
چهار گام اساسي براي حل مسائل
فرمولهکردن هدف: وضعيتهاي مطلوب نهايي کدامند؟
فرمولهکردن مسئله: فراين تصميمگيري در مورد اقدامات و حالتها براي رسيدن به هدف
جستجو: انتخاب بهترين دنباله از اقدامات که منجر به رسيدن به هدف شود
اجرا: اجراي گام به گام اقدامات
HA-AI, IUST-CE Dep.
اسلاید 4 :
مثال: نقشه روماني
HA-AI, IUST-CE Dep.
اسلاید 5 :
صورت مسأله: رفتن از آراد به بخارست
فرمولهکردن هدف: رسيدن به بخارست
فرمولهکردن مسئله:
وضعيتها: شهرهاي مختلف
اقدامات: حرکت بين شهرها
جستجو: دنبالهاي از شهرها مثل:آراد، سيبيو، فاگارس، بخارست
اين جستجو با توجه به کمهزينهترين مسير انتخاب ميشود
مثال: نقشه روماني
HA-AI, IUST-CE Dep.
اسلاید 6 :
فرمولهکردن مسئله
حالت اوليه: حالتي که عامل از آن شروع ميکند.
در مثال روماني: شهر آراد n(Arad)
تابع جانشين: توصيفي از فعاليتهاي ممکن که براي عامل مهيا است.
در مثال روماني:Zerind,Sibui,Timisoara} S(Arad)={
فضاي حالت: مجموعه اي از حالتها که از حالت اوليه ميتوان به آنها رسيد.
در مثال روماني: کليه شهرها که با شروع از آراد ميتوان به آنها رسيد
تابع جانشين + حالت اوليه = فضاي حالت
HA-AI, IUST-CE Dep.
اسلاید 7 :
آزمون هدف: تعيين ميکند که آيا يک حالت خاص، حالت هدف است يا خير
هدف صريح: در مثال روماني، رسيدن به بخارست
هدف انتزاعي: در مثال شطرنج، رسيدن به حالت کيش و مات
هزينه مسير: براي هر مسير يک هزينه عددي در نظر ميگيرد.
در مثال روماني: طول مسير بين شهرها بر حسب کيلومتر
راهحل يک مسير از حالت اوليه به حالت هدف
راهحل بهينه راهحلي که کمترين هزينه مسير را دارد
HA-AI, IUST-CE Dep.
اسلاید 8 :
مثال: فرمولهکردن مسئله جارو برقي
حالتها: دو مکان که هر يک ممکن است کثيف يا تميز باشند.لذا 8 = 2^2* 2حالت در اين جهان وجود دارد
حالت اوليه: هر حالتي ميتواند به عنوان حالت اوليه طراحي شود
تابع جانشين: حالتهاي معتبر از سه عمليات: راست، چپ، مکش
آزمون هدف: تميزي تمام مربعها
هزينه مسير: تعداد مراحل در مسير
HA-AI, IUST-CE Dep.
اسلاید 9 :
مثال: دنياي جارو برقي
حالتها: دو مکان که هر يک ممکن است کثيف يا تميز باشند. جارو برقي نيز در هر مکان ممکن است باشد. لذا 8 = 2*2*2 حالت در اين جهان وجود دارد
حالت اوليه: هر حالتي ميتواند به عنوان حالت اوليه طراحي شود
تابع جانشين: حالتهاي معتبر از سه عمليات: راست، چپ، مکش
آزمون هدف: تميزي تمام مربعها
هزينه مسير: تعداد گامها در مسير
HA-AI, IUST-CE Dep.
اسلاید 10 :
مثال: معماي8
حالتها: مکان هر هشت خانه شماره دار و خانه خالي در يکي از 9 خانه
حالت اوليه: هر حالتي را ميتوان به عنوان حالت اوليه در نظر گرفت
تابع جانشين: حالتهاي معتبر از چهار عمل، انتقال خانه خالي به چپ، راست، بالا يا پايين
آزمون هدف: بررسي ميکند که حالتي که اعداد به ترتيب چيده شدهاند(طبق شکل روبرو) رخ داده يا نه
هزينه مسير: برابر با تعداد مراحل در مسير
HA-AI, IUST-CE Dep.
اسلاید 11 :
مثال: معماي8تايي
حالتها: مکان هر هشت خانه شمارهدار و خانه خالي در يکي از 9 خانه
حالت اوليه: هر حالتي را ميتوان به عنوان حالت اوليه در نظر گرفت
تابع جانشين: حالتهاي معتبر از چهار عمل، انتقال خانه خالي به چپ، راست، بالا يا پايين
آزمون هدف: بررسي ميکند که حالتي که اعداد به ترتيب چيده شدهاند حالت هدف است يا نه
هزينه مسير: برابر با تعداد مراحل در مسير
HA-AI, IUST-CE Dep.
اسلاید 12 :
مثال: مسئله 8 وزير
فرمولبندي افزايشي
حالتها: هر ترتيبي از 0 تا 8 وزير در صفحه، يک حالت است
حالت اوليه: هيچ وزيري در صفحه نيست
تابع جانشين: وزيري را به خانه خالي اضافه ميکند
آزمون هدف: 8وزير در صفحه وجود دارند و هيچ کدام به يکديگر گارد نميگيرند
در اين فرمولبندي بايد 14^10*3 دنباله ممکن بررسي ميشود
HA-AI, IUST-CE Dep.
اسلاید 13 :
مثال: مسئله 8 وزير
فرمولبندي افزايشي
حالتها: هر ترتيبي از 0 تا 8 وزير در صفحه، يک حالت است
حالت اوليه: هيچ وزيري در صفحه نيست
تابع جانشين: وزيري را به خانه خالي اضافه ميکند
آزمون هدف: 8وزير در صفحه وجود دارند و هيچ کدام به يکديگر گارد نميگيرند
در اين فرمولبندي بايد 14^10*3=64!/56! دنباله ممکن بررسي ميشود
HA-AI, IUST-CE Dep.
اسلاید 14 :
مثال: مسئله 8 وزير
فرمولبندي حالت کامل
حالتها: چيدمان n وزير (0≤ n≤ 8) ، بطوريکه در هر ستون از n ستون سمت چپ، يک وزير قرار گيرد و هيچ دو وزيري به هم گارد نگيرند
حالت اوليه: با 8 وزير در صفحه شروع ميشود
تابع جانشين: وزيري را در سمت چپ ترين ستون خالي قرار ميدهد، بطوري که هيچ وزيري آن را گارد ندهد
آزمون هدف: 8وزير در صفحه وجود دارند و هيچ کدام به يکديگر گارد نميگيرند
اين فرمولبندي فضاي حالت را از 14^10*3 به 2057 کاهش ميدهد
HA-AI, IUST-CE Dep.
اسلاید 15 :
مثال: مسئله 8 وزير
فرمولبندي حالت کامل
حالتها: چيدمان n وزير (0≤ n≤ 8) ، بطوريکه در هر ستون از n ستون سمت چپ، يک وزير قرار گيرد و هيچ دو وزيري به هم گارد نگيرند
حالت اوليه: با 8 وزير در صفحه شروع ميشود
تابع جانشين: وزيري را در سمت چپ ترين ستون خالي قرار ميدهد، بطوري که هيچ وزيري آن را گارد ندهد
آزمون هدف: 8وزير در صفحه وجود دارند و هيچ کدام به يکديگر گارد نميگيرند
اين فرمولبندي فضاي حالت را از 14^10*3 به 2057 کاهش ميدهد
HA-AI, IUST-CE Dep.
اسلاید 16 :
اندازه گيري کارايي حل مسئله
کاملبودن: آيا الگوريتم تضمين ميکند که در صورت وجود راهحل، آن را بيابد؟
بهينگي: آيا اين راهبرد، راهحل بهينه اي را ارائه ميکند.
پيچيدگي زماني: چقدر طول ميکشد تا راهحل را پيدا کند؟
تعداد گرههاي توليد شده در اثناي جستجو
پيچيدگي فضا: براي جستجو چقدر حافظه نياز دارد؟
حداکثر تعداد گرههاي ذخيره شده در حافظه
HA-AI, IUST-CE Dep.
اسلاید 17 :
اندازه گيري کارايي حل مسئله
کاملبودن: آيا الگوريتم تضمين ميکند که در صورت وجود راهحل، آن را بيابد؟
بهينگي: آيا اين راهبرد، تضمين ميکند که راهحل بهينه اي را ارائه کند؟
پيچيدگي زماني: چقدر طول ميکشد تا راهحل را پيدا کند؟
تعداد گرههاي توليد شده در اثناي جستجو
پيچيدگي فضايي: براي جستجو چقدر حافظه نياز دارد؟
حداکثر فضاي لازم در حافظه براي اجراي الگوريتم جستجو
HA-AI, IUST-CE Dep.
اسلاید 18 :
جستجوي ناآگاهانه
ناآگاهي اين است که الگوريتم هيچ اطلاعاتي غير از تعريف مسئله در اختيار ندارد
اين الگوريتمها فقط ميتوانند جانشينهايي را توليد و هدف را از غير هدف تشخيص دهند
راهبردهايي که تشخيص ميدهد يک حالت غير هدف نسبت به گره غير هدف ديگر، اميدبخشتر است، جستجوي آگاهانه يا جستجوي اکتشافي ناميده ميشود.
راهبردها
جستجوي عرضي
جستجوي عمقي
جستجوي عميقکننده تکراري
جستجوي هزينه يکنواخت
جستجوي عمقي محدود
جستجوي دو طرفه
HA-AI, IUST-CE Dep.
اسلاید 19 :
جستجوي عرضي
HA-AI, IUST-CE Dep.
اسلاید 20 :
جستجوي عرضي
کاملبودن: بله
بهينگي: بله (مشروط)
در صورتي بهينه است که هزينه مسير، تابعي غير نزولي از عمق گره باشد.(مثل وقتي که فعاليتها هزينه يکساني دارند)
پيچيدگي زماني:
پيچيدگي فضا:
کاملبودن:
بهينگي: بله (مشروط)
HA-AI, IUST-CE Dep.
