حل مسئله Maze با استفاده از A* - A star

[Mah]

با سلام خدمت همه دوستان .
من برای حل مسئله Maze با این الگوریتم مشکل دارم .
قبلاً در این وب و سایر منابع نیز جستجو نمودم . اما توضیحات قابل توجهی پیدا نکردم . لطفا یکی از دوستان راهنمایی جامعی انجام دهد .

ضمنا من برای پیاده سازی از دلفی استفاده می نمایم .
امیدوارم بتوانید مرا راهنمایی کنید .

[Mah]

دوستان من همچنان منتظرم .
........................................
........................................
........................................

[pvza85]

سلام
اولا مشکلت رو نگفتی
دوما نگفتی چه قدر کار کردی یعنی مشکلت پایه ای هست یا پیادش کردی و مشکل برخورد کردی( فکر کنم این همون اولا بود، سخت نگیر)

با فرض اینکه هیچ کاری نکردی و کلیات A-star رو می دونی به طور بسیار خلاصه:
سخت ترین کار تو حل Maze پیدا کردن هیوریستیک هستش یعنی اینکه بدونی چقدر به مقصد رسیدی. در واقع مهمترین خصوصیت Maze همینه که نمی دونی چقدر نزدیکی. تنها چیزی که به ذهن ناقص من میرسه فاصلت بدون در نظر گرفتن دیوارها تا مقصد هستش که این تفکر احمقانه branching factor بسیار گنده ای رو نتیجه می ده که یعنی یه ابر کامپیوتر با کلی حافظه (مثلا 1TB ) لازم داری پس اینجا باید خلاقیت به خرج بدی و از روش های دیگه هم استفاده کنی مثل یه حرکت دو طرفه و مسلما یه هرس حسابی. برا هرس من پیشنهاد می کنم به همه گره شاخص بده و یه تابع jumb back (یه چیزی شبیه backtracking ) طراحی کن و وقتی به یه بن بست رسیدی تمام تقاطع های مسیرهای انحصاری اون بن بست رو از حافظه حذف کن و ...

ببین همه اینایی که گفتم مثل گفتنش راحت نیستا

ولی میرسیم به قسمت خوشمزش. این پروژه رو واسه چی می خوایی؟ چقدر واست مهمه؟ اگه یه پروژس که می خوایی از سرت بازش کنی به قدرت )brute force) کامپیوترت اعتماد کن و تو طراحی Maze احتیاط کن همش حل میشه احتیاج به هرس و سایر قرطی بازی ها نداری

[nasrin_yalda]

سلام
چه حل های برای maze ارائه شده است؟

[qwerty11]

با فرض اینکه هیچ کاری نکردی و کلیات A-star رو می دونی به طور بسیار خلاصه:
سخت ترین کار تو حل Maze پیدا کردن هیوریستیک هستش یعنی اینکه بدونی چقدر به مقصد رسیدی. در واقع مهمترین خصوصیت Maze همینه که نمی دونی چقدر نزدیکی. تنها چیزی که به ذهن ناقص من میرسه فاصلت بدون در نظر گرفتن دیوارها تا مقصد هستش که این تفکر احمقانه branching factor بسیار گنده ای رو نتیجه می ده که یعنی یه ابر کامپیوتر با کلی حافظه (مثلا 1TB ) لازم داری پس اینجا باید خلاقیت به خرج بدی و از روش های دیگه هم استفاده کنی مثل یه حرکت دو طرفه و مسلما یه هرس حسابی. برا هرس من پیشنهاد می کنم به همه گره شاخص بده و یه تابع jumb back (یه چیزی شبیه backtracking ) طراحی کن و وقتی به یه بن بست رسیدی تمام تقاطع های مسیرهای انحصاری اون بن بست رو از حافظه حذف کن و ...

سلام دوست عزیز، ممنون جواب قشنگی دادی به سوالشون. اما من اون قسمت بولد شده رو متوجه نشدم، چرا به یه ابر کامپیوتر نیاز داریم !؟ من فکر میکنم با کامپیوتر خودم و اون هیوریستیکی که شما گفتین میتونم مسئله رو به جواب برسونم.... در هر صورت منظورتونو متوجه نشدم.

خوب جواب من به این سوال : من تابع هیوریستیکم رو واسه یه state اینجوری در نظر میگیرم : طول مسیری که به گره رسیدیم + فاصله ی گره از مقصد (که در واقع همون فاصله ی منهتنشونه)