فضای جستجو در الگوریتم — بررسی فضای حالات ۲ مسئله معروف

مقدمه مقاله فضای جستجو در الگوریتم

منظور از فضای جستجو، تمام حالات ممکن از یک راه حل است که احتمال وقوع آنها وجود دارد. این فضا می‌تواند بصورت گسسته یا پیوسته باشد. در فضای گسسته، حالات محدود و قابل شمارش می‌باشد مانند بازی شطرنج یا بازی هشت وزیر، اما در فضاهای پیوسته فضای حالات نامتناهی است مانند فضای حالت مربوط به ماشین‌های بدون سرنشین.

در این بخش کاری به درست یا نادرست بودن راه حل، بهینه و غیر بهینه بودن آن نداریم. فقط هدف تولید همه حالات قابل دسترس می‌باشد. برای شروع جستجو ابتدا باید نقطه شروع در دسترس باشد، در حالت کلی از مجموعه زیر برای تولید فضای حالت استفاده می‌کنیم:

{S,Avail(S), Action(S), Result(S,a), Cost(S,a)}

در مجموعه بالا

• S: حالت شروع مسئله
•  Avail: ارزش یک حالت که براساس پارامترهای مختلفی می تواند ارزیابی و ارزش گذاری شود.
• Action: فعالیت مجازی که در این وضعیت می توانیم انجام دهیم
• Result: نتیجه حاصل از انجام یک فعالیت مجاز یک
• Cost: هزینه انجام آن عمل

چنانچه تصمیم به داشتن ارائه‌ای بهتر و مفید در این زمینه دارید می‌توانید از لینک زیر پاورپوینت مسئله هشت وزیر را نگاهی بیندازید.

• پاورپوینت مسئله هشت وزیر — Eight queens Problem — کلیک کنید.

فضای جستجو در الگوریتم

همانطور که قبلاً نیز اشاره شد فضای جستجو، تمام حالات ممکن از یک راه حل است که احتمال وقوع آنها وجود دارد. برای درک بهتر موضوع، برای دو مسئله معروف در هوش مصنوعی ( بازی پازل ۸ و رانندگی بدون سر نشین) فضای حالت را ترسیم می‌کنیم.

مثال ۱ — فضای جستجو بازی پازل هشت

بازی پازل هشت یک پازل کشویی در یک شبکه ۳*۳ است با هشت مربع که با اعداد ۱ تا ۸ برچسب گذاری شده است. هدف از این بازی جا به جا کردن مربع‌هاست به شکلی که از ۱تا ۸ مرتب شوند. و حرکت‌های مجاز در این بازی حرکت در راستای افقی و عمودی به صورت بالا و پایین و چپ و راست می‌باشد.

• S: برای این بازی فرض می‌کنیم هرچیدمانی از اعداد ۱ تا ۸ و یک خانه خالی می‌تواند به عنوان حالت شروع انتخاب شود.
• avail: هر چیدمان می‌تواند بر اساس یک ویژگی ارزیابی شود، مثلا تعداد مهره‌هایی که در خانه درست قرار دارند یا تعداد مهره‌هایی که در خانه‌های اشتباه قرار دارند.
• Action: فعالیت‌های مجاز بسته به محل قرارگیری خانه خالی می‌تواند حرکت در راستای افقی و عمودی به صورت بالا و پایین و چپ و راست باشد.
• Result(S,a): با انجام فعالیت a بر روی حالت S یک چیدمان جدید از اعداد ۱ تا ۸ حاصل می‌شود.
• Cost(S,a): هزینه عمل در این مسأله با توجه به این که حرکات مجاز بالا، پایین، چپ و ر است فرقی باهم ندارند باهم یکسان می‌باشد. مثلا هر جابجایی یک واحد هزینه خواهد داشت.

در مثال فوق از حالت شروع با انجام چهار حرکت مجاز U بالا، D پایین، L چپ و R  راست، چهار حالت مجاز به دست می‌آید، که با بسط دادن هر کدام از حالت‌ها با استفاده از حرکات مجاز فضای حالتی به شکل درخت تشکیل خواهد شد که در شکل بخشی از آن را مشاهده می‌کنید. این یک نمونه فضای حالت گسسته می‌باشد که تعداد حالت آن هرچند زیاد است ولی متناهی است. جهت آشنایی با فضای جستجو در الگوریتم می‌توانید سورس کد مسئله هشت وزیر با الگوریتم ژنتیک را از لینک زیر مطالعه کنید.

• مسئله هشت وزیر با الگوریتم ژنتیک GA در متلب — کلیک کنید.

مثال ۲ — فضای جستجو در رانندگی بدون سرنشین

فرض کنید یک اتومبیل کنترل از راه دور دارای یک کنترلر با سه کلید تنظیم می‌باشد. یک کلید برای تنظیم دور موتور، یک کلید برای تنظیم بادگیر عقب و یک کلید برای تنظیم زاویه چرخ‌هاست. با کم و زیاد کردن این کلیدها سرعت اتومبیل کم و زیاد خواهد شد.

• S: در این مسأله وضعیت ایستاده اتومبیل به عنوان حالت اولیه در نظر گرفته می‌شود.
• AVAIL: ارزش هر حالت از ترکیب این سه کلید بر اساس سرعت اتومبیل در آن لحظه ارزیابی و ارزش گذاری می‌شود
• ACTION: فعالیت‌های مجاز برای تغییر حالت می‌تواند تغییر مقدار یک یا چند کلید کنترلر باشد.
• Result(S,a): سرعت حاصل از انجام تغییرات بر روی کلید یا کلیدها نتیجه آن فعالیت را مشخص می‌کند.
• Cost(S,a): در این مسأله با فعالیت‌ها هزینه یکسانی دارند.

اگر هر کدام از کلیدها به عنوان یک بعد از فضای مسئله در نظر گرفته شود فضای حالتی سه بعدی به شکل زیر ایجاد خواهد شد(دامنه مقادیر هر کدام از کلیدها می‌تواند به دلخواه مقدار دهی شود)

در شکل فوق رنگ قرمز نشانگر یک سرعت مطلوب و رنگ زرد یک سرعت متوسط و رنگ آبی نشانگر سرعت پایین است. فرض کنید کلید اول مقدار۰.۴، کلید دوم ۱.۱ و کلید سوم ۱.۰۰۹ باشد، در این حالت به یک نقطه به رنگ قرمز یعنی سرعت مناسب خواهیم رسید.

این مسئله یک نمونه از فضای حالت پیوسته می‌باشد که تعداد نا متناهی حالت برای آن می‌توان در نظر گرفت. چنانچه تصمیم به داشتن ارائه‌ای کاربردی در زمینه فضای جستجو هستید می‌توانید از پاورپوینتی که در رابطه با این موضوع در لینک زیر قرار داده‌ایم استفاده کنید.

• پاورپوینت الگوریتم *IDA — جست و جوی تعمیق تکراری — کلیک کنید.

نتیجه گیری از فضای جستجو در الگوریتم

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