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

اسلاید 1 :

هوش مصنوعي
فصل سوم
حل مسئله با جستجو

اسلاید 2 :

هوش مصنوعي Artificial Intelligence
فهرست
عاملهای حل مسئله
مسئله
اندازه گيری کارايي حل مسئله
جستجوی ناآگاهانه
اجتناب از حالتهای تکراری
جستجو با اطلاعات ناقص
قسمت اول
قسمت دوم

اسلاید 3 :

حل مسئله با جستجو
منظور از جستجو: پيداكردن دنبالهاي از عمليات كه ما را از نقطه شروع به هدف برساند.
الگوريتم جستجو: مسئلهاي را به عنوان ورودي دريافت كرده و راهحلي را به صورت دنبالهاي از عمليات برميگرداند.
عاملهای حل مسئله: نوعي عامل هدفگرا هستند كه توسط الگوريتمهاي جستجو مسئلهاي را حل ميكنند.
براي سادگي فرض ميكنيم محيط گسسته، ايستا و قطعي است.

اسلاید 4 :

حل مسئله با جستجو
چهار گام اساسي برای حل مسائل
فرموله کردن هدف: وضعيتهای مطلوب نهايي کدامند؟
فرموله کردن مسئله: چه فعاليتها و وضعيتهايي برای رسيدن به هدف موجود است؟
جستجو: انتخاب بهترين دنباله از فعاليتها
اجرا: وقتی دنباله فعاليت مطلوب پيدا شد، فعاليتهای پيشنهادی آن ميتواند اجرا شود.

اسلاید 5 :

حل مسئله با جستجو
مثال: نقشه رومانی

اسلاید 6 :

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

اسلاید 7 :

پارامترهاي هر مسئله
حالت اوليه: حالتی که عامل از آن شروع ميکند.
در مثال رومانی: شهر آراد n(Arad)
تابع جانشين: به ما ميگويد براي يك حالت داده شده، چه فعاليتهايي ميتوانيم انجام دهيم و به چه حالتهايي ميرويم.
در مثال رومانی:Zerind,Sibui,Timisoara} S(Arad)={

اسلاید 8 :

پارامترهاي هر مسئله(ادامه)
فضای حالت: مجموعه ای از حالتها که از حالت اوليه ميتوان (با يك گام يا بيشتر) به آنها رسيد. فضاي حالت، گرافي است كه همه وضعيتهاي ممكن جهان و انتقال ميان آنها را نشان ميدهد.
در مثال رومانی: کليه شهرها که با شروع از آراد ميتوان به آنها رسيد
تابع جانشين + حالت اوليه = فضای حالت

آزمون هدف: تعيين ميکند که آيا حالت خاصی، حالت هدف است يا خير
هدف صريح: در مثال رومانی، رسيدن به بخارست
هدف انتزاعی: در مثال شطرنج، رسيدن به حالت کيش و مات

اسلاید 9 :

مسير: دنباله ای از حالتها که دنباله ای از فعاليتها را به هم متصل ميکند.
در مثال رومانی: Arad, Sibiu, Fagaras يک مسير است
هزينه مسير: برای هر مسير يک هزينه عددی در نظر ميگيرد.
در مثال رومانی: طول مسير بين شهرها بر حسب کيلومتر
راه حل مسئله مسيری از حالت اوليه به حالت هدف است
راه حل بهينه کمترين هزينه مسير را دارد
پارامترهاي هر مسئله(ادامه)

اسلاید 10 :

مثال: دنيای جارو برقي
حالتها: دو مکان که هر يک ممکن است کثيف يا تميز باشند.لذا 8 = 2^2* 2حالت در اين جهان وجود دارد
حالت اوليه: هر حالتی ميتواند به عنوان حالت اوليه طراحی شود
تابع جانشين: حالتهای معتبر از سه عمليات: راست، چپ، مکش
آزمون هدف: تميزی تمام مربعها
هزينه مسير: تعداد مراحل در مسير

اسلاید 11 :

حالتها: دو مکان که هر يک ممکن است کثيف يا تميز باشند.لذا 8 = 2^2* 2حالت در اين جهان وجود دارد
حالت اوليه: هر حالتی ميتواند به عنوان حالت اوليه طراحی شود
تابع جانشين: حالتهای معتبر از سه عمليات: راست، چپ، مکش
آزمون هدف: تميزی تمام مربعها
هزينه مسير: تعداد مراحل در مسير
مثال: دنيای جارو برقي

اسلاید 12 :

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

اسلاید 13 :

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

اسلاید 14 :

مثال: مسئله 8 وزير
فرمول بندی افزايشي
حالتها: هر ترتيبي از 0 تا 8 وزير در صفحه، يک حالت است
حالت اوليه: هيچ وزيری در صفحه نيست
تابع جانشين: وزيری را به خانه خالی اضافه ميکند
آزمون هدف: 8وزير در صفحه وجود دارند و هيچ کدام به يکديگر گارد نميگيرند
در اين فرمول بندی بايد 14^10*3 دنباله ممکن بررسی ميشود

اسلاید 15 :

مثال: مسئله 8 وزير
فرمول بندی افزايشي
حالتها: هر ترتيبي از 0 تا 8 وزير در صفحه، يک حالت است
حالت اوليه: هيچ وزيری در صفحه نيست
تابع جانشين: وزيری را به خانه خالی اضافه ميکند
آزمون هدف: 8وزير در صفحه وجود دارند و هيچ کدام به يکديگر گارد نميگيرند
در اين فرمول بندی بايد تقريباً 9^10*4 دنباله ممکن بررسی شود

اسلاید 16 :

مثال: مسئله 8 وزير
فرمول بندی حالت کامل
حالتها: چيدمان n وزير (0≤ n≤ 8) ، بطوريکه در هر ستون از n ستون سمت چپ، يک وزير قرار گيرد و هيچ دو وزيری بهم گارد نگيرند
حالت اوليه: با 8 وزير در صفحه شروع ميشود
تابع جانشين: وزيری را در سمت چپ ترين ستون خالي قرار ميدهد، بطوری که هيچ وزيری آن را گارد ندهد
آزمون هدف: 8وزير در صفحه وجود دارند و هيچ کدام به يکديگر گارد نميگيرند
اين فرمول بندی فضای حالت را از 14^10*3 به 2057 کاهش ميدهد

اسلاید 17 :

مثال: مسئله 8 وزير
فرمول بندی حالت کامل
حالتها: چيدمان n وزير (0≤ n≤ 8) ، بطوريکه در هر ستون از n ستون سمت چپ، يک وزير قرار گيرد و هيچ دو وزيری بهم گارد نگيرند
حالت اوليه: با 8 وزير در صفحه شروع ميشود
تابع جانشين: وزيری را در سمت چپ ترين ستون خالي قرار ميدهد، بطوری که هيچ وزيری آن را گارد ندهد
آزمون هدف: 8وزير در صفحه وجود دارند و هيچ کدام به يکديگر گارد نميگيرند
اين فرمول بندی فضای حالت را از 14^10*3 به 2057 کاهش ميدهد

اسلاید 18 :

معيارهاي کارايي حل مسئله
کامل بودن: آيا الگوريتم تضمين ميکند که در صورت وجود راه حل، آن را بيابد؟
بهينگي: آيا اين راهبرد، راه حل بهينه ای را ارائه ميکند.
پيچيدگي زمانی: چقدر طول ميکشد تا راه حل را پيدا کند؟
تعداد گره های توليد شده در اثنای جستجو
پيچيدگی فضا: برای جستجو چقدر حافظه نياز دارد؟
حداکثر تعداد گره های ذخيره شده در حافظه

در متن اصلی پاورپوینت به هم ریختگی وجود ندارد. برای مطالعه بیشتر پاورپوینت آن را خریداری کنید