الگوریتم جستجوی حریصانه

  • شماره مطلب : 17
  • دسته بندی : هوش مصنوعی
  • عنوان : الگوریتم جستجوی حریصانه
  • نویسنده : NetBoss
  • پیش نیاز : روش های جستجوی آگاهانه
  • پروژه عملی :

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

نمایی از عملکرد جستجوی حریصانه
نمایی از عملکرد جستجوی حریصانه

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

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

مثال : نقشه زیر مفروض است. فرض بفرمایید قصد سفر از Arad به Bucharest  را داریم. بر اساس الگوریتم جستجوی حریصانه مسئله را حل خواهیم نمود.

جستجوی حریصانه

همانطور که در نقشه فوق مشاهده مینمایید فاصله خط مستقیم بین دو شهر، در کادر قرمز رنگ ذکر شده. بدین ترتیب ما میتوانیم برای یافتن یک مسیر بین دو شهر آراد و بخارست از این اطلاعات اضافی استفاده نماییم. استراتژی حل مسئله ما این گونه خواهد بود که ابتدا وضعیت اولیه را وارد فضای وضعیت کرده و پس از آن وضعیت هایی را که فاصله خط مستقیم آنها به وضعیت هدف نزدیک تر است را به منظور گسترش از فضای وضعیت انتخاب مینماییم. در واقع ما در این مسئله تابع هیوریستیک خود را برابر با فاصله خط مستقیم بین وضعیت جاری تا وضعیت هدف در نظر گرفته ایم که با اصل تعریف تابع هیوریستک هم خوانی دارد. اگر دقت نمایید ما در طول حل مسئله با استفاده از این استراتژی به صورت خوش بینانه ای به سمت هدف نزدیک میشویم. مثلا اگر بخواهیم از تهران به سمت اهواز حرکت نماییم به جای انتخاب جاده هراز و شهرهای شمالی به صورت کور کورانه، به سمت جاده ها و شهر هایی که ما را به جنوب غرب هدایت مینمایند حرکت خواهیم کرد. دلیل نیز کاملا واضح است زیر شهر هایی که در جنوب غرب تهران واقع میباشند از نظر فاصله خط مستقیم به هدف نهایی نزدیکتر هستند! در نقشه بالا با استفاده از هیوریستیکِ کمترین فاصله خط مستقیم، اولین وضعیتی که پس از شهر ‘آراد’ گسترش داده میشود شهر ‘سیبویی’ خواهد بود زیرا این شهر از دو شهر ‘زریند’ و ‘تمیسرا’ به بخارست نزدیک تر است. پس از آن ‘فاگاراس گسترش داده شده و نهایتا به بخارست خواهیم رسید. همانطور که مشاهده مینمایید در این مثال بدون اینکه حتی یک نود اضافه گسترش داده شود با کمترین پیچیدگی جستجو (در زمان و حافظه) به مقصد رسیده ایم این در حالیست که پاسخ ما بهینه نمیباشد!  اگر دقت نمایید مسیری با طول 32 مایل کمتر به سمت بخارست موجود است که الگوریتم آن را از دست داده است.ما در ادامه علت بهینه نبودن پاسخ یافته شده و همچنین ضعف الگوریتم حریصانه را بررسی خواهیم کرد. 

  1. Arad is the only node in the state space and there is no other choice.
  2. Arad is selected.
  3. Zerind, Sibui and timisora are extended from Arad.
  4. The Sibui is selected as the next node because it’s straight distance from Bucharest is the shortest one.
  5. Sibui is extended so Fagaras and Rimnicu are added into the state space.
  6. Fagaras is chosen as the next node because it’s straight distance from Bucharest is the shortest one.
  7. Bucharest is achieved.

توجیه بهینه نبودن پاسخ و ضعف جستجوی حریصانه

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

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

بازدهی الگوریتم جستجوی حریصانه

همانند الگوریتم جستجوی عمق اول، الگوریتم جستجوی حریصانه به ادامه دادن یک شاخه از مسیر بر روی درخت تمایل دارد. همچنین در صورت مواجهه با بمبست در مسیر، توانایی تغییر مسیر بر روی درخت جستجو را دارا میباشد. این الگوریتم مانند الگوریتم جستجوی عمق اول از مشکل گیر افتادن در مسیر های بی نهایت و یا بسیار طولانی رنج میبرد. پس میتوان نتیجه گرفت که این الگوریتم نه کامل است و نه بهینه .  پیچیدگی زمان برای این الگوریتم در بدترین سناریو ی ممکن برابر با ( O( b^m که m حداکثر عمق درخت و b فاکتور انشعاب میباشند. از آنجا که این الگوریتم تمامی وضعیت های موجود را در حافظ نگهداری مینماید پیچیدگی حافظه آن همانند پیچیدگی زمانی خواهد بود. در آخر نیز باید یاد آور شد که با استفاده از یک تابع هیورستیک مناسب پیچیدگی زمان و حافظه در این الگوریتم ،کاهش چشمگیری خواهند داشت.

4 Comments

Add a Comment

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

Copy Protected by Chetan's WP-Copyprotect.