توضیحات
برنامه نویسی الگوریتم جستجوی کلاسیک به زبان پایتون python
هدف این پروژه آشنایی شما با الگوریتمهای جستجوی کلاسیک و نحوه فرموله کردن مسائل جستجوی مختلف در قالب یک رابط یکسان است.
در این پروژه میبایست مجموعه ای از الگوریتمهای جستجوی کلاسیک که فهرست آنها در ادامه ذکر شده است را پیادهسازی و از این الگوریتم ها برای حل چند مساله جستجوی مختلف که در قالب یک واسط مشخص پیادهسازی میشوند استفاده کردیم. پیادهسازی الگوریتمها و مسائل مختلف میبایست به صورت مستقل از یکدیگر باشند به گونهای که حل یک مساله جستجوی جدید نیازمند هیچ گونه تغییری در پیادهسازی الگوریتم های جستجو نباشند. هر الگوریتم جستجو میبایست در انتهای اجرا، اطلاعات کافی در مورد اجرای الگوریتم مانند تعداد گرههای مشاهده شده، تعداد گرههای بسط داده شده، بهترین مسیر یافته شده، هزینه مسیر یافته شده، و حداکثر حافظه استفاده شده (بر حسب تعداد گرههای نگهداری شده در حافظه) را بازگرداند.
الگوریتمها:
الگوریتمهایی که میبایست در این پروژه پیادهسازی کنید عبارتند از:
– سطح اول
– عمق اول )در سه حالت نامحدود، با عمق محدود و با افزایش تدریجی عمق(
– هزینه یکنواخت
– دوجهته
– A*
الگوریتمهای پیادهسازی شده میبایست قابلیت اجرا در دو حالت جستجوی درختی و گرافی را دارا باشند.
مسائل:
به ازاء هر یک از مسائل که در این بخش معرفی میشود شما میبایست یک داده ساختار state برای نگهداری حالت مساله و یک کلاس Problem بنویسید که در آن توابع لازم برای تعریف مساله (تابع حالت اولیه، عملهای ممکن در هر حالت، نتیجه هر عمل، آزمایش هدف، هزینه مسیر و گام، و تابع شهودی مورد استفاده) پیادهسازی شده باشند.
با اجرای الگوریتمهای جستجوی ذکر شده برای هر مساله، عملکرد این الگوریتمها در حل مساله مورد نظر را بررسی و با یکدیگر مقایسه کنید.
مساله اول: پارچ آب
در این مساله به شما دو پارچ با سایزهای ۳ و ۴ لیتر و یک شیر آب که به مقدار نامحدود آب دارد، داده میشود. شما میتوانید با شیر آب، پارچها را پر کنید و یا اینکه پارچها را بر روی زمین خالی کنید. همچنین میتوانید از یک پارچ داخل پارچ دیگر آب بریزید.
توجه داشته باشید که بر روی هیچ یک از پارچها اندازهها علامتگذاری نشده است و تنها اطلاعاتی که از اندازه آنها موجود است اندازه کل پارچ است. با استفاده از الگوریتمهای جستجو باید طوری پارچها را خالی و پر کنید که در نهایت پارچ ۴ لیتری به اندازه ۲ لیتر آب داشته باشد.
همانطور که مشخص است برنامه شما ورودی نخواهد داشت و خروجی نیز به صورت توالی از اعمال است که جهت رسیدن به هدف نهایی انجام میشود. نتایج خود را برای این مساله گزارش کنید. برای حل مساله از الگوریتم های زیر استفاده نمایید:
– عمق اول(گرافی)
– دوجهته
مساله دوم: پازل ۸ تایی
مساله پازل ۸ تایی همانطور که در کلاس معرفی شد، یکی از معروفترین مسائل جستجو است. در این مساله یک ماتریس ۳×۳ به عنوان ورودی داده میشود که تنها خانه ۰ آن با خانههای مجاورش میتواند جابهجا شود و برنامه شما تنها با انجام دادن همین حرکات باید مساله را طوری حل کند که در نهایت ماتریس خروجی به شکل زیر باشد:
با استفاده از الگوریتم های جستجوی زیر اقدام به حل این مساله نمایید.
- سطح اول (درختی)
- عمق اول (با عمق محدود ۸ )
- A* با تابع شهودی مجموع فواصل مستقیم خانه هر عدد با خانهای که باید حضور داشته باشد.
مساله سوم: مسیریابی ربات
در این مساله یک ربات در یک محیط ?×? خانهای قرار است از نقطه شروع (0,0) به نقطه هدف (1-,m1-(n برود. ربات در هر حرکت میتواند به یکی از خانههای مجاور خود (بالا، پایین، چپ و راست) حرکت کند. ربات از خانههایی که با مقدار صفر مشخص شدهاند نمیتواند عبور کند. در این مساله یک ماتریس ?×? شامل درایه های ۰ و ۱ است که در صورتی که درایه ۱ باشد، ربات میتواند در آن وارد شود و اگر ۰ باشد به معنای دیوار است و ربات نمیتواند در آن قرار گیرد. برای مثال نمونه ورودی زیر را در نظر بگیرید:
خروجی شما از این مساله یک مسیر از خانه 0) (0, به خانه 1)-1,m-(n است.
نتایج خود را برای این مساله گزارش کنید. برای حل مساله از الگوریتم های زیر استفاده نمایید:
– هزینه یکنواخت (هزینه حرکت از هر خانه به خانه مجاور آن را برابر یک در نظر بگیرید)
– دو جهته
– A* با تابع شهودی فاصله منهتن
برنامه نویسی الگوریتم جستجوی کلاسیک به زبان پایتون python توسط کارشناسان گروه ۱.۲.۳ پروژه پیاده سازی گردیده و به تعداد محدودی قابل فروش می باشد.فایلهای پروژه به صورت کامل پس از خرید فایل بلافاصله در اختیار شما قرار خواهد گرفت.
سفارش پروژه مشابه
درصورتیکه این پروژه دقیقا مطابق خواسته شما نمی باشد، با کلیک بر روی کلید زیر پروژه دلخواه خود را سفارش دهید.
دیدگاهها
هیچ دیدگاهی برای این محصول نوشته نشده است.