Description

دانشگاه تهران
پردیس دانشکدههای فنی
دانشکده مهندسی برق و کامپیوتر

درس هوش مصنوعی
پروژه یک – سرچ
مهلت ارسال تا 21 مهر

طراحان پروژه: امید بداقی ،راستین سورکی ،طاها شعبانی

پاییز ۹۹
مقدمه

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

تعریف مسأله

مسئله مشابه بازی snake بوده و به شرح زیر است:
در یک صفحه دو بعدی که در ورودی ابعاد آن مشخص می شود، در ابتدا یک مار با طول برابر 1 و مختصات اولیه مشخص و تعدادی دانه وجود دارد. وظیفه مار این است که در بهینه ترین حالت ممکن همه ی دانه ها را بخورد.
در هر حرکت، مار می تواند به یکی از جهات ممکن یعنی بالا، پایین ، چپ و یا راست حرکت کند و در صورتی که دانه ای را بخورد طول مار یکی افزایش پیدا می کند.
دانه ها می توانند امتیاز 1+ و یا 2+ داشته باشند که این امتیاز مشخص میکند چند بار دانه باید توسط مار خورده شود تا از صفحه بازی حذف شود. توجه کنید که هر بار خوردن دانه طول مار را یکی زیاد می کند و برای دانه های 2 امتیازی و پس از یکبار خوردن آن، بدن مار باید به طور کامل از دانه باقی مانده خارج شود تا دوباره بتواند آن دانه را بخورد ) مار فقط با سر خود دانه را میخورد( .
اگر مار به دیواری برسد می تواند از آن عبور کند و از جهت دیگر دوباره وارد صفحه شود .همچنین در صفحه هیچ مانعی وجود ندارد و مار اجازه برخورد با بدن خودش را ندارد.

نکته : در هر حرکت مار، اگر دانه ای خورده نشود. آخرین خانه ی مار حذف و یک خانه در جهت حرکت، به مار اضافه می شود. در صورتی که مار دانه ای را بخورد، دیگر خانه ای حذف نمیشود و تنها یک خانه در جهت حرکت، به مار افزوده می شود.
در ادامه چند مثال برای درک بهتر بیان می کنیم: )در این مثال ها حرکت بالا را با) 0،1-(، حرکت پایین را با )0،1+(، حرکت راست را با) 1+،0( و حرکت چپ را )1-،0( مشخص شده اند(.
مثال1. اگر مار به ترتیب از ته به سر، خانه های) 0،4( ، )1،4( و) 2،4( را در برگرفته باشد و دانه ای را در مختصات) 2،4( بخورد و به راست حرکت کند، مختصات جدید مار خواهد بود: )0،4( ، )1،4( و) 2،4( و) 3،4( و اگر دانه ای در خانه) 2،4( وجود نداشته باشد مختصات مار )1،4( ، )2،4( و) 3،4( خواهد شد.
مثال2. اگر مار به ترتیب از ته به سر، خانه های )1،2( ، )2،2( ، )2،3( و) 1،3( را در برگرفته باشد و به بالا حرکت کند، مختصات جدید مار خواهد شد: )2،2( ، )2،3( ، )1،3( و) 1،2(.

مثال3. مار فقط در صورتی که طولش برابر با 1 با شد میتواند به هر 4 جهت حرکت کند. در غیر این صورت برای حرکت بعدی حداکثر سهه جهت باقی میماند. برای مثال اگر مار به ترتیب از ته به سهر، خانه های )1،1( و) 1،2( را در برگرفته باشهد، حرکت بعدی می تواند پایین، چپ و راست باشد زیرا در بالای سر مار، خانه) 1،1( قرار دارد که جزئی از خود مار است.

فرمت ورودی

اطلاعات اولیه مسئله در یک فایل با فرمت زیر در اختیارتان قرار خواهد گرفت:
1. سایز صفحه بازی ) عرض و طول صفحه(
2. مختصات اولیه مار در صفحه
3. تعداد دانه های موجود در صفحه
4. مختصات هر دانه به همراه امتیاز آن

برای مثال:
7,6
0,0
5
3,4,1
2,2,1
6,1,2
5,2,1
4,5,2

که در این مثال صفحه دوبعدی با ابعداد )6،7( ، مختصات اولیه مار) 0،0( و 5 دانه وجود دارد که دانه های با مختصات) 1،6( و) 5،4( امتیاز 2+ و بقیه 1+ هستند.

شما باید فایل های ورودی مسئله که مشابه مثال بالا هستند را خوانده و مسئله را با دو روش جستوجوی ناآگاهانه BFS و IDS و روش جستوجوی آگاهانه *A حل و پیاده سازی کنید. برای روش *A شما باید 2 heuristic استفاده کنید که هر دوی آنها admissible باشند و حداقل یکی از آنها باید consistent هم باشد و جواب بهینه را تولید کند. توجه کنید که ممکن است
برخی تست ها چندین جواب بهینه داشته باشند که در این صورت پیدا کردن یک جواب کفایت میکند. ) همه ی جواب های بهینه برای یک مسئله دارای طول مسیر برابر هستند( .

همچنین برای جستوجوی آگاهانه بهینه خود، روش *weighted A را نیز به ازای حداقل دو مقدار مختلف α یکی مقادیر نزدیک به عدد 2 و دیگری اعداد بزرگ تر) کمتر مساوی 5 ( بررسی و در گزارش خود توضیح دهید.

محدودیت زمانی اجرا

تست1 تست2 تست3
BFS کمتر از 1 ثانیه کمتر از 10 ثانیه کمتر از 30 ثانیه
IDS کمتر از 2 ثانیه کمتر از 30 ثانیه کمتر از 2 دقیقه
Heuristic حداقل یک کمتر از 1 ثانیه کمتر از 5 ثانیه کمتر از 10 ثانیه

گزارش کار

شما باید در گزارش خود موارد زیر را ذکر کنید. بخشی از نمره شما متعلق به گزارش کار است که تصحیح آن جدا از تحویل پروژه است. از کامل بودن آن اطمینان حاصل کنید.
• شرح نحوه ی مدل کردن مسئله (action ، goal state ، initial state و …( به صورت دقیق.
• توضیح الگوریتم های پیاده سازی شده و تفاوتها و مزیتهای الگوریتمها نسبت به یکدیگر.
• توضیح heuristic های پیاده سازی شده در بخش جستوجوی آگاهانه و مقایسه ی آنها.
• توضیح و علت یابی جواب هایی که در روش *weighted A به دست آمده اند.
• به ازای هر الگوریتم، هر تست کیس را 2 بار اجرا کنید و میانگین زمان اجرا را ثبت کنید .همچنین جدول زیر را کامل کنید:

فاصله جواب مسیر جواب )با حروف
)D,U,L,R تعداد استیت دیده شده تعداد استیت مجزای دیده شده زمان اجرا
BFS
IDS
به ازای هر( A* )heuristic
Weighted A*
)به ازای هر α(

ملاحظات

● موعد تحویل غیرحضوری تا پایان روز 21 مهر میباشد.
● تمامی نتایج باید در یک فایل فشرده با عنوان AI-CA1-<#STID>.zip تحویل داده شود. این فایل باید شامل موارد زیر باشد:
○ یک پوشه به نام Code شامل کدهای تمام قسمتهایی از تمرین که پیاده سازی نمودهاید.

○ گزارش پروژه با فرمت PDF و شههامل شههرح تمامی کارهای انجام شههده، نتایج به دسههت آمده و تحلیلها و بررسیهای خواسته شده در صورت پروژه.
○ درصهورتی که از Jupyter Notebook اسهتفاده میکنید نیازی به ارسهال جداگانه کدها و گزارش نیسهت و هردو را میتوانید در یک فایل Notebook ارائه دهید. حتما خروجی html فایل Notebook خود را نیز همراه فایل Notebook ارسال کنید .
توجه داشهته باشهید که علاوه بر ارسهال فایلهای پروژه، این پروژه تحویل نیز گرفته خواهد شهد. بنابراین میبایسهت بر تمامی قسمت های کدتان تسلط کافی را داشته باشید و تمام بخشهای پروژه باید قابلیت اجرای مجدد در زمان تحویل را داشته باشند. همچنین درصورت عدم حضور در زمان تحویل، نمرهای دریافت نخواهید کرد. ●
هیچگونه شباهتی در انجام این پروژه بین افراد مختلف پذیرفته نمیشود. در صورت کشف هرگونه تقلب برای همه افراد متقلب نمره 100- در نظر گرفته میشود. ●
ا ستفاده از مراجع با ارجاع به آنها بلامانع ا ست. اما در صورتی که گزارش شما ترجمه عینی از آنها با شد، یا از گزارش افراد دیگر استفاده کرده باشید کار شما تقلب محسوب میشود . ●
در صورتی که سوالی در مورد پروژه داشتید بهتر است در فروم درس مطرح کنید تا بقیه از آن استفاده کنند، در غیر این صورت به طراحان پروژه ایمیل بزنید و از یکی از آنها بپرسید .

omid.bodaghi79@gmail.com rastin30@gmail.com taha.shabani.m@gmail.com
موفق باشید! ●