الگوریتم جستجو A*


در این مطلب قصد داریم تا الگوریتم جستجو A* را برای شما تشریح نماییم. اگر دو مطلب الگوریتم جستجوی حریصانه و الگوریتم جستجوی هزینه غیر آگاهانه را که به عنوان پیش نیاز از آنها یاد شده مطالعه کرده باشید، به یاد خواهید آورد که

اولا روش “حریصانه” بطور محسوسی هزینه رسیدن از وضعیت اولیه به وضعیت هدف را کاهش میدهد. این درحالی است که متاسفانه این الگوریتم در عین بازدهی بالا نه بهینه است و نه کامل!

دوما روش جستجوی “هزینه غیر آگاهانه” علیرغم بازدهی پایین در مسائل واقعی، هم کامل و هم بهینه است.

همانطور که در مطالب قبل گفتیم در مورد اول و یا همان روش جستجوی حریصانه ما با استفاده از تابع هیورستیک h کمترین هزینه رسیدن از هر وضعیت به وضعیت هدف را تخمین زده و از میان وضعیت های موجود آن وضعیتی را برای جستجو گسترش میدهیم که دارای هیورستیک کمتری باشد. یعنی آن وضعیتی که نسبت به دیگر وضعیت ها به هدف نزدیک تر تخمین زده شده باشد. این در حالی است که در روش هزینه غیر آگاهانه با استفاده از تابع G همیشه  وضعیتی را گسترش میدهیم که هزینه آن از وضعیت اولیه تا وضعیت جاری، کمترین مقدار ممکن را داشته باشد. با این کار عملا همیشه به سمت کمترین هزینه ممکن حرکت خواهیم کرد.

حال که روش های بالا را یادآوری نمودیم و مزایا و معایب هرکدام از دو روش را به خاطر آوردیم، قصد داریم تا با بهره گیری از مزایای دو الگوریتم فوق و ترکیب آنها با یکدیگر الگوریتمی به نام الگوریتم جستجو A* را معرفی نماییم. در واقع ایده پشت این روشِ جستجو اینگونه است که میگوید : اگر از بین وضعیت های موجود بر روی درخت جستجو آن وضعیتی را گسترش دهیم که هم فاصله اش از دیگران با وضعیت هدف کمتر باشد (h) و هم نسبت به دیگران تا لحظه جاری هزینه کمتری را مصرف کرده باشد (G)، عملا از دو مزیت فوق بطور کامل بهره برده ایم. پس بطور ساده بیان خواهیم کرد که در الگوریتم جستجو A* آن وضعیتی از انباره جهت گسترش انتخاب میشود که دارای کمترین میزان fباشد.

F(n)=G(n)+h(n)

خوشبختانه میتوان گفت که الگوریتم جستجو A* هم کامل و هم بهینه میباشد که این موضوع با توجه به بازدهی بالای این الگوریتم، تا اینجا آن را به یکی از قدرتمند ترین روش های جستجوی تبدیل نموده است.

مثالی از نحوه عملکرد الگوریتم جستجو A*

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

 

 

در لحظه اول در وضعیت آراد میباشیم پس آن را وارد انباره و یا همان فضای وضعیت مینماییم (مقدار دهی اولیه انباره). سپس وضعیت را خارج نموده و آن را گسترش میدهیم. همانطور که مشاهده مینمایید از شهر آراد میتوان به طرف سه شهر زرین، تیمیسرا و سیبویی حرکت نمود. پس چون در حال حاضر هیچ وضعیتی جز آراد در انباره موجو نیست آن را گسترش داده و سه وضعیت نام برده را به فضای وضعیت اضافه مینماییم. حال برای انتخاب قدم بعدی، یعنی اینکه از آراد به سمت کدام شهر حرکت نماییم، برای سه وضعیت جدید تابع F را محاسبه نموده و آن وضعیت را که دارای کترین مقدار F میباشد را به عنوان شهر بعدی انتخاب مینماییم.

  • F(Zerind)=G(Zerind)+H(Zerind)=75+374=449
  • F(Sibui)=G(Sibui)+H(Sibui)=140+253=393
  • F(Timisora)=G(Timisora)+H(Timisora)=118+329=447

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

بررسی رفتار الگوریتم جستجو A*

اگر تصویر بالا را بررسی نمایید متوجه خواهید شد که در طول یک مسیر از شاخه های درخت هیچ گاه مقدار تابع f کاهش پیدا نمیکند. این مسئله یک رخداد اتفاقی نیست! این در واقع اتفاقی است که برای توابع هیوریستیک قابل قبول (admissible) رخ میدهد. تابع هیوریستیک قابل قبول تابعی است که دارای یکنواختی باشد (monotonicity). اما منظور از یکنواختی چیست؟ فرض کنید دو وضعیت A و B در فضای وضعیت موجود میباشند بطوری که A وضعیت والد B میباشد. حال فرض کنید که شرایط زیر برقرار باشد :

  • F(A)=G(A)+H(A)=3+4=7
  • F(B)=G(B)+H(B)=4+2=6

با توجه به این واقعیت که هر مسیر عبور کننده از B قطعا از A نیز میگذرد عملا مقدار f برای وضعیت B غیر قابل قبول است. زیرا برای رفتن از B به سمت هدف  باید حداقل f ِ وضعیت A را پشت سر گذاشته باشیم! در کتاب راسل اشاره شده که برای ترمیم مقادیر f که به علت عدم یکنواختی پیش می آید میتوان راهکار زیر را بکار برد. استفاده از این راهکار باعث در نظر نگرفتن مقادیری میشود که میتوانند جستجو را به سمت مسیر های اشتباه هدایت نمایند.

F(B)=MAX(F(A),(G(B)+H(B)))

از نظر نرم افزاری، برای اعمال چنین قانونی در کد نرم افزار خود میبایست در هر مرحله به هنگام حساب کردن مقدار f برای هر وضعیت در صورتی که مقدار f آن از مقدار f والد خود کمتر بود، مقدار والد را با فرزند جاگزین نمایید.

اثبات بهینه بودن الگوریتم جستجو A*

برای اثبات این موضوع ابتدا میبایست اصلی نسبتا واضح را ذکر نماییم. اگر *f را هزینه مسیر بهینه از وضعیت شروع تا وضعیت هدف در نظر بگیریم، بر اساس آنچه در مورد یکنواختی توضیح داده شد، برای هر وضعیت n بر روی مسیر مورد نظر تا هدف خواهیم داشت:

f(n)<=f*

یادمان باشد که

f* = F(Goal) = H(Goal) + G(Goal) = 0 + G(Goal)  f* = G(Goal)

حال که اصل بالا را گفتیم میتوانیم بهینه بودن این الگوریتم جستجو را اثبات نماییم.فرض کنید وضعیت G1، وضعیت هدف باشد که از طریق مسیر بهینه به آن رسیده باشیم که طبیعتا این وضعیت دارای *f میباشد. از طرفی فرض کنید G2 وضعیت هدف باشد در حالی که از مسیری غیر بهینه به آن رسیده ایم. که طبیعتا در این حالت

G(G2)>f*

حال شرایطی را در نظر بگیرید که در آن الگوریتم جستجو A* وضعیت غیر بهینه و یا همان وضعیت G2 را به عنوان پاسخ باز میگرداند. آیا همچین چیزی امکان پذیر است؟ با توجه به شواهدی که در پایین ذکر میکنیم عملا چنین چیزی امکان پذیر نیست و الگوریتم همیشه G1 و یا همان وضعیت هدف با کمترین هزینه ممکن را باز میگرداند.

1- n وضعیتی ما بین وضعیت اولیه تا وضعیت هدف G1 میباشد پس :

f(n)<=f*

از طرفی اگر الگوریتم G2 را به عنوان پاسخ به جای G1 بازگردانده میتوان ادعا نمود که

f(G2)<=f(n)

از تریکب دو نابرابری بالا میتوان بیان کرد که :

f(G2)<=f*

در اینجا به یک تناقض آشکار میرسیم. زیرا ما پیشتر به این نتیجه رسیدیم که :

G(G2)>f*

اگر قرار بود که G2 بهینه نباشد نابرابری بالا برای آن بی معنی و غیر قابل قبول بود.  پس میتوان نتیجه گرفت که A* همیشه وضعیت با هزینه بهینه را به عنوان پاسخ باز خواهد گرداند.

پیچیدگی الگوریتم جستجو A*

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

|h(n)-h*(n)|<=O(logh*(n))

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

استفاده از الگوریتم جستجوی A*
استفاده از الگوریتم جستجو در پروژه پازل 9 خانه
Copy Protected by Chetan's WP-Copyprotect.