فضای جستجو در الگوریتم — بررسی فضای حالات 2 مسئله معروف
معمولاً چالش عمده در فرآیند حل یک مسئله شناخت صحیح از فضای جستجوی آن مسئله و انتخاب یک استراتژی برای جستجوی در آن فضا می باشد. قبل از پرداختن به استراتژی های جستجو اول باید درک درستی از فضای جستجو داشته باشیم. پس با این مقاله آموزشی با ما همراه باشید.
مقدمه
منظور از فضای جستجو، تمام حالات ممکن از یک راه حل است که احتمال وقوع آنها وجود دارد. این فضا می تواند بصورت گسسته یا پیوسته باشد. در فضای گسسته، حالات محدود و قابل شمارش می باشد مانند بازی شطرنج یا بازی هشت وزیر، اما در فضا های پیوسته فضای حالات نامتناهی است مانند فضای حالت مربوط به ماشین های بدون سرنشین.
در این بخش کاری به درست یا نادرست بودن راه حل، بهینه و غیر بهینه بودن آن نداریم. فقط هدف تولید همه حالات قابل دسترس می باشد. برای شروع جستجو ابتدا باید نقطه شروع در دسترس باشد، در حالت کلی از مجموعه زیر برای تولید فضای حالت استفاده می کنیم:
{S,Avail(S), Action(S), Result(S,a), Cost(S,a)}
در مجموعه بالا
- S: حالت شروع مسئله
- Avail: ارزش یک حالت که براساس پارامترهای مختلفی می تواند ارزیابی و ارزش گذاری شود.
- Action: فعالیت مجازی که در این وضعیت می توانیم انجام دهیم
- Result: نتیجه حاصل از انجام یک فعالیت مجاز یک
- Cost: هزینه انجام آن عمل
فضای جستجو در الگوریتم
همانطور که قبلاً نیز اشاره شد فضای جستجو، تمام حالات ممکن از یک راه حل است که احتمال وقوع آنها وجود دارد. برای درک بهتر موضوع، برای دو مسئله معروف در هوش مصنوعی ( بازی پازل 8 و رانندگی بدون سر نشین) فضای حالت را ترسیم می کنیم.
مثال 1 — فضای جستجو بازی پازل هشت
بازی پازل هشت یک پازل کشویی در یک شبکه 3*3 است با هشت مربع که با اعداد 1 تا 8 برچسب گذاری شده است. هدف از این بازی جا به جا کردن مربع هاست به شکلی که از 1تا 8 مرتب شوند. و حرکت های مجاز در این بازی حرکت در راستای افقی و عمودی به صورت بالا و پایین و چپ و راست می باشد.
- S: برای این بازی فرض می کنیم هرچیدمانی از اعداد 1 تا 8 و یک خانه خالی می تواند به عنوان حالت شروع انتخاب شود.
- avail: هر چیدمان می تواند بر اساس یک ویژگی ارزیابی شود، مثلا تعداد مهره هایی که در خانه درست قرار دارند یا تعداد مهره هایی که در خانه های اشتباه قرار دارند.
- Action: فعالیت های مجاز بسته به محل قرارگیری خانه خالی می تواند حرکت در راستای افقی و عمودی به صورت بالا و پایین و چپ و راست می باشد.
- Result(S,a): با انجام فعالیت a بر روی حالت S یک چیدمان جدید از اعداد 1 تا 8 حاصل می شود.
- Cost(S,a): هزینه عمل در این مسأله با توجه به این که حرکات مجاز بالا، پایین، چپ و ر است فرقی باهم ندارند باهم یکسان می باشد. مثلا هر جابجایی یک واحد هزینه خواهد داشت.
در مثال فوق از حالت شروع با انجام چهار حرکت مجاز U بالا، D پایین، L چپ و R راست، چهار حالت مجاز به دست می آید، که با بسط دادن هر کدام از حالت ها با استفاده از حرکات مجاز فضای حالتی به شکل درخت تشکیل خواهد شد که در شکل بخشی از آن را مشاهده می کنید. این یک نمونه فضای حالت گسسته می باشد که تعداد حالت آن هرچند زیاد است ولی متناهی است.
مثال 2 — فضای جستجو در رانندگی بدون سرنشین
فرض کنید یک اتومبیل کنترل از راه دور دارای یک کنترلر با سه کلید تنظیم می باشد. یک کلید برای تنظیم دور موتور، یک کلید برای تنظیم بادگیر عقب و یک کلید برای تنظیم زاویه چرخ هاست. با کم و زیاد کردن این کلید ها سرعت اتومبیل کم و زیاد خواهد شد.
- S: در این مسأله وضعیت ایستاده اتومبیل به عنوان حالت اولیه در نظر گرفته می شود.
- AVAIL: ارزش هر حالت از ترکیب این سه کلید بر اساس سرعت اتومبیل در آن لحظه ارزیابی و ارزش گذاری می شود
- ACTION: فعالیت های مجاز برای تغییر حالت می تواند تغییر مقدار یک یا چند کلید کنترلر باشد.
- Result(S,a): سرعت حاصل از انجام تغییرات بر روی کلید یا کلید ها نتیجه آن فعالیت را مشخص می کند.
- Cost(S,a): در این مسأله با فعالیت ها هزینه یکسانی دارند.
اگر هر کدام از کلیدها به عنوان یک بعد از فضای مسئله در نظر گرفته شود فضای حالتی سه بعدی به شکل زیر ایجاد خواهد شد(دامنه مقادیر هر کدام از کلید ها می تواند به دلخواه مقدار دهی شود)
در شکل فوق رنگ قرمز نشانگر یک سرعت مطلوب و رنگ زرد یک سرعت متوسط و رنگ آبی نشانگر سرعت پایین است. فرض کنید کلید اول مقدار0.4، کلید دوم 1.1 و کلید سوم 1.009 باشد، در این حالت به یک نقطه به رنگ قرمز یعنی سرعت مناسب خواهیم رسید.
این مسئله یک نمونه از فضای حالت پیوسته می باشد که تعداد نا متناهی حالت برای آن می توان در نظر گرفت.
نتیجه گیری از فضای جستجو در الگوریتم
به طور کلی قبل از پرداختن به حل یک مسئله باید فضای جستجوی آن مورد بررسی قرار گیرد. با جستجوی حالات حل یک مسئله بهتر می توان روش حل آن را پیدا کرد. به طور کلی در اکثر الگوریتم های هوش مصنوعی اولین قدم برای شروع، پیدا کردن فضای جستجو خواهد بود. در پایان توجه شما را به ویدئوی آموزش فضای جستجو در الگوریتم که توسط دکتر مرتضی نصیر اقدم تدریس شده، جلب می کنیم.
مباحث مرتبط
- الگوریتم *A ای استار — راهنمای جامع همراه با مثال
- سورس کد حل مسئله 8 وزیر با روش عقبگرد Back tracking در متلب
- سیستم های خبره هوش مصنوعی چیست — ویژگی ها و کاربردهای سیستم خبره
- الگوریتم جستجوی عرضی Breadth First Search — راهنمای جامع همراه با مثال
- کتابخانه های هوش مصنوعی پایتون – 15 کتابخانه محبوب و پر استفاده
- حل مسئله کوله پشتی با الگوریتم SA در متلب
- پیاده سازی الگوریتم a star در بازی maze برای یافتن کوتاهترین مسیر
- الگوریتم جستجوی عمقی Depth First Search — راهنمای جامع همراه با مثال
درباره مرتضی نصیر اقدم
دانشجوی دکتری تخصصی هوش مصنوعی، مدرس دانشگاه آزاد اسلامی، کارآفرین برتر در حوزه کسب و کارهای هوشمند، ایده پرداز در حوزه کسب و کارهای دیجیتال. ایشان در زمینه برنامه نویسی های هوشمند، الگوریتم های تکاملی و زبان های برنامه نویسی هوش مصنوعی سابقه تدریس فعال دارند.