|
الگوریتم جستجوی *a در مسئله 8 پازل
سلام
امکان داره الگوریتم جستجوی *a در مسئله 8 پازل توضیح بدین ؟ من در مورد این الگوریتم از کتاب راسل مطالعه کردم و مثالی که برای پیدا کردن کوتاه ترین مسیر برای شهر بخارست زده بود متوجه شدم ولی نمیدونم این الگوریتم تو 8 پازل چجوری پیاده سازی کنم !؟!؟!؟ اگه امکان داره راهنماییم کنید متشکرم |
این مثال هم عین همون مثال بخارست هست. اگر اون رو فهمیدید این هم ساده است.
در این مثال (پازل 8) بخارست ما ، رسیدن به چیدمان هدفه که با شکل نشون داده می شه در هر مسئله خاص. ممکنه ترتیب صعودی از 1 تا 8 به ترتیب از بالاترین ردیف تا پایین ترین ردیف ملاک باشه. به هر جهت مساله حتما حال هدف رو می ده. شهر آراد در این مثال حال شروع هست، که این هم در صورت مساله داده می شه. شهرهای بین راه، هر کدوم یک چیدمان هستند که نه هدف هستند و نه حال شروع. هیورستیک (تخمین هر حالت تا هدف) از دو راه پیشنهاد شده در کتاب اسل (گرچه هیورستیک های خفن تری هم هست که باید سرچ کنید در اینترنت اگر علاقه من هستید) . این دو هیورستیک به شرح زیر هستند: هیورستیک 1: تعداد خانه هایی (شماره هایی) که در جای صحیح خود (با توجه به حال هدف بخارست) نیستند. هیورستیک 2: فاصله منهتن (جمع فواصل افقی و عمودی) هر خانه (شماره) نسبت به حالت هدف(بخارست). حالا بای تابع f=g+h رو مثل مثال بخارست برای هر حالت تشکیل بدید و با اینتخاب کمترین f در هر حالت مسیر بهینه رسیدن از حالت شروع (آراد) به هدف (بخارست) رو پیدا کنید. موفق باشید |
1(ها)ضميمه
متشکر از پاسخ شما
حالت شروع زیر در نظر بگیرید اینجا تابع f برای 8 و 3 بررسی میکنیم . درسته ؟ واسه هر کدوم f کمتر باشه اونو حرکت میدیم ؟اگه f واسه هر 2 برار باشه چیکار میکنیم ؟ آیا برای 8 : h =2 , g =4 هست ؟ تو این مسئله g چجوری باید حساب کنم ؟ متشکرم |
نقل قول:
ببینید. اولا که گویا شما یه عکسی چیزی قرار بوده پیوست کنی که نکردی. من جز نوشته های شما چیزی ندیدم و متوجه حالت اولیه دقیق نشدم. اما در هر صورت الگوریتم *a در شرایط مساوی، اولین سمت چپ ترین گره رو بسط می ده (این یه قرارداده) پس بسته به این که این دو حالت مساوی فرزند کدام گره ها هستند و با توجه به اینکه اول پدر کدوم شون بسط داده شده، اون گره سمت چپ تر و مقدم تره. از طرفی چون الگورتیم همیشه راه بهینه و هدف بهینه رو پیدا می کنه پس نیاز نیست نگران این باشید. اگر نیازمند تحلیل دقیق تر هستید، شکل مورد نظرتون رو اینجا بذارید تا به کمک دوستان بحث کنیم در موردش. موفق باشید |
سلام
ببخشید یادم رفته بود عکس بزارم , پست قبلی وبرایش شد |
ببینید
برای محاسبه این مساله نیاز به حالت شروع و حالت هدف دارید شما یه عکس گذاشتید فقط. ضمن اینکه برای محاسبه g و h در هر حالت نیاز به حالت جاری هم هست (یعنی سه عکس) |
عکس قبلی که گذاشتم حالت شروع هست . حالت هدف هم ب این شکل هست
123 456 78b bهمون خالی هست متشکرم |
f فاصله تا خانه هدف هست و g تعداد خانه های جابجا شده .
در اولین مرحله خانه 8 جابجا میشه و پازل به شکل زیر در میاد 126 45b 738 در این مرحله چون 5 در خانه هدف هست f برای 8 و 6 بررسی میکنم و 6 جابجا میشه در این مرحله پازل به شکل زیر در میاد 12b 456 738 در این مرحله چیکار باید کرد ؟ چون 2 و 6 در خانه هدف هستن ولی f2 = 0 , F6 = 1 آیا برای خانه ای که در هدف هست باید F حساب کنیم ؟ متشکرم |
ببینید، شما باید مقدار h رو برای هر حالت حساب کنید که می شه مجموع فاصله منهتن برای یک یک خانه ها.
هر خانه برای خودش f نداره بلکه یک f برای همه خانه ها در یک حالت مشخص (چه شروع، چه هدف، چه میانی) می تونید حساب کنید که این عدد از جمع g و h حاصل میشه. g می شه هزینه اومدن به این حالت (تعداد حرکات) h می شه فاصله جمع فواصل منهتن برای یک یک خانه ها جمع این دو مقدار در هر حالت که باشید، f شماست. |
امکان داره 2 مرحله از اون حالت شروع توضیح بدین چجوری جلو میرین ؟!؟!
متشکرم |
حل پازل 8
3(ها)ضميمه
حالت اولیه (شروع):
http://artificial.ir/intelligence/at...1&d=1291669865 حالت هدف: http://artificial.ir/intelligence/at...1&d=1291669865 فرض کنید که حالت فعلی به این شکله: http://artificial.ir/intelligence/at...1&d=1291669865 حالا می ریم سر محاسبه f در این حالت فعلی (برای هر حالت یک f محاسبه می شه که جمع g و h هست) با چند حرکت از حالت اولیه به حالت جاری رسیدیم؟ (این رو نمی شه یهو واسه یه حالت حساب کرد. بلکه باید به تدریج که مراحل رو جلو میاید، یکی یکی حساب کنید و در حافظه نگهداری کنید. اما در این مثال چون ساده است، می شه فهمید که با چند حرکت از حالت اولیه به اینجا رسیدیم.) g=4 بعد از اون می ریم سراغ محاسبه h که هیورستیک یا تابع اکتشافی است.تخمیی که به کار می خوایم ببریم فاصله منهتنه. یعنی هر خانه، نسبت به جایی که باید باشه چند خونه اختلاف داره. به عبارت بهتر با چند حرکت می تونیم ببریم بذاریم اش سر جاش، اگر هیچ عدد دیگه ای در بازی نباشه و راه کاملا هموار باشه. برای تک تک خانه ها (هر 8 تا) باید حساب کنیم و آخرش با هم جمع بزنیم. h= فاصله منهتن خانه شماره 1 + فاصله منهتن خانه شماره 2 + فاصله منهتن خانه شماره 3 + فاصله منهتن خانه شماره 4 + ... پس خواهیم داشت: h=2+2+0+0+0+1+1+1=7 خوب حالا مقدار تابع ارزیابی f برای حالت جاری محاسبه شد:f=g+h=4+7=11 اگر مقدار f رو برای حالت های دیگه حساب کردیم و کمترین شون این مقدار (یعنی 11) بود، باید حالت های دیگه رو بی خیال شیم و حالت جاری رو بسط بدیم.امیدوارم متوجه شده باشید. |
متشکرم دوست عریز
من تونستم مثال بالا با روشی که گفتین حل کنم ولی در یک مثال دیگه که f برابر دارند نمیدونم باید چیکار کنم ! نقل قول:
حالت شروع : 54b 618 732 حالت هدف : 123 456 78b در اولین مرحله 2 گره زیر ایجاد میشه که f هر دو برابر 18 هست 548 61b 732 --------------- 5b4 618 732 حالا اگه طبق گفته شما بخواهیم سمت چپ ترین گره انتخاب کنیم کدوم یک باید انتخاب بشه ؟ چون هر دو میشه به عنوان گره چپ در نظر گرفت متشکرم |
شما باید مفاهیم هوش مصنوعی رو پله پله یاد بگیرید
من فرض کردم شما فصل جستجوهای ناآگاهانه (اول سطح، اول عرض، هزینه یکنواخت ...) رو بلد هستید. درصورتیکه با نقشه رومانی سروکار داشته باشید، اولین سمت چپ ترین گره، شهری است که روی نقشه در سمت چپ آراد قرار داشته باشه به لحاظ جغرافیایی. درمورد پازل 8، این به شیوه بسط شما بستگی داره. مهم اینه که شما یه شیوه استاندارد بسط داشته باشید. مثلا اگر خانه های مجاور یک مربع خالی (b) حداکثر چهار خانه هستند، شما با خودتون قرارداد کنید همیشه کوچکترین خانه رو با با خانه خالی جابجا کنید. یا اینکه در جهت عقربه های ساعت از ساعت 12 شروع کنید و بعد ساعت 3 و بعدش 6 و بعدش ساعت 9 رو . تنها چیز که مهمه، رعایت یک استاندارد در بسط دادن هست. چن در نهایت الگوریتم *A راه حل بهینه رو خواهد یافت. پس کافیه شیوه کار شما ثابت باشه تا اگر شخص دیگه ای خواست مراحل شما رو دنبال کنه بتونه این کار رو انجام بده. در مورد مثالی که زدید مثلا اگر با استاندارد بسط از ساعت 12 شروع کنیم، ابتدا حالت دوم رخ می ده، یعنی اول خانه شماره 8 و بعدش خانه شماره 4 می تونه بسط داده شه (به عنوان فرزندان حالت جاری) موفق باشید |
با سلام خدمت دوستان اگه ميشه الگوريتم *a رو براي پازل خوب تشريح كنيد من اينطوري متوجه نشدم اصلا f,g چيه فقط يك مرحله ش حتي بنويسيد هم متوجه ميشم فقط زود باشه فداتون يا علي
|
سلام
كسي برنامه آراد به بخارست را به الگوريتم *a نداره؟ ممنون ميشم كمك كنيد. |
2(ها)ضميمه
سلام خدمت دوستان عزیز
من میخوام پازل 8 رو به روش A* حل کنم . یه کدی هم (گرچه خیلی مبتدیا) با زبون vb.net نوشتم . اما جواب نمیگیرم . نمیدونم کلا الگوریتم رو اشتباه متوجه شدم یا اینکه کد هام مشکل دارن . میخوام اگر امکانش هست شما اساتید یه نگاهی بهش بندازید. و یه مورد دیگه اینکه اول با تابع بازگشتی خواستم بنویسم اما خیلی زود به استک اورفلو میرسیدم این بود که که فعلا توی یه حلقه گزاشتم و نود های گذشته رو نگه نمیدارم. کد رو ضمیمه کردم |
| زمان محلي شما با تنظيم GMT +3.5 هم اکنون ۰۸:۴۹ قبل از ظهر ميباشد. |
Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
Search Engine Friendly URLs by vBSEO 3.1.0 ©2007, Crawlability, Inc.