بخشی از پاورپوینت
اسلاید 1 :
فصل سوم
حل مسئله با جستجو
اسلاید 2 :
فهرست
عاملهای حل مسئله
مسئله
اندازه گيری کارايي حل مسئله
جستجوی ناآگاهانه
اجتناب از حالتهای تکراری
جستجو با اطلاعات ناقص
اسلاید 3 :
چهار گام اساسي برای حل مسائل
فرموله کردن هدف: وضعيتهای مطلوب نهايي کدامند؟
فرموله کردن مسئله: چه فعاليتها و وضعيتهايي برای رسيدن به هدف موجود است؟
جستجو: انتخاب بهترين دنباله از فعاليتهايي که منجر به حالاتی با مقدار شناخته شده ميشود.
اجرا: وقتی دنباله فعاليت مطلوب پيدا شد، فعاليتهای پيشنهادی آن ميتواند اجرا شود.
اسلاید 4 :
مثال: نقشه رومانی
ایستا
رویت پذیر
گسسته
معین
اسلاید 5 :
مثال: نقشه رومانی
صورت مسأله: کل فرآیند تصمیم گیری در مورد اقدامات و حالتها بر اساس یک هدف خاص
رفتن از آراد به بخارست
هدف: مجموعه ای از حالتهای دنیا
رسيدن به بخارست
حالات: شهرهای مختلف (در چه شهری هستیم)
اقدامات: حرکت از یک شهر به شهر دیگر
جستجو: فرآیند یافتن دنباله ای از اقدامات که عامل را به هدف میرساند:
مثل:آراد، سيبيو، فاگارس، بخارست
اجرا: اجرای یک به یک اقدامات توصیه شده حاصل از جستجو
اسلاید 6 :
پنج مولفه اصلی یک مساله (ویرایش 3 کتاب)
حالت اوليه: حالتی که عامل از آن شروع ميکند.
In(Arad)
اقدامات ممکن: در هر حالت چه کاری میتوان انجام داد.
Actions(In(Arad)) = {Go(Sibiu), Go(Timisoara), Go(Zerind)}
مدل (تابع) گذر: از یک حالت با یک اقدام مشخص به چه حالتی میرویم
RESULT(In(Arad), Go(Zerind)) = In(Zerind)
فضای حالت= مدل گذر(تابع جانشين) + اقدامات ممکن + حالت اوليه
تست هدف: مشخص میکند آیا به هدف رسیده ایم یا خیر؟
{In(Bucharest)}
هدف صريح: در مثال رومانی، رسيدن به بخارست
هدف انتزاعی: در مثال شطرنج، رسيدن به حالت کيش و مات
اسلاید 7 :
پنج مولفه اصلی یک مساله
تابع هزینه: مشخص میکند یک راه حل خاص مساله چقدر خوب است (برحسب معیار کارآیی تعیین میشود)
طول یک مسیر از آراد به بخارست برحسب کیلومتر
راه حل مسئله مسيری از حالت اوليه به حالت هدف است
راه حل بهينه کمترين هزينه مسير را دارد
اسلاید 8 :
مساله دست گرمی: دنيای جارو برقي
حالتها: دو مکان که هر يک ممکن است کثيف يا تميز باشند.
لذا 8 = 2^2* 2حالت در اين جهان وجود دارد
حالت اوليه: هر حالتی ميتواند به عنوان حالت اوليه طراحی شود
مدل گذر: حالتهای معتبر از سه عمليات: راست، چپ، مکش
آزمون هدف: تميزی تمام مربعها
هزينه مسير: تعداد مراحل در
اسلاید 9 :
مساله دست گرمی : پازل 8 تایی
یک مساله NP-Complete
حالتها: مکان هر هشت خانه شماره دار و خانه خالی در يکي از 9 خانه (9!/2 حالت قابل حل)
1.3 تریلیون حالت برایس پازل 4×4، حل در چند میلی ثانیه توسط بهترین الگوریتمهای جستجو
1025 حالت در پازل 5×5 و غیرقابل حل با الگوریتمها و ماشینهای فعلی
حالت اوليه: هر حالتي را ميتوان به عنوان حالت اوليه در نظر گرفت
مدل گذر: حالتهای معتبر از چهار عمل، انتقال خانه خالی به چپ، راست، بالا يا پايين
آزمون هدف: بررسی ميکند که حالتی که اعداد به ترتيب چيده شده اند(طبق شکل روبرو) رخ داده يا نه
هزينه مسير: برابر با تعداد مراحل در مسير
اسلاید 10 :
مساله دست گرمی : مسئله 8 وزير
فرمول بندی حالت کامل
حالت اوليه: با 8 وزير در صفحه شروع ميشود
حالتها: هر ترتيبي از 0 تا 8 وزير در صفحه، يک حالت است.
مدل گذر: هر حرکت ممکن برای وزیران
آزمون هدف: 8 وزير در صفحه وجود دارند و هيچ کدام به يکديگر گارد نميگيرند
اسلاید 11 :
مساله دست گرمی : مسئله 8 وزير
اسلاید 12 :
مسایل دنیای واقعی
مسایل مسیریابی
زمانبندی سفر هوایی
سامانه های تجاری مشاور سفر (Touring Problem)
مساله فروشنده دوره گرد
هدف پیدا کردن کوتاه ترین گردش میباشد.
مساله چیدمان VLSI
اتصال میلیونها قطعه الکترونیکی با هدف کمینه کردن مساحت و تاخیر مدار و .
جهت یابی روبات:
حرکت در یک فضای پیوسته به منظور رسیدن به یک مقصد
درستی یابی سیستمهای نرم افزاری و سخت افزاری
هدف یافتن اشکالات و خطاهای موجود در یک برنامه یا یک مدار است.
برنامه ریزی روباتهای نرم افزاری
طراحی پروتئین
اسلاید 13 :
جستجوی راه حل
در فضای حالت به دنبال مسیری میگردیم که ما را از حالت اولیه به حالت مقصد برساند.
درخت جستجو
حالت ابتدایی به عنوان ریشه
اقدامات به عنوان اضلاع
و هر گره متناظر یک حالت از فضای حالت است.
بین فضای حالت و درخت جستجو تفاوت قائل شوید.
اسلاید 14 :
جستجوی درختی
مرز(frontier):
گره های برگ آماده بسط
گسترش حالت فعلی
ساخت تعدادی فرزند از حالت فعلی
راهبرد جستجو: کدام فرزند به عنوان گره بعدی انتخاب شود؟
حالتهای تکراری و مسیرهای حلقه ای
مسیرهای تکراری
در بعضی موارد میتوان طوری صورت مساله را تعریف کرد که مسیرهای تکراری حذف شوند یا کم شوند، مثل مساله 8 وزیر
اسلاید 15 :
الگوریتم جستجوی گراف
اما بعضی اوقات مسیرهای تکراری اجتناب ناپذیرند، به خصوص در مسایلی که دارای فعالیتهای برگشت پذیر هستند، مثل مسیریابی یا پازلهای لغزنده
دنبال کردن مسیرهای زاید میتواند باعث شود یک مساله قابل حل به یک مساله غیرقابل حل تبدیل شود
راه حل: تجهیز الگوریتم جستجوی درخت به لیست بسته (لیست گره های بازدید شده)
الگوریتم جستجوی گراف:
اسلاید 16 :
الگوریتم کلی جستجو در درخت یا گراف
ویرایش سوم
اسلاید 17 :
زیرساختهای الگوریتمهای جستجو
نمایش گره ها در فضای جستجو
حالت
با چه حالتی از فضای حالت متناظر است؟
دو گره متفاوت ممکن است حالت یکسانی داشته باشند.
گره والد
اقدام
با چه اقدامی از گره والد به گره فعلی رسیده ایم؟
هزینه مسیر (g(n))
با چه هزینه ای از حالت اولیه به این گره رسیده ایم.
صف گره های آماده بسط
میتواند دارای راهبرد FIFO، LIFO و یا صف اولویت باشد.
اسلاید 18 :
اندازه گيری کارايي حل مسئله
فاکتورهای کارآیی:
کامل بودن: آيا الگوريتم تضمين ميکند که در صورت وجود راه حل، آن را بيابد؟
بهينگي: آيا اين راهبرد، راه حل بهينه را پیدا ميکند؟
پيچيدگي زمانی: چقدر طول ميکشد تا راه حل را پيدا کند؟
(تعداد گره های توليد شده در اثنای جستجو)
پيچيدگی فضا: برای جستجو چقدر حافظه نياز دارد؟
(حداکثر تعداد گره های ذخيره شده در حافظه)
اسلاید 19 :
اندازه گيری کارايي حل مسئله
در علوم کامپیوتر کلاسیک پیچیدگی زمان و فضا بر حسب اندازه فضای حالت (تعداد گره ها و یالها) تعیین میشود، زیرا گراف به عنوان یک ساختمان داده صریح به الگوریتم جستجو داده میشود.
اما در هوش مصنوعی در بسیاری از اوقات فضای حالت نامتناهی است و به صورت ضمنی در قالب حالت اولیه، اقدامات و مدل گذر به الگوریتم داده میشود.
پس پیچیدگی الگوریتم بر حس موارد زیر سنجیده میشود:
b (ضریب انشعاب): حداکثر تعداد فرزندان در یک گره
d: عمق کم عمق ترین گره هدف
m: حداکثر طول مسیر در فضای حالت.
اسلاید 20 :
روشهای جستجوی ناآگاهانه
جستجوی ناآگاهانه: الگوريتم هيچ اطلاعاتی غير از تعريف مسئله در اختيار ندارد
اين الگوريتمها فقط ميتواند جانشينهايي را توليد و هدف را از غير هدف تشخيص دهند
جستجوی آگاهانه (اکتشافی یا آروینی): راهبردهايي که تشخيص ميدهد يک حالت غير هدف نسبت به گره غير هدف ديگر، اميد بخش تر است.
انواع روشهای جستجوی ناآگاهانه
جست و جوی سطح اول (عرضی)
جست و جوی عمق اول (عمقی)
جست و جوی عميق کننده تکراری
جست و جوی هزينه يکنواخت
جست و جوی عمقی محدود
جست و جوی دو طرفه
