روش های جستجوی آگاهانه


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

در مطالب قبل دیدم که روش های جستجوی غیر آگاهانه، با تولید و درج وضعیت های جدید در فضای وضعیت (State Space) و سنجش آنها با استفاده از تابع تست هدف (Goal Test) سعی در رسیدن به پاسخ هدف دارد. راسل در کتاب خود این مکانیزم جستجو را یک مکانیزم سیستماتیک نامیده است. مثال هایی مانند مسیر یابی بر روی نقشه و حل مسئله هشت وزیر را با این الگوریتم ها انجام دادیم که میتوانید آنها را در اینجا ( پروژه مسیریاب هوشمند آلفا) و  اینجا (پروژه هشت وزیر) مشاهده نمایید. همانطور که در مطالب قبل خوانده اید و احتمالا خود نیز به آن پی برده اید متاسفانه این الگوریتم ها در مسائل دنیای واقعی میتوانند نا کارمد باشند.

جستجوی آگاهانه
جستجوی آگاهانه

یاد آوری اول

بطور خلاصه اگر مطالب مرتبط با روش های جستجوی غیر آگاهانه و مسائل خوش تعریف را خوانده باشید به یاد خواهید آورد که برای جستجوی یک پاسخ، با مفهومی با نام فضای وضعیت سر و کار داریم. فضای وضعیت در واقع انباره ای است که ما در آنجا وضعیت های جدید ناشی از یک وضعیت موجود را نگهداری مینماییم. مثلا فرض کنید در یک مسئله مسیر یابی ما در شهر A قرار داریم که سه مسیر خروجی از آن به شهر های B،C و D موجود میباشد. اگر بخواهید برای حرکت بین شهر ها، درخت جستجویی رسم نمایید باید وضعیت های A و BCD را که ناشی از آن (A) هستند،  در طول حل مسئله وارد انباره فضای وضعیت نمایید.

یادآوری دوم

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

در جستجوی آگاهانه به دنبال چه هستیم؟

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

رفع سوء تفاهم در نحوه عملکرد!

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

فانکشن ارزیابی چگونه کار میکند؟

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

2 Comments

Add a Comment

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

Copy Protected by Chetan's WP-Copyprotect.