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