لینک دانلود و خرید پایین توضیحات
فرمت فایل word و قابل ویرایش و پرینت
تعداد صفحات: 7
فصل سوم:حل مسئله با جست وجو
فاطمه کاکائی-الهه نعیمی خامه کار
1.تعریف مفاهیم زیر؟
حالت:یک حالت شرایطی ست که یک عامل می تواند خودش را در آن بیابد.ما دو نوع حالت را می توانیم تشخیص دهیم:وضعیت های جهان (شرایط پیوسته ای واقعی در جهان واقعی) وضعیت های نمایشی(عامل ها بعد از تعمق در کاری که انجام می دهند شرح انتزاعی از جهان واقعی ارائه می دهند )
فضای حالت:یک گراف است که نودهای آن همه حالت ها را نشان می دهند،و اتصالات آن فعالیتهایی هستند که برای انتقال از یک حالت به حات دیگراتفاق می اقتند.
درخت جستجو:یک درخت جستجو درختی است که(یک گراف با سیکل های غیر مستقیم)که در آن نود ریشه نود شروع است فرزندان آن را برای هرنود متشکل از حالت های قابل دسترس برای انجام هر فعالیت ،قرار می دهد.
نود جستجو:یک نود در درخت جستجوست
هدف:مجموعه ای از حالت های دنیا در نظر می گیریم.وظیفه عامل یافتندنباله ای است از فعالیتها آن را به حالت هدف می رساند.
فعالیت:چیزی است که عامل می تواند آنرا برای انجام انتخاب کند.
تابع جانشین:خصوصیات عامل ها را شرح می دهد:یک مجموعه حالت برمی گرداند،جفت(حالت،فعالیت)،جاهایی که هرحالت یک حالت قابل دسترس به وسیله فعالیتی است که انجام می دهد.
Branch Factor: در درخت جستجو تعداد فعالیت های در دسترس یک عامل.
2.چرافرموله بندی مسئله باید از فرموله کردن هدف پیروی کند؟
در فرموله کردن هدف،ما تصمیم داریم از دید جهانی که ما به آن تمایل داریم و می توانیم چشم پوشی کنیمیا به طور انتزاعی از آن برداشت کنیم.سپس در فرموله کردن مسئله ما تصمیم می گیریم که چگونه نماهای مهم را دستکاری کنیم (وچشم پوشی کنیم از بقیه نماها).اگر ما ابتدا فرموله کردن مسئله را انجام داده باشیم ما نخواهیم فهمید شامل چه چیزهایی می شود و شامل چه چیزهایی نمی شود،که گفته می شود هنگامی که یک حلقه تکراری از فرموله کردن مسئله،فرموله کردن هدف و حل مسئله داریم، این اتفاق می تواند بیفتدتا زمانی که یکی از اینها به یک درجه سودمندی یا راه حل موثر برسد.
3.در این بازی ما داریم:
Successor fn_:result .وlegal action راتابع جانشین تعریف می کند.
Def successor_fn(S)
Return[(a,result[a,s])for a in legal_ actions(s)]
_legal action &result تعریف شده در تابع جانشین هستند.به این صورت:
Def legal_ actions;
Return(a for[a,s] in successor_fn(s)]
Def result(a,s);
for(a1,s1) in successor_fn(s)
if a==a1
return s1;
4.حالت های معمای8 به دو مجموعه مجزاتقسیم می شوند.به طوری که هیچ حالتی در یک مجموعه نمی تواند به حالت دیگری در مجموعه دیگری تبدیل شود.رویه ای که بیان کند که حالت مورد نظر در کدام مجموعه است؟
تعریف:حالت هدف ارقامی به یک ترتیب خاص دارد،که ما محاسبه می کنیم آنها را از یک گوشه ی بالای سمت چپ،سپس از چپ به راست پردازش می کنیم و وقتی ما به آخر یک سطر رسیدیم می آییم به چپ ترین مربع سطر زیر.برای هر پیکربندی کناری دیگر،با وجود یک کاشی بزرگتردرون پردازش می کند یک کاشی را بار قم کوچکتر،که گفته می شود دو کاشی معکوس یکدیگرند.
موضوع:برای پییکربندی یک پازل داده شده:
N را جمع همه ارقام معکوس و تعداد سطرهای مربع های خالی در نظر بگیرید.سپس (Nmod2) ثابتی است برای هرحرکت قانونی.به عبارتی دیگر بعد از یک حرکت قانونی یک N فرد باقیمانده فردی خواهدداشت و یک N زوج باقیمانده زوج.بنابراین حالت هدف در شکل 3- با هیچ معکوسی ومربع خالی در اولین سطر مواجه نخواهدشد.داریم N=1 حالت شروع را با N فرد آغاز می کنیم نه زوج.
دلیل:اول از همه یک کاشی را به صورت افقی عوض می کند اما نه با همه ارقام معکوس وتعداد سطرمربع های خالی.بنابراین بهتراست که یک لغزش عمودی را داشته باشیم.
ابتدا تصورکنید که کاشی A به طور مستقیم در امتداد مربع خالی قرار گرفته وآنرا لغزش بدهید به سمت پایین وآن را عوض کنید با سطر زوج مربع خالی. مجموع ارقام معکوس را حساب کنید.حرکت فقط از A,B,C,D انجام می گیرد.اگر هیچ کدام از B,C,D سبب یک نسبت معکوس از A نشوند (مثلا هرسه از A بزرگتر باشند)سپس بع از لغزش یک سه تایی از جمع معکوسات بدست می آید.اگر یکی از این 3کوچکتر از A باشد،سپس قبل از حرکت B,C,D در یک معکوس مجرد حرکت می کنند.درحالی که بعد حرکت آنها شرکت می کنند دردو inversion.یک تغییر از 1 همچنین یک تغییر از یک عدد فرد.دو مورد اضافی متفاوت به روشنی منجرب یک نتیجه می شوند.بنابراین تغییر در جمع N معمولا به وجود می آید.این دقیقا چیزی است که می خواهیم نمایش دهیم.
بنابراین ما قبل از اینکه حل کنیم یک پازل را باید حالت شروع و پایان N رامحاسبه کنیم.و مطمئن شویم هردو یک مقدار رادارند.به عبارت دیگر هیچ راه حل ممکن دیگری وجود ندارد.
5.فرموله کردن آن به این ترتیب است که هروزیر را در هرستون قرار می دهد.هروزیر در یک مربع قرار می گیرد که وزیر بعدی نتواند نسبت به آن گارد بگیرد.برای ساده سازی ابتدا از مسئله n رخ استفاده می کنیم.اولین رخ دراولین مربع ستون اول قرار می گیرد.دومین رخ در هرمربعی به جز ستون 2همان سطری که رخ در ستون 1آن قرار داشته ،قرا می گیرد ومعمولا فضای حالت آن n! خواهد بود.
6.یک فضای حالت پایانی همیشه یک درخت جست وجو پایانی نیست.یک فضای حالت با دو وضعیت دارند.هرکدام ازفعالیتهای آنها منجرب فعالیت دیگری می شوند.این یک درخت جست وجوی پایانی محسوب می شود زیرا ما امکان بازگشت داریم.نابراین اگر فضای حالت درخت پایانه باشد یک حالت پایانه غیرمدور باشد ،هیچ سیکلی ندارد ودرخت جست وجو یک درخت پایانه است.
7.a.حالت اولیه هیچ ناحیه ای رنگ نشده.
تست هدف:همه مکان ها رنگ شدند وهیچ دو ناحیه ای یک رنگ ندارند
تابع جانشین:هر رنگ را برای یک ناحیه در نظر بگیرید.
تابع هزینه:تعداد گذرها یا تصورات
.b.حالت اولیه:شرح درمتن
تست هدف:موزها دست میمون باشد
تابع جانشین:HOP on ,HOP offو PUSH از یک نقطه به نقطه دیگر
تابع هزینه:تعداد فعالیت ها
.c حالت اولیه:همه رکوردهای ورودی به حساب می آید
تست هدف:در نظر گرفتن یک رکورد مجرد و گرفتن یک پیغام خطا
تحقیق درمورد حل مسئله با جست وجو 7 ص
