Artificial Intelligence - هوش مصنوعی - A-star چیست و چگونه کار میکند؟

Artificial Intelligence - هوش مصنوعی (http://artificial.ir/intelligence/)

- هوش مصنوعی چیست؟ (http://artificial.ir/intelligence/forum36.html)

- - A-star چیست و چگونه کار میکند؟ (http://artificial.ir/intelligence/thread1161.html)

A-star چیست و چگونه کار میکند؟

سلام..
خسته نباشید دوستان.:o

من با اینکه در مورد چگونگی عملکرد A-star مطالعه هم کردم، اما هنوز برام جا افتاده نیست.
مطلبی هنوز ازش توی نت پیدا نکردم، ممنون میشم توضیحش بدید.

قکر می کنم بهترین راه برای درک خوب الگوریتم های جستجو، استفاده کردن از اپلت های جاوا باشه.

مثلا مو تونی عبارت هایی مثل A Star Algorithm Applet رو جستجو کنی.

اگر هم نشد که دقیقا بگو که کجای الگوریتم رو متوجه نمی شی.

موفق باشی.

سلام دوستان.

من یه شبه کد پیدا کردم در مورد حل معمای 8 (پازل 8) با استفاده از روش A-Star.

ولی برام نامفهومه، خوده تعریف a-star رو متوجه شدم، ولی اونطور که باید برام جا افتاده نیست که بتونم این شبه کد رو خوب متوجه بشم.
اگر برام توضیح بدید این شبه کد رو واقعا یک دنیا ممنون میشم، مخصوصا قسمتهای بلد شده.

كد:





function A*(start,goal)

     closedset := the empty set                 % The set of nodes already evaluated.     

     openset := set containing the initial node % The set of tentative nodes to be evaluated.

     g_score[start] := 0                        % Distance from start along optimal path.

     h_score[start] := heuristic_estimate_of_distance(start, goal)

     f_score[start] := h_score[start]           % Estimate d total distance from start to goal through y.

     while openset is not empty

         x := the node in openset having the lowest f_score[] value

         if x = goal

             return reconstruct_path(came_from,goal)

         remove x from openset

         add x to closedset

         foreach y in neighbor_nodes(x)

             if y in closedset

                 continue

             tentative_g_score := g_score[x] + dist_between(x,y)

 

             if y not in openset

                 add y to openset

 

                 tentative_is_better := true

             elseif tentative_g_score < g_score[y]

                 tentative_is_better := true

             else

                 tentative_is_better := false

             if tentative_is_better = true

                 came_from[y] := x

                 g_score[y] := tentative_g_score

                 h_score[y] := heuristic_estimate_of_distance(y, goal)

                 f_score[y] := g_score[y] + h_score[y]

     return failure

 

 function reconstruct_path(came_from,current_node)

     if came_from[current_node] is set

         p = reconstruct_path(came_from,came_from[current_node])

         return (p + current_node)

     else         return the empty path

سپاسگذارم.{گل}

دوست عزیز شما اول باید مشخص کنید که می خواید این روش را یاد بگیرید یا اینکه یاد گرفتید و می خواید پیاده سازی کنید.
اگر می خواید خوب یاد بگیرید همون مثال فاصله شهر ها در کتاب راسل را مرحله به مرحله دنبال کنید قطعا خواهید فهمید که روش کار به چه شکلی است.
اگر مثال را متوجه شدید فهمیدن کدها خیلی ساده خواهد بود و به هر زبانی که بخواهید می توانید پیاده سازی کنید.
اگر باز هم سوالی بود در جزئیات آن می توانید بپرسید

mardin200 عزیز، من به حرف شما گوش کردم و یکبار دیگه مطالب مربوط به A-star از راسل رو خوندم.
ببینید چیز کلی که من از این نوع جستجو بدست آوردم، اینه که A-star کم هزینه ترین مسیر را انتخاب میکنه تا به هدف برسه.
g(n) هزینه رسیدن به گره ای هست که هر بار از بین همسایه ها (فرزندان) انتخاب میشه.
h(n) هم هزینه رسیدن از گره ای که انتخاب کردیم تا هدف هست. درست؟
حالا f(n) ما، یعنی کل ارزش مسیرمون، جمع دو تا تابع بالایی هست.

من قبل از اینکه سوالم رو بپرسم یه معذرت خواهی بابت پست قبلیم بدهکارم، من اونجا مشخص نکرده بودم که شبه کدی که گذاشتم، مربوط به "حل معمای 8 (پازل هشت) توسط A-star هست."
الآن ادیتش میکنم.

خب با این اوصاف، مشکل من اینه که نمیدونم چطور باید در درخت معمای 8 هزینه ها رو پیدا کنم؟
اصلا فکر کنم بهتره اول هر گامش رو به صورت شکل، روی کاغذ بیارم، تا بهتر تحلیل بشه.

مرحله اول ما پازل آغازین معمای 8 رو با 4 تا فرزند داریم:

http://img3.tinypic.info/files/00ml6gx5njou62zhk6jd.jpg

حالا از کجا باید بدونیم که برای انتخاب در سطح 3 چه گره ای را انتخاب کنیم؟

اگر قرار باشه فرزندای این 4 تا هم مشخص بشن که احتیاجی به این کار نیست، این فرزندان رو داریم:

http://img3.tinypic.info/files/dcx72v0cbixs24w5z2d2.jpg

اون 2 تایی که با ضربدر سبز مشخص کردم در واقع میتونن نباشن.

من تحلیل معمای 8 با A-Star را برای پروژه هوش واقعا نیاز دارم، امیدوارم برای یادگیریش کمکم کنید.

چرا کسی این شبه کد رو برای من توضیح نمیده؟
شما که همتون متخصصیت دوستان.

گاهی، نگاهی، ثوابی ...

سلام قبل هر چیز ببخش که یکم دیر شد.
ما در ابتدا باید یک تابع اکتشافی خوب برای مسئله پیدا کنیم.
مقدار تابع برابر است با مجموع فاصله های افقی و عمودی هر عدد با مکان اصلی آن که همان هدف است.
مثلا در مثالی که خودتون انتخاب کردید همان حالت آغازین را در نظر بگیرید، فاصله عدد 8 با مکان اصلی خودش 3 است.ی2 حرکت افقی و یکی عمودی و اگر برای تک تک اعداد آن این مقادیر را بدست آوریم حاصل تابع برای این حالت برابر است با:

1+1+3+3+2+0+1+1+2=14

این مقدار، مقدار تابع h است. مقدار تابع g را هم به این صورت می توان بدست آورد ولی برای محاسبه آن باید فاصله هر حالت با حالت آغازی بدست آوریم و برای هر حالت f=g+h را بدست می آوریم برای هر نود که کمتر بود آن را بست می دهیم.
مثلا برای حالت اول که بست دادی :

f(1)=2+12=14 f(2)=2+16=18 f(3)=2+14=16 f(4)=2+14=16

پس حالا بهتر است ابتدا نود شماره 1 را بسط دهیم 3 یا 4 را هم ذخیره داشته باشیم شاید بعدا از طریق آنها به جواب بهتر برسیم
پیاده سازیش را هم با# C در سایت قرار دادم
بازم اگه سوالی بود ما هستیم.
با آرزوی موفقیت

مرسی مارین جان.
h رو متوجه شدم، ولی g رو نه!
یعنی 12 و 16 و 14 را که برای جمع با 2 استفاده کردی از کجا اومده؟
و اصلا خوده 2 ها را از کجا آوردین؟

ببخشید من یه کم زیاد آیکیوم پایینه:دی

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

بعد اینکه استاد ما علاوه بر نوشتن برنامه، میخواد تحلیل رو به صورت شکل روی کاغذ هم پیاده سازی کنیم.

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

ماردین جان قربون دستت..:53:
الهی که خیر از زندگیت ببینی جوون، نمیدونید چقدر خوشحالم که الآن با خیال راحت کامل و درست با مقادیر h و g به جواب رسوندمش.

از گرافش خیالم راحت شد.:o