پازل N

[فاطـمه]

سلام
من متاسفانه کامپایلر ندارم
اگه خطا نداره که هیچی
ولی اگه جواب نمی ده عجیب نیست
چون پازل های N-PUZZLE همیشه به دو فضای حالت قابل حل و غیر قابل حل تقسیم می شوند. یعنی برای نصف حالت ها «به هیچ وجه» نمیشه به حالت هدف رسید.

همچنین برای اون نصفی که میشه رسید، عمق درخت جستجو می تونه تا 24 (یعنی 24 حرکت) برسه. که فضای جستجو به صورت نمایی زیاد می شه . یعنی اگر هر حالت فقط دو حالت همسایه داشته باشد (که اینطور نیست و بعضی ها سه یا چهار حالت همسایه دارند)، 2 به توان 24 می شود خیلی!!! یعنی اصلاً شما برای اینکار هم حافظه و هم قدرت پردازش کم می آورید.
در نتیجه bfs «در تئوری» برای همه حالات «قابل حل» جواب به دست می آورد ولی «در عمل» برای تعداد خیلی محدودی از اون نصف حالات قابل حل می تونه کار کنه. مثلاً برای اونایی که عمقشون 6-7 باشه (6-7 حرکت لازم داشته باشن تا برسن به حالت هدف).

برای همینه که از روش های هوشمند مثل A* استفاده می شه. چون این روش ها فضای جستجو رو به میزان بسیار زیادی محدود می کنند و در نتیجه سرعت جستجو خیلی خیلی بالاتر می ره (البته A* مشکل حافظه داره و نه قدرت پردازش). یعنی بعد از مدتی حافظه رو پر می کنه. البته توی کتاب هوش مصنوعی راسل روش هایی برای حل این مشکل ارائه شده مثل ids و ...

از پیگیری تون ممنون
اینایی که می گین درست
ولی من به کد خودم اطمینان ندارم
ببینید من تابع dfs رو این جوری نوشتم:

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

استفاده بازگشتی به این صورت درسته؟
با توجه به اینکه برنامه رو توی c++ نوشتم
واسه اجراش خیلی محدودیت حافظه دارم
فک کنم مجبور شم تبدیل به c# کنم
اجرا که بیشتر از 1000 میشه سیستم هنگ میکنه واسه همین اون sw رو گذاشتم

[hamidreza_buddy]

اگه توی توربو سی پلاس پلاس نوشتین شاید حافظه کم بیاره ولی توی vc++ 6 کامپایلش کنین مشکلی از نظر حافظه نخواهد داشت و نسبت به سی شارپ هم سریع تر خواهد بود!

حقیقتش من متوجه استفاده شما هز int a و متغییر path نشدم.

فکر می کنم دارید سعی می کنید که مسیر رو ذخیره کنید.

بهرته برای ذخیره مسیر هر وقت به حالت هدف رسیدید مثلاً 1 رو برگردونید و همین طور rewind کنید به بالا و اون حرکت رو ذخیره کنید.

به نظر من به جای dfs ، سعی کنید ids رو پیاده سازی کنید. چون dfs همین طور الکی پایین میره و احتمال به جواب رسیدنش خیلی کمه!

یعنی به جای متغییر سراسری sw، از یک متغییر به نام depth استفاده کنین که عمق رو حساب کنه و مثلاً اگه به عمق 25 رسید برگرده.

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

وباید از مکان اولیه خونه خالی شروع کنی:

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

البته من تصور می کنم که شما یک متغییر سراسری دارید که آرایه دو بعدیه توش جدول ذخیره شده.

همچنین جدول تستو یه جدول با راه حله کوچیک (تو مایه های 2-3) بده ببین الگوریتم حلش می کنه. و کم کم حرکت اضافش کن ببین که چقدر طول می کشه که حل بشه. مثلاً فک کنم تا 7-8 حرکت رو بیشتر نکشه.

[فاطـمه]

حقیقتش من متوجه استفاده شما هز int a و متغییر path نشدم.

فکر می کنم دارید سعی می کنید که مسیر رو ذخیره کنید.

بله از path برای ذخیره مسیر و از a برای نگهداری عمق استفاده کردم

به نظر من به جای dfs ، سعی کنید ids رو پیاده سازی کنید. چون dfs همین طور الکی پایین میره و احتمال به جواب رسیدنش خیلی کمه!

من باید به هر 4 الگوریتم dfs,bfs,a*,idf این برنامه رو بنویسم

به نظر من به جای dfs ، سعی کنید ids رو پیاده سازی کنید. چون dfs همین طور الکی پایین میره و احتمال به جواب رسیدنش خیلی کمه!

یعنی به جای متغییر سراسری sw، از یک متغییر به نام depth استفاده کنین که عمق رو حساب کنه و مثلاً اگه به عمق 25 رسید برگرده.

خب همین برگردون رو چه جوری انجام بدم
از روی path?!
---------
کدتون جالبه

[فاطـمه]

ببینید من ساختار ها رو این جوری تعریف کردم

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

[hamidreza_buddy]

ببینید به کدی که من نوشتم دقیت کنید. هر وقت به جایی رسید که Goal باشه، 1 رو برمی گردونه. اینجوری همینجور مستقیم تا بالا می ره و می شه همه حرکات رو به یه لیست اضافه کرد.

اگه a داره عمق رو حساب می کنه ، باید

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

همه

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

باشه.

همچنین به جای swap تو کد من دقت کنید.

همچنین به این دلیل گفتم ids رو اول پیاده سازی کنید این بود که بتونید الگوریتم رو امتحان کنید و نتایج رو ببینید که الگوریتم درسته یا نه.
و بعد از اون محدودیت عمق رو حذف کنید تا بشه dfs!
چون با dfs به نتیجه نمی رسه و نمی تونین متوجه شین که الگوریتم رو درست پیاده سازی کردین یا نه!

[فاطـمه]

از توضیحاتتون بازم ممنون به نکات ظریفی اشاره کردین که بهشون دقت نکرده بودم
الان امتحانش می کنم

[فاطـمه]

سلام کد dfs رو اصلاح کردم حالا دارم bfs رو می نویسم
ممکنه یه شبه کد واسه bfs هم مشابه اونی که واسه dfs گذاشتین بذارین

[hamidreza_buddy]

برای پیاده سازی BFS باید یه صف queue داشته باشید:
شبه کد کلیش. باید یه ساختمان داده صف و یا لیست پیوندی داشته باشید:

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

[عــــلی]

من باید به هر 4 الگوریتم dfs,bfs,a*,idf این برنامه رو بنویسم

سلام خسته نباشید میشه لطفاً بگید این dfs,bfs,a*,idf چی هستن؟
و اینکه با چه زبانی این پروژه رو میخواین؟ممنون.

[فاطـمه]

سلام دوست
هر 4 تاش رو نوشتم البته با c++ ، البته با راهنمایی دوستان
bfs : جست و جوی اول سطح
dfs: اول عمق
ids: اول عمق با عمق محدود
a* : هوشمند