Y@SiN
01-25-2010, 02:00 PM
انواع روش های جستجودر حالت کلی روش های جستجو را می توان به سه دسته زیر تقسیم کرد
• ناآگاهانه
• هیوریستیکی
• متاهیوریستیکی
مسائلی وجود دارند که فضای جستجوی آنها به اندازه ای بزرگ می باشد که استفاده از روش های جستجوی ناآگاهانه و هیوریستیکی را برایمان غیرممکن می سازند. در چنین مواردی از روش های متاهیوریستیکی یا فرامکاشفه ای استفاده خواهیم کرد.
در ادامه این بخش ابتدا به بررسی انواع مسائل هوش مصنوعی خواهیم پرداخت، سپس روش های جستجوی ناآگاهانه را بررسی کرده و به دنبال آن با روش های جستجوی هیوریستیکی آشنا خواهیم شد.
http://pnu-club.com/imported/mising.jpg
مسائل مطرح شده در هوش مصنوعی را از چند دیدگاه مختلف می توان مورد بررسی قرار دارد :
• هدف یافتن تنها یک جواب برای مسئله است یا همه جواب های ممکن برای مسئله باید جستجو شوند؟
• پاسخ دهی الگوریتم جستجو برای حل مسئله بلادرنگ خواهد بود یا زمان بیشتری برای حل مساله می توان اختیار کرد
• آیا در مسئله محدودیت هایی وجود دارد یا نه ؟
همه اینها سوالاتی هستند که هنگام طراحی الگوریتمی برای پویش در فضای جستجو باید به آنها توجه کنیم. به عنوان مثال در صورتی که همه جواب های مسئله مدنظر ما باشد، در اینصورت حتی در صورت آگاهانه بودن ماهیت مسئله نیز نمی توان از روش های هیوریستیکی استفاده کرد. به عنوان مثال در صورتی که هدف یافتن همه مسیرهای ممکن از تبریز به شیراز باشد، استفاده از هیوریستیک تنها موجب پیچیده شدن الگوریتم و حتی موجب ناقص بودن جواب های مسئله خواهد شد.
سیستم های پویا سیستم هایی هستند که در آنها به طور مداوم ورودی ها و حالت مسئله در حال تغییر است و هربار تغییر در یکی از پارامترها موجب خواهد شد که عمل جستجوی مجددی در فضای جستجو انجام پذیرد. در چنین مواردی ممکن است مدت زمان پاسخ دهی سیستم برای حل مساله بسیار کم باشد. همچنین ممکن است سیستم مدت زمان کافی برای حل مساله در اختیار داشته باشد که هریک از این موارد تاثیر بسزایی در طراحی الگوریتم جستجو خواهند داشت.
فرض کنید می خواهیم در یک صفحه شطرنج استاندارد، 8 وزیر را به گونه بر روی صفحه شطرن قرار دهیم که هیچیک از آنها وزیر دیگری را گارد ندهند. در این مسئله که به مسئله 8 وزیر معروف است، محدودیتی وجود دارد که بر اساس آن هیچ وزیری باید همدیگر را گارد ندهند. به صورت تجربی می توان چنین گفت که بیشتر مسائلی که با آنها سروکار داریم دارای محدویت هایی در مسئله هستند. به چنین مسائلی مسائل ارضای محدودیت نیز می گوییم. وجود محدودیت در مسئله قدری موجب پیچیدگی مسئله می شود اما در اکثر موارد نیز موجب خواهد شد فضای جستجو مسئله بسیار کوچکتر از حالتی باشد که در آن مسئله هیچ محدودیتی در خود ندارد.
مسائلی که در عمل با آنها مواجه هستیم ترکیبی از موارد فوق را در خود دارند. به عنوان مثال در مسئله ی 8 وزیر ، مسئله دارای محدودیت بوده ولی در مقابل هدف یافتن تنها یک جواب در مدت زمان معقول است و در واقع یافتن جواب در آن نیازی به بلادرنگ بودن ندارد.
• ناآگاهانه
• هیوریستیکی
• متاهیوریستیکی
مسائلی وجود دارند که فضای جستجوی آنها به اندازه ای بزرگ می باشد که استفاده از روش های جستجوی ناآگاهانه و هیوریستیکی را برایمان غیرممکن می سازند. در چنین مواردی از روش های متاهیوریستیکی یا فرامکاشفه ای استفاده خواهیم کرد.
در ادامه این بخش ابتدا به بررسی انواع مسائل هوش مصنوعی خواهیم پرداخت، سپس روش های جستجوی ناآگاهانه را بررسی کرده و به دنبال آن با روش های جستجوی هیوریستیکی آشنا خواهیم شد.
http://pnu-club.com/imported/mising.jpg
مسائل مطرح شده در هوش مصنوعی را از چند دیدگاه مختلف می توان مورد بررسی قرار دارد :
• هدف یافتن تنها یک جواب برای مسئله است یا همه جواب های ممکن برای مسئله باید جستجو شوند؟
• پاسخ دهی الگوریتم جستجو برای حل مسئله بلادرنگ خواهد بود یا زمان بیشتری برای حل مساله می توان اختیار کرد
• آیا در مسئله محدودیت هایی وجود دارد یا نه ؟
همه اینها سوالاتی هستند که هنگام طراحی الگوریتمی برای پویش در فضای جستجو باید به آنها توجه کنیم. به عنوان مثال در صورتی که همه جواب های مسئله مدنظر ما باشد، در اینصورت حتی در صورت آگاهانه بودن ماهیت مسئله نیز نمی توان از روش های هیوریستیکی استفاده کرد. به عنوان مثال در صورتی که هدف یافتن همه مسیرهای ممکن از تبریز به شیراز باشد، استفاده از هیوریستیک تنها موجب پیچیده شدن الگوریتم و حتی موجب ناقص بودن جواب های مسئله خواهد شد.
سیستم های پویا سیستم هایی هستند که در آنها به طور مداوم ورودی ها و حالت مسئله در حال تغییر است و هربار تغییر در یکی از پارامترها موجب خواهد شد که عمل جستجوی مجددی در فضای جستجو انجام پذیرد. در چنین مواردی ممکن است مدت زمان پاسخ دهی سیستم برای حل مساله بسیار کم باشد. همچنین ممکن است سیستم مدت زمان کافی برای حل مساله در اختیار داشته باشد که هریک از این موارد تاثیر بسزایی در طراحی الگوریتم جستجو خواهند داشت.
فرض کنید می خواهیم در یک صفحه شطرنج استاندارد، 8 وزیر را به گونه بر روی صفحه شطرن قرار دهیم که هیچیک از آنها وزیر دیگری را گارد ندهند. در این مسئله که به مسئله 8 وزیر معروف است، محدودیتی وجود دارد که بر اساس آن هیچ وزیری باید همدیگر را گارد ندهند. به صورت تجربی می توان چنین گفت که بیشتر مسائلی که با آنها سروکار داریم دارای محدویت هایی در مسئله هستند. به چنین مسائلی مسائل ارضای محدودیت نیز می گوییم. وجود محدودیت در مسئله قدری موجب پیچیدگی مسئله می شود اما در اکثر موارد نیز موجب خواهد شد فضای جستجو مسئله بسیار کوچکتر از حالتی باشد که در آن مسئله هیچ محدودیتی در خود ندارد.
مسائلی که در عمل با آنها مواجه هستیم ترکیبی از موارد فوق را در خود دارند. به عنوان مثال در مسئله ی 8 وزیر ، مسئله دارای محدودیت بوده ولی در مقابل هدف یافتن تنها یک جواب در مدت زمان معقول است و در واقع یافتن جواب در آن نیازی به بلادرنگ بودن ندارد.