پازل N

واضح آرشیو وب فارسی:سایت ریسک: View Full Version : پازل N فاطـمه23-05-2009, 10:31 AMسلام بچه ها من باید برنامه پازل n رو با الگوریتمهای مختلف بنویسم(bfs,dfs,a*,idf,...) ولی مشکلم اینجاست که اصلا نمی دونم چه استراتژی برای جست و جو داشته باشم مثلا برای مسئله nqueen در حالت افزایشی یکی یکی q ها رو اضافه می کردیم ، تو هر سطر یکی می ذاشتیم و تو حالتای ضربدری چک می کردیم ولی این رو نمی دونم چه جوری حل کنم اگر راهنمایی کنید ممنون میشم واسه دوستانی که ممکنه ندونند npuzzle چیه توضیح می دم این قسمت رو: یه پازل داریم با N تا خونه مثلا تو حالت n=9 یه پازل 3*3 داریم تو خونه ها اعداد 1و8 رو به صورت نا مرتب داریم و یه خونه خالی که این برنامه باید خودش خونه ها رو مرتب کنه و ترتیب اعمالی رو که انجام داده بده:41: ali.sholug23-05-2009, 11:38 AMسلام ببین اینجوری میشه؟ پازل رو یه ماتریس در نظر بگیر تمام سطر هارو مرتب کن بعد تمام ستونهارو مرتب کن عنصر آخر هر سطر رو با عنصر اول سطر بعدی مقایسه کن اگه کوچیک بود سطر بالایی مرتب شده اگه نه جای این عنصر ها رو عوض کن اه واسه همه سطر ها شرط بالا درست بود ماتریست مرتبه ای کارو واسه سطر های پایین هم انجام بده بعد دوباره تمام سطر هارو مرتب کن و تمام ستونهارو مرتب کن ali.sholug23-05-2009, 11:41 AMیا اینکه میتونی از اول هر عدد رو برداری ببری سر جاش بذاری وقتی به n/2 +1 عضو رسیدی ماتریست مرتبه امتاحانش کن هر دو روشو موفق باشی فاطـمه23-05-2009, 11:44 AMنه دیگه اینا نمیشه اگه این بازی رو انجام داده باشی می بینی که با توجه به خونه خالی حرکاتی که می تونی انجام بدی خیلی محدوده یعنی همیشه بین 2-4 حرکت فقط وجود داره واسه انتخاب بچه ها خیلی فوریه لطفا کمک hamidreza_buddy23-05-2009, 07:15 PMاینارو واسه 8puzzle توضیح می دهم. ببین شما state فعلیت یه حالت رندومه. اگه خونه وسطی خالی باشه، چهار تا حرکت می تونید انجام بدید. http://i42.tinypic.com/2duz7o8.jpg اگه مثلاً خونه پایین سمت راست خالی باشه دو حرکت قابل انجامه. http://i41.tinypic.com/jiyv7m.jpg پس شما به یک تابع نیاز دارید که بتونه حالت های بعدی حالت فعلی رو به دست بیاره. اسم این تابع رو می گذاریم succ (مخفف successor یا بعدی) این تابع اینجوری اجرا میشه که حالت فعلی و می گیری و حالت بعدی رو می ده (این تابع توی همه این الگوریتم هایی که شما قصد پیاده سازیش رو دارید مشترکه) !!!! برای مشاهده محتوا ، لطفا ثبت نام کنید / وارد شوید !!!! البته ساختمان داده State چیزی نیست جز یه آرایه دو بعدی (یا حتی یک بعدی) خوب! حالا که اینو داریم ما می آیم و استراتژی های جستجو رو که توی کتاب هوش مصنوعی هست و می نویسیم. مثلاً واسه A* باید از یک تابع heuristic استفاده کنیم (فاصله منهتن یا فاصله قطری ...) این تابع یه همچین شکلی داره: !!!! برای مشاهده محتوا ، لطفا ثبت نام کنید / وارد شوید !!!! خوب! حالا تابعای اصلی رو داری. می آی از حالت اولیه شروع می کنی و همه همسایه هاشو بوسیله Succ به دست می آری. بعدش می آی و روی اون همسایه ها تابع Heuristic رو اجرا می کنی و واسه هر کدوم یه امتیاز به دست می آری. حالا از بین حالات همسایه هر کدوم که امتیاز بهتری رو داره (توی A* باید امتیاز Heuristic رو با path طی شده جمع کرد) رو انتخاب و دوباره همون کار بالا رو روش انجام می دی. در نتیجه این جستجوی A* یه جورایی هوشمند هست (البته نه خیلی) bfs و dfs هم که هیچی! فقط همسایه هارو با Succ تولید می کنی و اونا رو با یه ترتیبی (بسته به اینکه سطح اولند یا عمق اول) پیمایش می کنی. پیمایش هم یعنی اینکه Succ رو رو این حالات همسایه به دست آمده اجرا می کنیم و بررسی مکی کنیم که آیا به حالت هدف رسیده ایم؟ یعنی به حالت زیر: http://www.8puzzle.com/images/8_puzzle_goal_state_b.png هر وقت هم به حالت هدف رسیدید، درخت جستجو را تا بالا پیمایسش می کنید تا ترتیب حرکت ها رو به دست بیاری. همین! idf هم که همون dfs هست که اونو محدود می کنیم به یه عمق خاص (تا اونجایی که یادم باشه)! DaneshD24-05-2009, 03:02 AMخیلی ساده هست. حتما میتونی تو زمان کمی انجام بدی. این دوستمون hamidreza_buddy هم توضیحات بالارو از این سایت آورده و البته به خوبی توضیح داده: !!!! برای مشاهده محتوا ، لطفا ثبت نام کنید / وارد شوید !!!! که الگوریتمش هم اونجاست. سورس کدش هم رو اینترنت هست که البته ندونی کجاست بهتره تا خودت انجام بدی و یه چیزی یاد بگیری. راهنمایی: مساله رو به Maze تبدیل کن. Maze همون بازی بود که از یک نقطه به یک نقطه دیگه باید بری تو یک مسیر مارپیچ. خونه خالی رو فرض کن که باید تکون بدی تا برسه به مرکز که اطرافش خونه های مرتب شده puzzle هست. برای ثبت حرکات هم از یک counter استفاده کن. طول counter هم برابر با 2 به توان n هست که n تعداد خونه های puzzle هست که میشه 9 برای یک puzzle با سایز 3x3. هر بار که counter یکی میره بالا در واقع یک حرکت جدید رو امتحان کردی. تقریبا حل شد! فاطـمه24-05-2009, 09:42 AMسلام دوست من ،( اول از همه از اینکه وقت گذاشتین خیلی ممنون) خب اینا همه درست ولی مشکل من اینجاست که مثلا تو حالت bfs که باید جست و جوی اول سطح داشته باشیم چه جوری درخت رو تشکیل بدیم؟ مثلا سطح اول (با فرض وسط بودن خونه خالی) یه بار به راست ، یه بار به چپ، یه بار به پایین و یه بار به بالا می ریم خب تو سطح دو چکار کنیم؟ اونی که سطح اول به راست رفته از کجا بفهمیم که سطح دوم کدوم طرفی حرکت کنه؟ این کار رو باید رندوم انجام بدیم؟ اگر فرضا واسه حالتای bfs و dfs این کار رو رندوم انجام بدیم تو حالت a* که حالت آگاهانه رو داریم باید چکار کنیم؟! hamidreza_buddy24-05-2009, 10:38 PMببینید درخت جستجو تقریباً یه چیزه مجازیه! یعنی شما واقعاً یه درخت نمی سازید بلکه با فراخوانی های بازگشتی برنامه شما حالت یک درخت می گیره. مثلاً شما یه تابع به اسم Solve می نویسی که ورودیش یه حالته. سپس توی مثلاً bfs دوباره اون رو روی همسایه های اجرا می کنی که در نتیجه یه درخت حالت به وجود می آد: شبه کد: !!!! برای مشاهده محتوا ، لطفا ثبت نام کنید / وارد شوید !!!! یا مثلاً DFS: !!!! برای مشاهده محتوا ، لطفا ثبت نام کنید / وارد شوید !!!! یا مثلاً A*: !!!! برای مشاهده محتوا ، لطفا ثبت نام کنید / وارد شوید !!!! می بینید که ساختمان داده درخت نداریم ولی فراخوانی بازگشتی توابع به صورت درخت است. فاطـمه25-05-2009, 03:55 PMببینید درخت جستجو تقریباً یه چیزه مجازیه! یعنی شما واقعاً یه درخت نمی سازید بلکه با فراخوانی های بازگشتی برنامه شما حالت یک درخت می گیره. مثلاً شما یه تابع به اسم Solve می نویسی که ورودیش یه حالته. سپس توی مثلاً bfs دوباره اون رو روی همسایه های اجرا می کنی که در نتیجه یه درخت حالت به وجود می آد: شبه کد: !!!! برای مشاهده محتوا ، لطفا ثبت نام کنید / وارد شوید !!!! یا مثلاً DFS: !!!! برای مشاهده محتوا ، لطفا ثبت نام کنید / وارد شوید !!!! یا مثلاً A*: !!!! برای مشاهده محتوا ، لطفا ثبت نام کنید / وارد شوید !!!! می بینید که ساختمان داده درخت نداریم ولی فراخوانی بازگشتی توابع به صورت درخت است. سلام دوست من از راهنمایی تون واقعا ممنون من برنامه bfs رو نوشتم خطا نداره ، بعضی اوقاتم جواب می ده ولی به نظر خودم کاملا درست کار نمی کنه اگه ممکنه یه نگا بندازین:20: !!!! برای مشاهده محتوا ، لطفا ثبت نام کنید / وارد شوید !!!! hamidreza_buddy25-05-2009, 05:08 PMسلام من متاسفانه کامپایلر ندارم اگه خطا نداره که هیچی ولی اگه جواب نمی ده عجیب نیست چون پازل های N-PUZZLE همیشه به دو فضای حالت قابل حل و غیر قابل حل تقسیم می شوند. یعنی برای نصف حالت ها «به هیچ وجه» نمیشه به حالت هدف رسید. همچنین برای اون نصفی که میشه رسید، عمق درخت جستجو می تونه تا 24 (یعنی 24 حرکت) برسه. که فضای جستجو به صورت نمایی زیاد می شه . یعنی اگر هر حالت فقط دو حالت همسایه داشته باشد (که اینطور نیست و بعضی ها سه یا چهار حالت همسایه دارند)، 2 به توان 24 می شود خیلی!!! یعنی اصلاً شما برای اینکار هم حافظه و هم قدرت پردازش کم می آورید. در نتیجه bfs «در تئوری» برای همه حالات «قابل حل» جواب به دست می آورد ولی «در عمل» برای تعداد خیلی محدودی از اون نصف حالات قابل حل می تونه کار کنه. مثلاً برای اونایی که عمقشون 6-7 باشه (6-7 حرکت لازم داشته باشن تا برسن به حالت هدف). برای همینه که از روش های هوشمند مثل A* استفاده می شه. چون این روش ها فضای جستجو رو به میزان بسیار زیادی محدود می کنند و در نتیجه سرعت جستجو خیلی خیلی بالاتر می ره (البته A* مشکل حافظه داره و نه قدرت پردازش). یعنی بعد از مدتی حافظه رو پر می کنه. البته توی کتاب هوش مصنوعی راسل روش هایی برای حل این مشکل ارائه شده مثل ids و ... فاطـمه25-05-2009, 05:58 PMسلام من متاسفانه کامپایلر ندارم اگه خطا نداره که هیچی ولی اگه جواب نمی ده عجیب نیست چون پازل های N-PUZZLE همیشه به دو فضای حالت قابل حل و غیر قابل حل تقسیم می شوند. یعنی برای نصف حالت ها «به هیچ وجه» نمیشه به حالت هدف رسید. همچنین برای اون نصفی که میشه رسید، عمق درخت جستجو می تونه تا 24 (یعنی 24 حرکت) برسه. که فضای جستجو به صورت نمایی زیاد می شه . یعنی اگر هر حالت فقط دو حالت همسایه داشته باشد (که اینطور نیست و بعضی ها سه یا چهار حالت همسایه دارند)، 2 به توان 24 می شود خیلی!!! یعنی اصلاً شما برای اینکار هم حافظه و هم قدرت پردازش کم می آورید. در نتیجه bfs «در تئوری» برای همه حالات «قابل حل» جواب به دست می آورد ولی «در عمل» برای تعداد خیلی محدودی از اون نصف حالات قابل حل می تونه کار کنه. مثلاً برای اونایی که عمقشون 6-7 باشه (6-7 حرکت لازم داشته باشن تا برسن به حالت هدف). برای همینه که از روش های هوشمند مثل A* استفاده می شه. چون این روش ها فضای جستجو رو به میزان بسیار زیادی محدود می کنند و در نتیجه سرعت جستجو خیلی خیلی بالاتر می ره (البته A* مشکل حافظه داره و نه قدرت پردازش). یعنی بعد از مدتی حافظه رو پر می کنه. البته توی کتاب هوش مصنوعی راسل روش هایی برای حل این مشکل ارائه شده مثل ids و ... از پیگیری تون ممنون اینایی که می گین درست ولی من به کد خودم اطمینان ندارم ببینید من تابع dfs رو این جوری نوشتم: !!!! برای مشاهده محتوا ، لطفا ثبت نام کنید / وارد شوید !!!! استفاده بازگشتی به این صورت درسته؟ با توجه به اینکه برنامه رو توی c++ نوشتم واسه اجراش خیلی محدودیت حافظه دارم فک کنم مجبور شم تبدیل به c# کنم اجرا که بیشتر از 1000 میشه سیستم هنگ میکنه واسه همین اون sw رو گذاشتم hamidreza_buddy25-05-2009, 06:33 PMاگه توی توربو سی پلاس پلاس نوشتین شاید حافظه کم بیاره ولی توی vc++ 6 کامپایلش کنین مشکلی از نظر حافظه نخواهد داشت و نسبت به سی شارپ هم سریع تر خواهد بود! حقیقتش من متوجه استفاده شما هز int a و متغییر path نشدم. فکر می کنم دارید سعی می کنید که مسیر رو ذخیره کنید. بهرته برای ذخیره مسیر هر وقت به حالت هدف رسیدید مثلاً 1 رو برگردونید و همین طور rewind کنید به بالا و اون حرکت رو ذخیره کنید. به نظر من به جای dfs ، سعی کنید ids رو پیاده سازی کنید. چون dfs همین طور الکی پایین میره و احتمال به جواب رسیدنش خیلی کمه! یعنی به جای متغییر سراسری sw، از یک متغییر به نام depth استفاده کنین که عمق رو حساب کنه و مثلاً اگه به عمق 25 رسید برگرده. !!!! برای مشاهده محتوا ، لطفا ثبت نام کنید / وارد شوید !!!! وباید از مکان اولیه خونه خالی شروع کنی: !!!! برای مشاهده محتوا ، لطفا ثبت نام کنید / وارد شوید !!!! البته من تصور می کنم که شما یک متغییر سراسری دارید که آرایه دو بعدیه توش جدول ذخیره شده. همچنین جدول تستو یه جدول با راه حله کوچیک (تو مایه های 2-3) بده ببین الگوریتم حلش می کنه. و کم کم حرکت اضافش کن ببین که چقدر طول می کشه که حل بشه. مثلاً فک کنم تا 7-8 حرکت رو بیشتر نکشه. فاطـمه25-05-2009, 06:42 PMحقیقتش من متوجه استفاده شما هز int a و متغییر path نشدم. فکر می کنم دارید سعی می کنید که مسیر رو ذخیره کنید. بله از path برای ذخیره مسیر و از a برای نگهداری عمق استفاده کردم به نظر من به جای dfs ، سعی کنید ids رو پیاده سازی کنید. چون dfs همین طور الکی پایین میره و احتمال به جواب رسیدنش خیلی کمه! من باید به هر 4 الگوریتم dfs,bfs,a*,idf این برنامه رو بنویسم به نظر من به جای dfs ، سعی کنید ids رو پیاده سازی کنید. چون dfs همین طور الکی پایین میره و احتمال به جواب رسیدنش خیلی کمه! یعنی به جای متغییر سراسری sw، از یک متغییر به نام depth استفاده کنین که عمق رو حساب کنه و مثلاً اگه به عمق 25 رسید برگرده. خب همین برگردون رو چه جوری انجام بدم از روی path?! --------- کدتون جالبه فاطـمه25-05-2009, 06:48 PMببینید من ساختار ها رو این جوری تعریف کردم !!!! برای مشاهده محتوا ، لطفا ثبت نام کنید / وارد شوید !!!! hamidreza_buddy25-05-2009, 07:01 PMببینید به کدی که من نوشتم دقیت کنید. هر وقت به جایی رسید که Goal باشه، 1 رو برمی گردونه. اینجوری همینجور مستقیم تا بالا می ره و می شه همه حرکات رو به یه لیست اضافه کرد. اگه a داره عمق رو حساب می کنه ، باید !!!! برای مشاهده محتوا ، لطفا ثبت نام کنید / وارد شوید !!!! همه !!!! برای مشاهده محتوا ، لطفا ثبت نام کنید / وارد شوید !!!! باشه. همچنین به جای swap تو کد من دقت کنید. همچنین به این دلیل گفتم ids رو اول پیاده سازی کنید این بود که بتونید الگوریتم رو امتحان کنید و نتایج رو ببینید که الگوریتم درسته یا نه. و بعد از اون محدودیت عمق رو حذف کنید تا بشه dfs! چون با dfs به نتیجه نمی رسه و نمی تونین متوجه شین که الگوریتم رو درست پیاده سازی کردین یا نه! فاطـمه26-05-2009, 12:03 PMاز توضیحاتتون بازم ممنون به نکات ظریفی اشاره کردین که بهشون دقت نکرده بودم الان امتحانش می کنم فاطـمه27-05-2009, 07:42 AMسلام کد dfs رو اصلاح کردم حالا دارم bfs رو می نویسم ممکنه یه شبه کد واسه bfs هم مشابه اونی که واسه dfs گذاشتین بذارین hamidreza_buddy27-05-2009, 04:50 PMبرای پیاده سازی BFS باید یه صف queue داشته باشید: شبه کد کلیش. باید یه ساختمان داده صف و یا لیست پیوندی داشته باشید: !!!! برای مشاهده محتوا ، لطفا ثبت نام کنید / وارد شوید !!!! hamishebahar01-06-2009, 12:48 PMمن باید به هر 4 الگوریتم dfs,bfs,a*,idf این برنامه رو بنویسم سلام خسته نباشید میشه لطفاً بگید این dfs,bfs,a*,idf چی هستن؟ و اینکه با چه زبانی این پروژه رو میخواین؟ممنون. فاطـمه01-06-2009, 12:56 PMسلام دوست هر 4 تاش رو نوشتم البته با c++ ، البته با راهنمایی دوستان bfs : جست و جوی اول سطح dfs: اول عمق ids: اول عمق با عمق محدود a* : هوشمند hamishebahar01-06-2009, 02:23 PMسلام دوست هر 4 تاش رو نوشتم البته با c++ ، البته با راهنمایی دوستان bfs : جست و جوی اول سطح dfs: اول عمق ids: اول عمق با عمق محدود a* : هوشمند سلام ممنون ولی من یه خوردهشو خوب متوجه نشدم با عرض معذرت آخه نمیدونم:31:.من این پروژه رو واستون نوشتم به سه زبان نت امیدوارم به دردتون بخوره(ببخشید که دیر رسیدم دیگه):5:: http://hamishebaharp30world.persiangig.ir/Puzzle%20hamishebahar%28forum.p30world.com%29.JPG http://hamishebaharp30world.persiangig.ir/HamisheBahar%28Forum.P30World.Com%29Csharp.jpgسی شارپ(#C) دانلود پروژه: !!!! برای مشاهده محتوا ، لطفا ثبت نام کنید / وارد شوید !!!!http://hamishebaharp30world.persiangig.ir/HamisheBahar%28Forum.P30World.Com%29C++.jpgسی پلاس پلاس(++C) دانلود پروژه: !!!! برای مشاهده محتوا ، لطفا ثبت نام کنید / وارد شوید !!!!http://hamishebaharp30world.persiangig.ir/HamisheBahar%28Forum.P30World.Com%29VB.jpgویژو ال بیسیک(Visual Basic)دانلود پروژه: !!!! برای مشاهده محتوا ، لطفا ثبت نام کنید / وارد شوید !!!!البته کامله اگه برنده هم بشی پیغام میده. فاطـمه01-06-2009, 02:45 PMنه دوست من من برنامه ای می خواستم که خودش پازل رو خودش با اون الگوریتما حل کنه به هر حال از لطف و توجه تون خیلی ممنونم در ضمن برنامه رو نوشتم، بازم ممنون كارمج23-06-2009, 11:21 AMبرنامه پيمايش يك درخت فاطـمه23-06-2009, 04:39 PMبرنامه پيمايش يك درخت برنامه ای که تو این تاپیک هست خودش یه برنامه پیمایش درخته mehdi_hoolakian31-03-2010, 01:01 PMفاطمه خانم میشه برنامتونو بزارین ما هم استفاده کنیم؟ سایت ما را در گوگل محبوب کنید با کلیک روی دکمه ای که در سمت چپ این منو با عنوان +1 قرار داده شده شما به این سایت مهر تأیید میزنید و به دوستانتان در صفحه جستجوی گوگل دیدن این سایت را پیشنهاد میکنید که این امر خود باعث افزایش رتبه سایت در گوگل میشود

این صفحه را در گوگل محبوب کنید

[ارسال شده از: سایت ریسک]

[مشاهده در: www.ri3k.eu]

[تعداد بازديد از اين مطلب: 6365]