معمای هشت یا 8Puzzle

[qwerty11]

با تشکر از Amateur_G
این برنامه ای که نوشتید در واقع Best-First است. برای A* نمیدونید شرط
h>=h* چطور باید اعمال بشه؟
h:هزینه تخمینی ارزانترین مسیر از گره n به گره هدف
h*: ارزانترین مسیر واقعی از گره n به هدف
یعنی اول باید هزینه واقعی رو در بیاریم و شرط رو بر اساس اون بزاریم؟؟؟؟

سلام،
در مورد حل پازل پانزدهتایی من جایی ندیدم که درباره ی جواب بهینش چیزی گفته باشن، اما اگه تو صفحه ی ویکیپدیاش بری یه راه برای حل معما گفتن : تبدیل کردن پازل 15 به پازل 8. به این ترتیب که اول سطر اول و ستون اولش رو میچینی و بعدش مسئله به معمای هشت تبدیل میشه. البته جواب بهینه رو نمیده.

حل معمای هشت با جستجوی اول سطح هم کار آسونیه، فقط کافیه کاری کنی تا وقتی به یه گره تکراری رسیدی بتونی سریع تشخیص بدی و در واقع search رو با (1)O انجام بدی که اگه بتونی هر گره رو یه string در نظر بگیری میتونی اینکار رو با map توی C++‎‎‎ و HashTable توی جاوا انجام بدی.

جستجوی عمیق کننده ی تکراری هم همونطور که از اسمش پیداست باید فقط وقتی DFS میزنی، اگه به عمق محدود مورد نظر رسیدیم دیگه گره رو ادامه ندیم و عمق محدود مورد نظر رو یکی افزایش بدیم تا وقتی که بتونیم تو یه عمقی به جواب برسیم. این روش هم مثل جستجوی اول سطح جواب بهینه رو به ما میده ... h که همون هزینه ی تخمینی هست برابر فاصله ی manhattan گره از goal هستش بعلاوه ی هزینه ای که تا اینجا اومدیم.