الگوریتم جستجوی هزینه غیر آگاهانه


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

الگوریتم جستجوی هزینه
مسیر کشف شده با هزینه کمینه توسط الگوریتم جستجوی هزینه

در واقع الگوریتم جستجوی هزینه با قرار دادن نود های دارای هزینه کمتر در ابتدا صف فضای وضعیت، همیشه ابتدا آن نود هایی را گسترش میدهد که دارای هزینه کمتری هستند. الگوریتم، هزینه مورد نظر مسیر را با استفاده از تابع (G (n که در مطالب قبل در مورد آن صحبت نمودیم بدست می آورد. برای مثال در نرم افزار Google Map با استفاده از تصاویر ماهواره ای هزینه ترافیک خیابان های یک شهر بزرگ را محاسبه مینماید و از این اطلاعات در یافتن مسیر های بهینه استفاده میکند. در نرم افزار مسیر یاب آلفا که تصویر آن را در بالا مشاهده مینمایید هزینه مسیر ها را با اعداد فرضی و ثابتی مشخص کرده ایم. این اعداد با رنگ قرمز بر روی نقشه مشخص شده اند و نمایانگر طول خیابان میباشند. هرچه طول خیابان بیشتر باشد هزینه آن بیشتر در نظر گرفته شده است. پس نتیجتا طبق توضیحات بالا با محاسبه هزینه دسترسی به وضعیت های ایجاد شده از وضعیت اولیه، الگوریتم آن وضعتی را گسترش میدهد که کمترین هزینه را داشته باشد. طبق روال گذشته این فرآیند تا یافتن وضعیت هدف ادامه پیدا خواهد کرد. واضح است که در صورتی که تمامی وضعیت های فضای وضعیت بررسی شده باشند و به هدف نرسیده باشیم هیچ مسیری بین دو نقطه مذکور موجود نخواهد بود. نکته ای که باید به آن توجه کرد این است که، در این الگوریتم، اولین راه حلی که کشف شود، بهینه ترین راه حل خواهد بود، به این علت که با توجه به روشی که در بالا توضیح داده شده است اگر مسیری با هزینه کمتر وجود داشت، قبل از مسیر کشف شده فعلی مورد بررسی قرار میگرفت. یادمان باشد که این الگوریتم جستجو هم کامل و هم بهینه میباشد این در حالی است که از نظر پیچیدگی زمان و حافظه میتوان آن را ناکارامد در نظر گرفت. در مطالب آینده که مرتبط با مبحث روش های جستجوی آگانه میباشند از مزایای این الگوریتم در جستجوی *A استفاده خواهد شد.

بگذارید قسمتی از کد برنامه را که در این الگوریتم وظیفه دریافت نود های منتخب از فضای وضعیت را دارد با شما به اشتراک بگذارم. این تکه کد را با تصویر زیر مقایسه نمایید. (تکه کد C#)

var min = (from s in StateSpace.StateItems orderby s.Cost ascending select s.Cost).FirstOrDefault();
var state = (from s in StateSpace.StateItems where s.Cost == min select s).FirstOrDefault();

تمرین شماره 1: با توجه به تصاویر پایین و توضیحات بالا، ساختمان داده ای طراحی نمایید که قابلیت حمل وضعیت های روی درخت جستجو را داشته باشد.

الگوریتم جستجوی هزینه
در این مسیر هدف رسیدن به نقطه جی میباشد

 

2 Comments

Add a Comment

Your email address will not be published. Required fields are marked *

Copy Protected by Chetan's WP-Copyprotect.