PDA

View Full Version : سوال: معمای 8 به روش A استار



oasis051
یک شنبه 27 اردیبهشت 1388, 19:02 عصر
سلام به همه دوستان برنامه نویس.

من یه کمی توضیح راجع به برنامه معمای 8 می خوام حالا به هر روشی که شد(اگه A استار باشه بهتر)

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

پیشاپیش ممنون.

qwerty11
دوشنبه 15 تیر 1388, 10:35 صبح
خوب اگه serach ميكردي بحث هاي زيادي درباره ي eight puzzle انجام شده بود !!!
اما به هر حال، براي حل eight puzzle راه هاي مختلفي از جمله جستجوي اول عمق و جستجوي اول سطح و A استار و ... وجود داره كه البته از بين همه ي اينا A استار سرعتش از بقيه بيشتره چون واسه رسيدن به جواب گره هاي كمتري توليد ميكنه !!!

واسه به دست آوردن جواب به روش اول سطح يا همون bfs به يه map يا hashTable احتياج داري كه بتوني search كردن يه گره رو با (1)O انجام بدي !! تو هر مرحله هم همه ي حركت هاي چپ و راست و بالا و پايين رو چك ميكني و اگه اين گره جديد تو map يا hashTable وجود نداشت به map و صف اضافش ميكني. احتياجي به گفتن نيست كه وقتي صحبت از جستجوي اول سطح ميسه به يه صف احتياج داري ...

و اما در مورد روش A استار بايد توجه كني كه به جاي داشتن صف اين بار بايد از يه صف اولويت استفاده كني (PriorityQueue). صف اولويت اين خاصيت رو داره كه اضافه كردن يه گره به اون پيچيدگي log n رو داره و اين كيتونه به سرعت بخشيدن به برنامه كمك كنه. و اما ملاك ترتيب قرار گرفتن گره ها تو صف اولويت چيه ؟؟ ملاك قرار گرفتن گره ها تو صف اولويت "فاصله ي منهتنشون از حالت نهايي + عمقي كه به گره رسيديم" هستش. كه براي پياده سازي اين هم تنها نياز داري كه فاصله ي منهتن 2 تا حالت از هم رو بدست بياره كه اين كار به راحتي انجام ميگيره ...

ashegh_h
جمعه 31 اردیبهشت 1389, 13:42 عصر
كسي مي تونه كمكم كنه اگه كسي هست تو را خدا كمك كنيد
برنامه جستجوي عرضي و آ استار

whitehat
شنبه 01 خرداد 1389, 10:34 صبح
قبلا پرسیده شده ... جستجو کنید