مسائل خوش تعریف


در کتاب راسل پس از درج تیتر مسائل خوش تعریف (البته عنوان کامل مسائل و راه حل های خوش تعریف میباشد) مجموعه ای از مفاهیم تعریف شده و در ادامه ی کتاب  مسائلی را  به صورت عملی بررسی کرده است. این مطلب، عملا آخرین مطلبی است که فقط از نظر تئوری هوش مصنوعی را مورد بررسی قرار میدهد و از مطلب نهم بطور مستقیم با حل عملی مسائل در قالب برنامه نویسی و یا همان ساخت نرم افزار های هوشمند درگیر خواهیم شد. تا اینجا یعنی تا مطلب هشتم، ما دو فصل اول کتاب راسل را مرور و بررسی نموده ایم. از آنجا که در اقدامی انقلابی،  برای پیاده سازی پروژه های هوش مصنوعی از زبان C شارپ استفاده میکنیم به شما نیز پیشنهاد میکنم که این زبان را بیاموزید.

مسائل خوش تعریف

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

وضعیت اولیه

 وضعیت اولیه آن وضعیتی است که عامل هوشمند در شروع کار و یا به زبانی دیگر در لحظه شروع حل مسئله، در آن قرار دارد.

عملگر

مجموعه واکنش های موجود برای یک عامل هوشمند از عملگرها تشکیل شده است. برای مثال عملگر حرکت به چپ راست و یا جلو. شما میتوانید عملگر را همان واکنش عامل هوشمند در نظر بگیرید.

فضای وضعیت

از ترکیب دو مفهوم بالا یعنی وضعیت اولیه و عملگر ها به مفهومی بنام فضای وضعیت میرسیم. برای مثال فرض بفرمایید عامل هوشمند در وضعیت 1 قرار دارد. حال با اعمال عملگر حرکت به جلو به وضعیت شماره 3 دست پیدا خواهیم کرد. حال در این مثال به مجموعه وضعیت های 1 و 3 و تمامی وضعیت های ناشی از اعمال عملگر ها بر وضعیت های موجود، فضای وضعیت میگویند.

تست هدف

تست هدف را میتوان فانکشنی تعریف نمود که به وسیله آن میتوان تشخیص داد که آیا وضعیت جاری که عامل هوشمند در آن قرار دارد همان وضعیت هدف است  یا خیر.

تابع هزینه مسیر

تابع هزینه مسیر آن تابعی است که هزینه مجموعه عملگر ها و یا همان واکنش ها را از وضعیت شروع تا وضعیت هدف اندازه گیری مینماید. یکه مثال بسیار رایج دراین زمینه ترافیک خیابان ها ی یک شهر بزرگ میباشد. وقتی که شما از نرم افزار Google Map استفاده مکنید بین دو مسیر مختلف آنکه از ترافیک کمتری برخوردار است از هزینه کمتری نیز برخوردار میباشد. یادمان باشد تابع هزینه خود میتواند مجموعه ای از زیر تابع ها باشد. مثلا در مثال فوق میتوان میزان مصرف سوخت و طول مسیر رانده شده توسط راننده را نیز به تابع هزینه اضافه نمود.

با توجه به مجموعه تعاریف فوق ساختمان داده ای که بیان گر یک مسئله باشد را میتوان به صورت زیر تعریف نمود.

  • datatype PROBLEM
  •  components: INITIAL-STATE, OPERATORS, GOAL-TEST, PATH-COST-FUNCTION

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

الگوریتم جستجو

الگوریتم جستجو آن  تابعی است که عامل هوشمند را از مسئله به راه حل میرساند. یعنی مسئله را به عنوان ورودی دریافت کرده و راه حل را به عنوان خروجی باز میگرداند

کار آمدی یک الگوریتم جستجو در حل یک مسئله

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

درخت جستجو

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

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

فرض کنید که شما یک نرم افزار هوشمند بر روی موبایل ساخته اید که مانند نرم افزار Google Map در مسیر یابی به شما کمک میکند. حال فرض کنید که شما در وضعیت اولیه میدان تجریش قرار داشته و قصد سفر به  میدان امات که وضعیت هدف میباشد را دارید. پس شما نرم افزار راه اندازی کرده و GPS گوشی همراه خود را روشن مینمایید. از این لحظه نرم افزار با بررسی موقعیت GPS متوجه میشود که وضعیت اولیه  برابر با میدان تجریش میباشد. حال با توجه به نقشه ای که از قبل به نرم افزار داده ایم، (مثلا نقشه خطوط تاکسیرانی تهران) عامل هوشمند نرم افزار متوجه میشود که از تجریش میتوان به سه وضعیت چهار راه پاسداران ، سید خندان و رسالت نقل مکان نمود. پس بیایید کمی مسئله را علمی تر بیان کنیم. در لحظه صفر در فضای وضعیت تنها وضعیت تجریش وجود داشت. پس از گسترش وضعیت اولیه تجریش توسط عامل هوشمند سه وضعیت جدید رسالت، سید خندان و پاسداران نیز به فضای وضعیت اضافه شد. نکته ای که در اینجا کاملا واضح است این است که بین وضعیت اولیه تجریش و سه وضعیت جدید یک مسیر موجود میبشاد. اگر شکل این ارتباط را به صورت بصری تصور کنید تصویر یک درخت وارونه را خواهید دید. به شکل زیر توجه بفرمایید. فرض کنید مثلا گره A میدان تجریش ، D رسالت، C پاسداران و B سیدخندان باشند. (البته که نقشه تاکسیرانی تهران از میدان تجریش بسیار گسترده تر از درخت زیر میباشد. این تصویر در واقع تنها قسمت بسیار کوچکی از درخت است)

اگر فرض کنیم که نود I میدان هفت حوض و K میدان امامت باشد، مشخص خواهد شد که عامل هوشمند پس از گسترش نود رسالت و سپس گسترش نود گره ) میدان هفت حوض با اسفاده از تابع تست هدف متوجه وضعیت هدف خواهد شد. (تا این لحظه نرم افزار هنوز هیچ واکنشی نشان نداده) در این لحظه و پس از تشخیص وضعیت هدف نرم افزار از وضعیت هدف به سمت وضعیت اولیه یک پیمایش انجام داده و معکوس این پیمایش را به عنوان پاسخ بر روی صفحه ی گوشی شما نشان خواهد داد. 

بگذارید قبل از آنکه از موضوع درخت جستجو بگذریم، چند سوال مهم را مطرح کنیم تا ذهن شما را مقداری درگیر کنند! این درگیری در مطالب آینده به شما کمک بسیاری خواهد نمود.

سوال اول : در نقشه واقعی تاکسی رانی تهران از هر سه مسیر پاسداران، رسالت و سید خندان به مقصد امامت حداقل یک مسیر موجود است. بیاید مسیر ها را مرور نماییم.

  1. تجریش – رسالت – هفت حوض – امامت
  2. تجریش – پاسداران – رسالت – هفت حوض – امامت
  3. تجریش – سید خندان – رسالت – هفت حوض – امامت

اگر عامل هوشمند پس از بررسی فضای وضعیت قبل از وضعیت رسالت، یکی از دو وضعیت دیگر را بررسی میکرد چه اتفاقی پیش می آمد؟ آیا فکر نمیکنید بصورت طبیعی کرایه ی مسافر و زمان و مسافت مسیر افزایش میافت؟!

سوال دوم : آیا با توجه به توضیحات بالا هنوز هم استفاده از واژه درخت جستجو را صحیح میدانید؟! آیا این مسیر ها یک گراف را تشکیل نمیدهند ؟!

سوال سوم : اگر از رسالت به تجریش یک خط تاکسیرانی وجود داشته باشد (که قطعا دارد!) درخت جستجوی فوق چه شکلی خواهد داشت؟! آیا ممکن است در طول یافتن پاسخ در حلقه های بی پایان محبوس شویم ؟!

خواص الگوریتم هایی که بر روی درخت، جستجو انجام میدهند

  • کامل بودن : آیا الگوریتم استفاده شده توسط عامل هوشمند در صورت وجود یک راه حل قطعا آن را پیدا خواهد کرد؟
  • پیچیدگی زمانی : چه مقدار زمان صرف یافتن راه حل خواهد شد؟
  • پیچیدگی فضای حافظه : چه مقدار حافظه صرف یافتن راه حل خواهد شد؟
  • بهینه بودن راه حل : آیا راه حل ارائه شده توسط الگوریتم جستجو بهینه میباشد؟ (بهترین راه حل است)
One Comment

Add a Comment

Your email address will not be published. Required fields are marked *

Copy Protected by Chetan's WP-Copyprotect.